[Programming] Shift Reduce Parser Example

Shift Reduce Parser Example

---

Shift Reduce Parser에 대한 예제 문제이다.

아래의 예제 문제를 살펴보며 Shift Reduce Parser에 대해서 이해할 수 있다.

---

#01 Example

 

# Parser Table

State	Action						Goto
	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

 

# Grammar

E -> E + T
E -> T
T -> T * F
T -> F
F -> (E)
F -> id

 

# Solution

Step	Stack	Input
1	0	(id*id)+id
2	0(4	id*id)+id
3	0(4id5	*id)+id
4	0(4F3	*id)+id
5	0(4T2	*id)+id
6	0(4T2*7	id)+id
7	0(4T2*7id5	)+id
8	0(4T2*7F10	)+id
9	0(4T2	)+id
10	0(4E8	)+id
11	0(4E8)11	+id
12	0F3	+id
13	0T2	+id
14	0E1	+id
15	0E1+6	id
16	0E1+6id5
17	Not Accepted

---