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

SLR보다 훨씬 강력하고 CLR보다 파싱표가 작음

모호하지 않은 문맥 자유 문법으로 표현된 거의 모든 언어를 인식 가능, 에러 초기 탐지 가능

그러나 LR(0) 항목의 집합을 구한 후 파싱표를 만들기 위해 감축 항목이 있는 각 상태에서 lookahead 기호를 구하는데 상당한 시간과 노력이 소요됨

 

LALR 파싱표 구성 방법은 두 가지

- 파싱표를 구성하기 쉽지만 크기가 커지는 LR(1)을 가지고 구성하는 방법

- LR(0)와 lookahead를 가지고 구성하는 방법

 

CLR 파싱표로부터 LALR 파싱표 구하기

- 코어가 같은 거 그냥 묶어주면 됨

 

 

lookahead의 정의

- 상태 p에서 LR(0) 항목 [ A → α•β ]의 lookahed는 LA(p, [ A → α•β  ] )로 표기하며, p상태에서 A 다음에 나올 수 있는 터미널 기호의 집합

- γα가 상태 p를 access 한다는 것은 시작 상태로부터 γα만큼 보고 상태 p로 이동을 하였다는 의미

 

S -> L = R

S -> R

L -> * R

L -> id

R -> L

 

(1) 증가 문법

0. S' -> S

1. S -> L = R

2. S -> R

3. L -> * R

4. L -> id

5. R -> L

 

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

SLR이라면 여기서 이동-감축 충돌이 발생 

 

여기서, [ R -> L• ] 의 lookahead가 필요

결국 얘도 구해야 한다

[ S' -> •S, $ ]

[ S  -> •L=R, $ ]

[ S  -> L•=R, $ ] -> $여야 감축 가능

[ R -> •L, $ ]

[ R -> L•, $ ] -> $여야 감축 가능

(충돌이 안나는 부분도 lookahead 참고 필요, 그냥 생략)

 

(3) LALR 파싱표

상태	구문 분석기 행동				GOTO 함수
	=	*	id	$	S	R	L
0		s4	s5		1	3	2
1				acc
2	s6			r5
3				r2
4		s4	s5			7	8
5				r4
6		s4	s5			9	8
7	r3			r3
8	r5			r5
9				r1

 

(4) *id=id$ 구문 분석

단계	스택	입력 기호	구문 분석 내용
0	0	*id=id$	s4
1	0*4	id=id$	s5
2	0*4id5	=id$	r4
3	0*4L	=id$	GOTO 8
4	0*4L8	=id$	r5
5	0*4R	=id$	GOTO 7
6	0*4R7	=id$	r3
7	0L	=id$	GOTO 2
8	0L2	=id$	s6
9	0L2=6	id$	s5
10	0L2=6id5	$	r4
11	0L2=6L	$	GOTO 8
12	0L2=6L8	$	r5
13	0L2=6R	$	GOTO 9
14	0L2=6R9	$	r1
15	0S	$	GOTO 1
16	OS1	$	acc