LL (1), LR (1), LR (0), LALR (1) 문법의 예?

LL (1), LR (1), LR (0), LALR (1) 문법의 예?

---

일부 주요 구문 분석 알고리즘 (LL (1), LR (1), LR (0), LALR (1))에 대한 문법 모음이있는 온라인 리소스가 있습니까? 나는 이러한 가족에 속하는 많은 개별 문법을 찾았지만 누군가가 많은 예제 문법 세트를 작성한 좋은 자료를 알지 못합니다.

누구든지 그러한 자원을 알고 있습니까?

---

구문 분석 기법-실용 가이드 에는 거의 모든 유형의 문법에 대한 몇 가지 예 (예 : 유형 당 6 개 정도)가 있습니다. 두 번째 버전 책을 구입할 수 있지만 첫 번째 버전은 저자의 웹 사이트 에서 PDF 형식 (링크 하단 근처)에서 무료로 사용할 수 있습니다 .

저자는 또한 두 번째 버전의 코드 예제와 함께 번들로 제공되는 몇 가지 테스트 문법을 가지고 있습니다 . 여기 에서 찾을 수 있습니다 .

참고 :이 문법은 모두 출판 된 책이기 때문에 작습니다 (수십 규칙 미만).

---

위키 백과의 예

LL (1)

문법

S -> F
S -> ( S + F )
F -> a

입력

( a + a )

구문 분석 단계

S -> "(" S "+" F ")"
  -> ( "F" + F ) 
  -> ( "a" + F ) 
  -> ( a + "a" )       

LR (0)

문법

(1) E → E * B
(2) E → E + B
(3) E → B
(4) B → 0
(5) B → 1 

입력

1 + 1

구문 분석 단계

need to build a parser table and traverse through states.

LR (1)

문법

S’ -> S S 
S  -> C C 
C  -> c C | d

입력

cd

구문 분석 단계

large table

LALR

문법

A -> C x A | ε
B -> x C y | x C
C -> x B x | z

입력

xxzxx

구문 분석 단계

traverse large parser table

당신은 또한보고 싶을 수 있습니다

• 구문 분석 시뮬레이터 도구
• antlr 작품 - > 다운로드 <
• ocw mit에서 파서 테이블 생성
• 파싱에서 코드 생성까지 ocw mit
• 추가 예

---

나는 당신이 의도적으로 그렇게 구성된 문법 모음을 많이 찾을 것이라고 기대하지 않습니다. 주최자는 그 대가로 무엇을 얻습니까?

What you might have a chance of doing, is to find parser generators that correspond to each family (e.g., LL(1)), and go look for instances of inputs for that parser generator, all of which will be LL(1) by definition. For instance, ANTLR's grammars are all various versions of LL(k) depending on which version of ANTLR you pick (the description of the ANTLR version will tell what k it accepts); Bison grammars are all LALR(1) [ignoring the recent GLR option]. If you go to my website (see bio), you see a list of grammars that are all pretty much context-free (that is, not in any of the classes you describe).

EDIT: Note @Bart Kier's clarification that ANTLR can explicitly mark a grammar as LL(k) for specific k.

ReferenceURL : https://stackoverflow.com/questions/6480634/examples-of-ll1-lr1-lr0-lalr1-grammars