U E D R , A S I H C RSS

New Compile Error/2014_08_16

LR파서 구현 단계

  • BNF를 보고 작성하려는 LR파서의 수준(CLR, LALR, SLR 등)의 문법에 맞는지 확인.
    • 제일 간단한 SLR 문법의 경우에도 shift-reduce collision, reduce-reduce collision등의 모호성이 발생할 수 있다.
  • LR파서의 문법 수준에 맞는 BNF를 이용해 GOTO 그래프 작성.
  • GOTO 그래프를 이용해 파싱 테이블 작성(터미널, 논터미널, 상태의 정보를 이용해서 작성)
    • 파싱 테이블의 크기 = 상태 수 * (터미널 + 논터미널 심볼 수)
  • 토큰이 하나 들어올 시 shift or reduce 작업을 수행하게 되며 이 과정에서 AST를 생성할 수 있음.

LALR과 SLR의 차이점

  • SLR과 LALR의 경우 둘 다 LR(0)지만 LALR의 경우 lookahead set을 만들어서 이를 이용해 생성해야 하는 파싱 테이블의 크기를 줄일 수 있음.

LR과 LL의 차이

  • LR -> reduce 중시
  • LL -> first를 따지며 shift를 중시

간단한 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)

MiniC Grammar의 분석

  • MiniC Grammar를 이용해 LR파서를 만드는 것을 고려할 경우 파싱 테이블의 크기가 너무 커짐
  • LL파서를 만들려고 해도 저 BNF를 바로 LL파서로 만들 수는 없음.
    • 대표적으로 ArgList에 대한 BNF에서 left-recursion이 발생함. 이러한 문제들을 제거해야 LL문법으로 만들 수 있음.

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:51
Processing time 0.0130 sec