【编译原理复习专题3】语法分析的例子整理

SLR(1)

考虑文法：

$E\rightarrow E+T|T$

$T\rightarrow T*F|F$

$F\rightarrow (E) |id$

1.扩展文法：

$E’\rightarrow E$
$E\rightarrow E+T|T$
$T\rightarrow T*F|F$
$F\rightarrow (E) |id$

2.LR(0)项：

3.绘制LR(0)自动机：

4.由状态1、2、9可发现，这个语法有移进归约冲突，因此不是LR(0)文法，

而在状态1中，Follow(E’)={$},+不在E’的Follow集里面的，因此无歧义，在状态2和9中，Follow(E)={+,(,$},*不在E的Follow集里，也无歧义，该文法是SLR(1)文法。

5.构建SLR(1)分析表。

6.串(id+id)*id的分析过程:

	stack	input	action
1	$0	(id+id)*id$	S4
2	$0(4	id+id)*id$	S5
3	$0(4id5	+id)*id$	$r(F\rightarrow id)$
4	$0(4F3	+id)*id$	$r(T\rightarrow F)$
5	$0(4T2	+id)*id$	$r(E\rightarrow T)$
6	$0(4E8	+id)*id$	S6
7	$0(4E8+6	id)*id$	S5
8	$0(4E8+6id5	)*id$	$r(F\rightarrow id)$
9	$0(4E8+6F3	)*id$	$r(T\rightarrow F)$
10	$0(4E8+6T9	)*id$	$r(E\rightarrow E+T)$
11	$0(4E8	)*id$	S11
12	$0(4E8)11	*id$	$r(F\rightarrow (E))$
13	$0F3	*id$	$r(T\rightarrow F)$
14	$0T2	*id$	S7
15	$0T2*7	id$	S5
16	$0T2*7id5	$	$r(F\rightarrow id)$
17	$0T2*7F10	$	$r(T\rightarrow T*F)$
18	$0T2	$	$r(E\rightarrow T)$
19	$0E1	$	accept

因此该串被接受。