[컴파일러] 14. LALR 파싱 테이블

SLR = Simple LR 

CLR = Canonical LR

LALR = Look Ahead LR

 

파싱시 look ahead symbol을 하나만 보는 SLR(1), CLR(1), LALR(1)은 1을 생략하여 SLR, CLR, LALR로 부름

아이템 집합 구성시의 LR(0), LR(1)에서 숫자는 아이템에 포함시켜 나타낸 look ahead(예측 기호)의 갯수를 나타냄

 

canonical LR 파싱 테이블 구성

• 예측기호 포함
  • 적합하지 않은  reduce를 위해 더 많은 정보 포함
  • 두번째 요소로서 단말 기호 포함
  • [A->α●,a]
  • 입력기호 a가 올 경우만 reduce 수행
  • a는 FOLLOW(A)의 부분집합

Closure(I), LR(1) 아이템 집합의 구성

• I에 있는 모든 아이템을 closure(i)에 넣는다.
• [A->α●Bβ,a]가 Clousre(I)에 속해있고 B->γ 및 FIRST(β a)에 포함되는 각 단말기호 b에 대해 아이템[B->●γ,b]가 closure(I)에 없을 경우

Goto 연산

• goto(I, X): I는 아이템 집합, X는 문법기호
• goto(I, X)는 [A->  αX●β, a]에 대해 [A->  αX●β, a]의 집합 J

아이템 집합군 구성

canonical LR(1)의 아이템 집합군 구성 알고리즘

procedure items(G');
begin
	C:={closure({[S'-> ●ㄴ, $]})};
    repeat
    	for C의 각 아이템 집합 I와 문법기호 X에 대해(단 goto(I,X)는 빈것이 아니고 C에 포함되지 않음)
        do goto(I,X)를 C에 추가
    until C에 추가할 아이템 집합이 더 이상 없다.
end

 

 

LALR 파싱

기본 원리

• 핵 문법의 첫번째 요소
• 같은 핵을 가진 문법을 합쳐 상태수를 줄임
• CLR보다 오류를 늦게 감지

파싱테이블 구성

• 입력: 확장 문법 G'
• 출력 G'에 대한 LALR 파싱 테이블 함수

방법

• LR(1) 아이템 집합군 C을 구성
• 아이템 집합에서 같은 핵을 가진 아이템을 합침
• 새로 합친 아이템 집합군에 대해 canonical LR 파싱 테이블 구성 알고리즘을 적용하여 파싱 테이블을 만든다.(오류이면 LALR(1)문법이 아님)

오류감지

늦은 오류 감지

• 이 문법은 c*dc*d생성
• 첫번째 c들을 이동하고 다음 d를 스택에 넣고 상태 4로 감
• CLR의 경우 다음 입력기호가 c나 d일 경우만 reduce C->d를 수행
• 합친 상태에서 다음 입력기호 $에 대해 reduce를 수행하면 ccd와같은 입력을 받아서 오류가 됨
• LALR파서는 일단 수행하고 나중에 오류로 처리함.