LR 파싱 과정

 

LR 파싱과정

   - LR 파싱은 Bottom-up 파싱

기법 중 하나로, LR 분석기를 사용하여 문법을 분석합니다. 이것은 스택(stack)과 상태(state)를 사용하여 해석과정을 진행합니다. LR 파싱 과정은 다음과 같이 진행됩니다.

1. 파서 생성 : LR 파싱을 위해 파서 생성기를 이용해 파서를 생성합니다.
2. LR 아이템 생성 : 각 규칙마다 LR 아이템을 생성합니다.
3. 상태 생성 : LR 아이템을 이용 하여 파싱 테이블의 상태를 생성합니다.
4. 파싱 테이블 생성 : 생성된 상태를 이용하여 파싱 테이블 생성
5. 파싱 : 생성된 파싱 테이블을 이용하여 입력을 분석하고 문법 규칙에 따라 파싱을 수행합니다.

예를 들어

E -> E+T | T
T -> T*F | F
F -> (E) | i

다음과 같은식을  SLR파싱 테이블을 구성한다고 가정을 하겠습니다.

 

위의 식을 기반으로 LR 아이템 생성을 합니다. (BNF 룰을 기반으로)

0. E' -> E
1. E  -> E+T
2. E  -> T
3. E  -> T*F
4. T  -> F
5. F  -> (E)
6. F  -> id

 

이제 생성된 LR 아이템을 이용하여 파싱테이블의 상태를 먼저 생성합니다. 각 상태는 '.' 이라는 기호에 따라 뒤에 나오는 순서를 표현한 것입니다. 이 마침표 기호'.'는 쉽게말해 "커서"를  뜻합니다. 이뒤에 올수 있는경우는 3가지가 있습니다.

1. non-terminal이 오는 경우 -> non-terminal에서 파생될 수 있는 모든 심볼들을 나열해서 정리합니다. 그다음 마침표를 뒤로 하나 이동 시켜 다음문자를 읽습니다.
2. terminal이 오는 경우 -> 그냥 마침표를 하나 옮겨서 다음 문자를 보게 한다.
3. 끝일 경우 -> $기호로 끝냅니다.

i0  :E' -> .E
     E -> .E+T
     E -> .T
     T -> .T*F
     T -> .F
     F -> .(E)
     F -> .id
     
I1  :E' -> E.
     E -> E.+T
     
I2  :E -> T.
     T -> T.*F
     
I3  :T -> F.

I4  :F -> (.E)
     E -> .E+T
     E -> .T
     T -> .T*F
     T -> .F
     F -> .(E)
     F -> .id
     
I5  :F -> id

I6  :E -> E+.T
     T -> .T*F
     T -> .F
     F -> .(E)
     F -> .id
     
I7  :T -> T*.F
     F -> .(E)
     F -> .id

I8  :F -> (E.)
     E -> E.+T
     
I9  :E -> E+T.
     T -> T.*F
     
I10  :T -> T*F

I11  :F -> (E).

이제 이 정보들을 기반으로 LR 파싱 테이블을 만듭니다. 파싱 테이블은 ACTION과 GOTO로 나뉩니다. ACTION 테이블엔 terminal 심볼들이 있고 ,shitf ,reduce,accept등이 있습니다. goto 테이블엔 non-terminal 심볼들이 있고 어디로 이동을 해야하는지 적혀있습니다. 

 

shift (n) -> 읽어야할 terminal값과 이동할 상태값(n)을 스택에 넣고, 상태이동(n상태로 이동)을 합니다.

 

reduce (n) -> 스택의 2개값을 pop 하고 위의 아이템 (n)번째 룰의 non-terminal을 스택에 넣습니다. 그이후 스택에서 두번째 상태 값에 있는 상태의 goto테이블에서 스택 가장위의 nonterminal값을 스택에 넣습니다.

 

accept -> 구문분석을 끝냅니다.

	ACTION						GOTO
STATE	id	+	*	(	)	$	E	T	F
0	S5			S4			1	2	3
1		S6				accept
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

 

 

다음은 a*b+c의 구문을 분석하는 과정을 예시로하겠습니다.

 

남은 식	연산 내용	스택
A*B+C$	shift 5	0
*B+C$	reduce 6	0A5
*B+C$	goto 3	0F
*B+C$	reduce 4	0F3
*B+C$	goto 2	0T
*B+C$	shift 7	0T2
B+C$	shift 5	0T2*7
+C$	reduce 6	0T2*7B5
+C$	goto 10	0T2*7F
+C$	reduce 3	0T2&7F10
+C$	goto 2	0T
+C$	reduce 2	0T2
+C$	goto 1	0E
+C$	shift 6	0E1
C$	shift 5	0E1+6
$	reduce 6	0E1+6C5
$	goto 3	0E1+6F
$	reduce 4	0E1+6F3
$	goto 9	0E1+6T
$	reduce 1	0E1+6T9
$	goto 1	0E
$	accept	0E1