LALR 파싱 테이블 구성 방법

Intro

• LALR 파싱 테이블 구성방법

LALR 파싱테이블 구성 방법

LALR은 LOOKAHEAD정보를 이용하기 때문에 SLR보다 훨씬 강력하면서도 CLR에서 CORE가 같은 아이템을 묶기때문에 파싱테이블 크기도 SLR과 같이 구성할 수 있다.

LALR 파싱 테이블은 C₁과 C₀에서 작성 하는 방법이있다.

C₁에서 유도

같은 core를 가진 LR(1) 아이템 집합들을 한 개의 LR(0) 아이템 집합으로 만들고 각 아이템의 lookahead는 LR(1) 아이템의 lookahead 합집합으로 구성하는 방법이다.

C₁ 예제

다음 C₁ 을 이용한 파싱테이블 작성

1.상태 I₃과 I₆이 같은 core를 가지고 있으므로 한 상태로 통합

I₃₆:

[C->c.C ,c/d/$]
[C->.cC ,c/d/$]
[C->.d ,c/d/$]

2.I₄과 I₇ 통합

I₄₇:

[C->d. ,c/d/$]

3.I₈과 I₉ 통합

I₈₉:

[C->cC. ,c/d/$]

파싱 테이블

C₀ 예제

문법

S -> L=R | R
R -> L
L -> *R | id

추가된 생성 규칙

0. S' -> S
1. S  -> L=R
2. S  -> R
3. R  -> L
4. L  -> *R
5. L  -> id

C₀과 GOTO 그래프

파싱 테이블

참고 저서

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