CLR 파싱 테이블 구성 방법

Intro

• CLR 파싱 테이블 구성방법

CLR 파싱테이블 구성 방법

CLR 파싱 테이블을 만들기 위해서는 LOOKAHEAD 정보가 필요하다.

각 아이템은 그에 해당하는 LOOKAHEAD를 갖고 다니는데 LR(0)아이템에 LOOKAHEAD 정보를 보강한 것이 LR(1) 아이템이다.

[A->α.β, a] 의 형태를 이루며 A->α.β 부분은 CORE이며 LR(0) 아이템과 같다.

두번째 부분 a는 LOOKAHEAD이며 Reduce 아이템 일때 그 심벌에 대하여 reduce 행동을 한다.

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

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

S -> CC
C -> cC | d

추가된 생성 규칙

0. S' -> S
1. S  -> CC
2. C  -> cC
3. C  -> d

LR(1) 아이템의 CLOSURE

CLOSURE({S’->.S, $}) = {[S’->.S, $]}, [S->.CC, $], [C->.cC, c/d], [C->.d, c/d]}

[C->.cC, c/d]에서 c/d는 [C->.cC, c]와 [C->.cC,d]의 축약 표현이다.

C₁ 및 GOTO 그래프

파싱 테이블

cdd 구문 분석 과정

CLR의 한계점

C₁의 크기가 LOOKAHEAD에 따라 너무 커지기 때문에 파싱 테이블이 매우 커진다.

따라서 실제 프로그래밍 언어의 파싱 테이블로 사용하기에는 적합하지 않다.

그러므로 reduce 행동은 LOOKAHEAD 정보를 이용하고 파싱 테이블 크기는 작게 구성할 수 있는 LALR 방식을 사용한다.

참고 저서

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