구문 분석 : 상향식 구문 분석 / SLR 구문 분석

가장 간단히 구현 가능한 LR 구문 분석 방법

LR(0) 항목 집합과 FOLLOW를 이용하여 SLR 파싱표를 만듦

SLR 파싱표는 LR(0) 항목의 정규 항목 집합으로부터 이동과 GOTO 행동을 구하고,

생성 규칙에 있는 논터미널 기호와 FOLLOW를 가지고 감축을 결정

 

SLR 파싱표 구성

입력: 문법 G'에 대한 SLR 파싱표

출력: 증가 문법 G'에 대한 SLR 파싱표

방법:

1. G'를 위한 LR(0) 항목 집합의 정규 항목 집합 C0 = { I0, I1, .... In }을 구성

2. 상태 i는 Ii에서 구성됨

- 점 뒤에 터미널이 있으면 SHIFT .. A → α•aβ 일 때, GOTO(Ii, a) = Ij 이면 action[i,a] = shift j (a를 읽고 j 상태로 이동)

- 점이 맨 뒤이면 REDUCE .. A → α•, A → α가 완성된 상태로 action[i, a] = reduce A → α, 단 a ∈ FOLLOW(A) (FOLLOW(A)에 있는 모든 terminal 을 reduce 트리거로 사용)

- 시작 규칙이 완성되면 ACCEPT .. S′ → S•, action[i, $] = accept

3. 점 뒤에 논터미널이 있으면

- A → α•Bβ, 그리거 GOTO(Ii, B) = Ij 이면  goto[i, B] = j, 이건 shift가 아니라 비단말 이동(GOTO)  * goto는 파싱 테이블

4. 표에서 비어 있는 칸 : 에러, LR(0) 항목 [S′ →•S]을 포함하는 상태가 시작 상태

 

SLR 구문 분석기를 만드는 과정

1. 문법이 주어진다

2. 증가 문법을 만든다

3. LR(0) 항목 집합의 정규 항목 집합을 구한다

4. 감축 행동을 결정하기 위해 FOLLOW를 계산한다

5. SLR 파싱표를 작성한다

 

예시

(1) 증가 문법

0. S' -> E

1. E -> E + T

2. E -> T

3. T -> T * F

4. T -> F

5. F -> (E)

6. F -> id

 

(2) LR(0) 항목 집합의 정규 항목 집합과 GOTO 그래프

 

(3) FOLLOW의 계산

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

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

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

 

(4) 파싱표 작성

파싱표는 ACTION TABLE(id, +, ..)과 GOTO 테이블(E, T, F)로 구성

각 칸은 상태 번호 + 입력 기호 -> 어떤 파싱 동작인가를 뜻함

 

Shift 규칙 (점 앞이 터미널이면 시프트)

- A → α•aβ 일 때, GOTO(Ii, a) = Ij 이면 ACTION[i,a] = shift j 

 

Reduce 규칙 (점이 끝에 오면 리듀스)

- A → α•이면 FOLLOW(A)의 모든 기호 a에 대해 ACTION[i, a] = reduce A → α

 

Accept 규칙

- I₁ : S′ → E• 이면 ACTION[1, $] = acc

 

GOTO 테이블 채우는 규칙

- 상태 i에서 GOTO(i, A) = j   이면 GOTO[i, A] = j

규칙대로 표를 만들면

- s는 시프트, n번 상태로 이동하라

- r은 리듀스, n번 생산 규칙으로 리듀스하라 

- s랑 r 뒤 숫자가 의미가 다름

간단히, 더 나올게 있으면 시프트 아니면 리듀스나 acc

GOTO는 논터미널에 의해서만 발생

상태	구문 분석기 행동						GOTO 함수
	id	+	*	(	)	$	E	T	F
0	s5			s4			1	2	3
1		s6				acc
2		r2	s7		r2	r2
3		r4	r4		r4	r4
4	s5			s4			8	2	3
5		r6	r6		r6	r6
6	s5			s4				9	3
7	s5			s4					10
8		s6			s11
9		r1	s7		r1	r1
10		r3	r3		r3	r3
11		r5	r5		r5	r5

 

 

LR 구문 분석 알고리즘

입력: 입력 문자열 w와 LR 파싱표

출력: 만약 w가 L(G) 안에 있으면 w에 대한 파스트리를 생성하고 그렇지 않으면 에러

방법: 구문 분석기는 스택의 초기 상태인 S0를 가질 때..

begin
    ip는 w$의 처음 기호를 가리킨다
    
    repeat
        s 는 stack의 톱 상태
        a는 ip가 가리키는 기호
        
        if action[s, a] = 이동 s'
            then begin a를 스택에 삽입하고 그 다음에 s'를 스택에 삽입한다
                       ip는 다음 입력 기호를 가리킨다
                 end
        else if action[s, a] = 감축 s' (생성 A -> β)
            then begin |β|개의 기호를 스택에서 삭제한다
                       A를 스택에 삽입한다
                       GOTO[s', A] = n이라면 n을 스택에 삽입
                 end
        else if action[s, a] = 수락
            then return
        else
            에러
    until ( ip = $이고 스택의 톱 = $ )
end

 

if * (id * id) 구문 분석하기

* 스택 구조는 [상태, 기호, 상태, 기호, 상태, ...]

단계	스택	입력 기호	구문 분석 내용
0	0	if * (id * id)$	s5
1	0id5	* (id * id)$	r6
2	0F	* (id * id)$	GOTO 3
3	0F3	* (id * id)$	r4
4	0T	* (id * id)$	GOTO 2
5	0T2	* (id * id)$	s7
6	0T2*7	(id * id)$	s4
7	0T2*7(4	id * id)$	s5
8	0T2*7(4id5	* id)$	r6
9	0T2*7(4F	* id)$	GOTO 3
10	0T2*7(4F3	* id)$	r4
11	0T2*7(4T	* id)$	GOTO 2
12	0T2*7(4T2	* id)$	s7
13	0T2*7(4T2*7	id)$	s5
14	0T2*7(4T2*7id5	)$	r6
15	0T2*7(4T2*7F	)$	GOTO 10
16	0T2*7(4T2*7F10	)$	r3
17	0T2*7(4T	)$	GOTO 2
18	0T2*7(4T2	)$	r2
19	0T2*7(4E	)$	GOTO 8
20	0T2*7(4E8	)$	s11
21	0T2*7(4E8)11	$	r5
22	0T2*7F	$	GOTO 10
23	0T2*7F10	$	r3
24	0T	$	GOTO 2
25	0T2	$	r2
26	0E	$	GOTO 1
27	OE1	$	acc

이렇게 해결이 된다

 

SLR(1) 문법은 모호하지 않으나,

SLR(1)이 아닌 모호한 문법도 존재

* 1은 lookahead(앞을 미리 보는 입력기호)의 개수

SLR 파싱표를 만들었을 때 두 가지 이상의 액션이 나올 수 있음

=> CLR, LALR 문법