[컴파일러] 13. SLR 파싱테이블

5/19

 

SLR 파싱 테이블의 구성

LR(0) 아이템

• 문법 G의 생성규칙 오른쪽 임의의 위치에 점이 찍혀 있는 규칙
• 점은 진행의 정도를 나타낸다.

SLR 방법의 중심 개념

• 바이어블 프리픽스를 인식하는 결정 유한 오토마톤(DFA) 구성
• 아이템들은 SLR파서의 상태에 해당하는 집합
  • NFA의 상태에 해당
  • 부분집합구성 방법으로 아이템들을 함께 묶음.

 

Closure 연산

Closure(I): 아이템 집합의 구성

• I에 있는 모든 아이템을 closure(I)에 넣는다.
• A->a●Bβ가 closure(I)에 속해있고 B->γ가 closure(I)에 없을 경우

Goto 연산

• goto(I, X): I는 아이템 집합. X는 문법기호
• goto(I, X)는 A->a●Bβ가 I에 있을 때 모든 아이템 A->aX●β의 closure로 정의
• I가 바이어블 프리픽스 γ에 유효하다면 goto(I,X)는 바이어블 프리픽스 γX에 대한 유효한 아이템 집합

아이템 집합군 구성 알고리즘

//canonical LR(0)의 아이템 집합군 구성 알고리즘
procedure items(G');
begin
	C:={closure({[S'->S]})};
    repeat
    	for C의 각 아이템 집합 I와 문법기호 X에 대해 //단 goto(I,X)는 빈 것이 아니고 C에도 포함X
        do
        	goto(I,X)를 C에 추가
    until C에 추가할 아이템 집합이 더 이상 없다.
end

 

First(X)

• 문법기호 X의 맨 처음에 나올 수 있는 단말기호
• 규칙
  1. X가 단말이면 FIRST(X) = {X}
  2. 만약 X->ε가 있으면, FIRST(X)에 ε를 추가
  3. X가 비단말이고, X->Y1Y2Y3...Yk라는 생성식이 있을 경우
     • FIRST(Y1)의 원소 중 ε가 아닌 모든 기호를 추가
     • ε가 있을 경우
       • FIRST(Y2)의 ε가 아닌 모든 원소 추가
     • FIRST(Y1), FIRST(Y2)에 모두 ε가 있을 경우
       • FIRST(Y3)의 ε가 아닌 모든 원소 추가
     • 위를 반복
     • 모든 i에 대해 FIRST(Yi)가 ε를 가지고 있다면 FIRST(X)에 ε추가

FOLLOW(A)

1. FOLLOW(S)에 $를 넣음(S: 시작기호, $: 입력의 끝)
2. A->αBβ라는 생성식이 있고, A->αB라는 생성식이 있거나 FIRST(β)가 ε를 가질 경우
   • FOLLOW(A)의 모든 원소는 FOLLOW(B)에 속함.

+강의자료 13-15페이지 참고해서 공부할 것.