More actions
LR파서 구현 단계
- BNF를 보고 작성하려는 LR파서의 수준(CLR, LALR, SLR 등)의 문법에 맞는지 확인.
- 제일 간단한 SLR 문법의 경우에도 shift-reduce collision, reduce-reduce collision등의 모호성이 발생할 수 있다.
- LR파서의 문법 수준에 맞는 BNF를 이용해 GOTO 그래프 작성.
- GOTO 그래프를 이용해 파싱 테이블 작성(터미널, 논터미널, 상태의 정보를 이용해서 작성)
간단한 BNF를 이용한 FIRST, FOLLOW의 예제
Sentence ::= Subject Verb Object . Subject ::= I | a Noun | the Noun Object ::= me | a Noun | the Noun | ε Noun ::= cat | mat | rat Verb ::= like | is | see | sees | go
FIRST(Sentence) = {I, a, the} FIRST(Subject) = {I, a, the} FIRST(Verb) = {like, is, see, sees, go} FIRST(Object) = {me, a, the, ε} FIRST(Noun) = {cat, mat, rat}
FOLLOW(Sentence) = FOLLOW(Subject) = {like, is, see, sees, go} FOLLOW(Verb) = {me, a, the, .} FOLLOW(Object) = {.} FOLLOW(Noun) = FOLLOW(Subject) ∪ FOLLOW(Object)