More actions
imported>linflus No edit summary |
imported>syjsmk No edit summary |
||
| Line 1: | Line 1: | ||
== LR파서 구현 단계 == | |||
* BNF를 보고 작성하려는 LR파서의 수준(CLR, LALR, SLR 등)의 문법에 맞는지 확인. | |||
** 제일 간단한 SLR 문법의 경우에도 shift-reduce collision, reduce-reduce collision등의 모호성이 발생할 수 있다. | |||
* LR파서의 문법 수준에 맞는 BNF를 이용해 GOTO 그래프 작성. | |||
* GOTO 그래프를 이용해 파싱 테이블 작성(터미널, 논터미널, 상태의 정보를 이용해서 작성) | |||
== 간단한 BNF를 이용한 FIRST, FOLLOW의 예제 == | |||
Sentence ::= Subject Verb Object ''.'' | Sentence ::= Subject Verb Object ''.'' | ||
Subject ::= ''I'' | ''a'' Noun | ''the'' Noun | Subject ::= ''I'' | ''a'' Noun | ''the'' Noun | ||
Revision as of 17:05, 22 August 2014
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)