SLR 파싱 테이블 구성 방법

Intro

• SLR 파싱 테이블 구성방법

SLR 파싱테이블 구성 방법 예제

다음 문법을 위한 SLR 파싱 테이블 구성

E -> E+T | T
T -> T*F | F
F -> (E) | id

추가된 생성 규칙

0. E' -> E
1. E  -> E+T
2. E  -> T
3. E  -> T*F
4. T  -> F
5. F  -> (E)
6. F  -> id

C₀ 및 GOTO 그래프

LR(0) 아이템 [A->α.β] a≠ε이면 kernal 아이템이다.

[A->.α] 처럼 심벌이 처음에 있는 아이템은 closure 아이템이며 S’이 새로운 시작 심벌일 때, 아이템 [S’->.S]는 kernal 아이템이 된다.

[A->α.]와 같이 생성 규칙 끝에 점이 있는 아이템은 reduce 아이템이다.

예시

FOLLOW 계산

FOLLOW(E) = {$, +, )}

FOLLOW(T) = {*, +, ), $}

FOLLOW(F) = {*, +, ), $}

파싱 테이블

Nontermianl 심벌 이동 상태를 GOTO테이블에 적고, Terminal 심벌 이동 상태는 ACTION 테이블에 Shift 번호를 적는다.

reduce 아이템은 예를 들어 5번 상태 [F->id.]의 생성 규칙 번호가 6이므로 F의 FOLLOW {*, +, ), $} 에 r6을 적어준다.

a*a+a 구문 분석 과정

참고 저서

오세만, 컴파일러 입문, 정익사,2010, 329쪽