문법은 LALR입니까?

Question

동일한 문법이 LR (1)이 아니라고 말하지만, 문법이 LAL이 아니라고 안전하게 말할 수 있습니까?

그렇지 않으면 문법이 LALR이되기위한 조건은 무엇입니까? (또는 LALR이 아닌 문법을 만드는 조건은 무엇입니까?)

도움을 주셔서 감사합니다!

Answer 1

LALR (1) ⊂ LR (1), 그렇다고 가정 할 수 있습니다. 두 문법은 비슷한 방식으로 언어를 표현하지만 LR (1)은 LALR (1)보다 더 많은 왼쪽 상태를 추적합니다. Cf. These lecture notes은 두 표현 간의 상태 차이를 설명합니다.

일반적으로 파서 생성기는 shift-reduce 단계를 만드는 모든 세부 사항을 처리합니다. 차이점은 큰 문법을 기반으로하는 생성자가 충돌없는 파싱 전략을 찾을 가능성이 높다는 것입니다.

Answer 2

This document 모두를 비교합니다.

Answer 3

여기 LR되는 간단한 문법 (1)가 아닌 LALR (1) :

G -> S 
S -> c X t 
    -> c Y n 
    -> r Y t 
    -> r X n 
X -> a 
Y -> a 

LALR (1) 파서 생성기 당신에게 LR (0) 상태 머신을 제공한다. LR (1) 파서 생성기는 LR (1) 상태 시스템을 제공합니다. 이 문법으로 LR (1) 상태 시스템은 LR (0) 상태 시스템보다 하나 더 많은 상태 을가집니다.

가

X -> a . 
Y -> a . 

하여 LR (1), 상태 머신이 포함 된 하나 위 두 상태 대신 의 :

X -> a . { t } 
Y -> a . { n } 

X -> a . { n } 
Y -> a . { t } 

문제

하여 LR (0), 상태 머신이 상태를 포함 LALR을 사용하면 룩 - 어 - 헤드에 대한 지식 없이도 상태가 처음으로 이루어지기 때문에 입니다. 그런 다음 상태 표를 작성한 후 머리 모양 을 검사하거나 작성합니다. 그런 다음 LALR 이 하나 개의 상태와 일반적으로 나중에 추가 된 봐 - 한 - 머리를 가지고, 는 다음과 같이 표시됩니다

X -> a . { t, n } 
Y -> a . { n, t } 

은 아무도 여기에 문제를 볼 수 있을까요? 미리보기가 't'이면 을 선택 하시겠습니까? 모호합니다! 따라서 LALR (1) 파서 생성기는 경험이 적은 문법 작성자에게 혼동을 줄 수있는 보고서 줄이기 충돌 감소 기능을 제공합니다 ( ).

LALR (1) 충돌이 LR (1) 파서 생성기로 해결 될 수있는 실제 컴퓨터 언어가 거의 없습니다. 그러나 이러한 충돌은 종종 LALR (2) 파서 생성기를 통해 해결할 수 있습니다.

그래서 내가 LRSTAR을 LALR (k) 파서 생성기로 만들었습니다. 은 런타임에 2보다 먼저 모양을 사용하여 위의 문법을 처리 할 수 ​​있습니다. LR (k) 파서 생성기누군가 LR (1)이지만 실제는 LALR (1)이 아닌 실제 문법을 보여줄 수 있습니다.