编译原理实验5——SLR(1)文法分析器实现
1、代码功能：
（1）计算非终结符的FIRST和FOLLOW集
（2）构造SLR分析表
（3）判断该文法是否为SLR文法
（4）输入字符串，按照SLR分析法判断该字符串的语法是否正确，并给出判断过程
2、代码的思路：
- 将文法中的每一个句子的左部和右部进行分离。其中，右部的每一个终结符和非终结符也是单独保存的。
- 将左部和右部分离后的文法中的终结符和非终结符识别出来。一般左部都是非终结符，那么右部除去非终结符就是终结符了。
- 计算FIRST集。设置一个变量_ALTERED_，在每次有新的终结符添加到FIRST集中的时候，就将_ALTERED_置为true。计算FIRST集的方法如下：
- 如果产生式右部是终结符a，且这个终结符a不在FIRST集中，则添加。
- 如果是非终结符A，则将A的FIRST集中的所有自己没有的终结符添加到自己的FIRST集中。
- 如果A的终结符中包含ε，则继续判断下一个。
- 计算FOLLOW集。设置一个变量_ALTERED_，在每次有新的终结符添加到FOLLOW集中的时候，就将_ALTERED_置位true。计算FOLLOW集的方法如下：
- 遍历文法中的所有产生式，所有出现在非终结符右边的终结符加入到相应follow集中，如果非终结符右边没有东西，则把$加入。 2、遍历文法中的所有产生式，若产生式最右边是非终结符，把左部非终结符的follow集的所有元素都添加到对应非终结符中。3、将$加入到第一个非终结符的follow集中。
- 根据每一条产生式，生成项目集规范族。程序设计的是对项目集规范族中的每一个项目集中的每一条项目都进行分析，产生了新的项目集就添加到项目集规范族中。
- 根据项目集规范族和FOLLOW集生成SLR分析表。根据 · 的位置判断是否将其添加到SLR分析表中，很容易。如果 · 后面的是终结符，将移进动作s添加到SLR分析表中的ACTION部分；如果 · 后面的是终结符，将转移添加到SLR分析表的GOTO部分；如果 · 在项目的末尾，将归约动作r添加到SLR分析表的ACTION部分。
- 设计词法分析器，用于分析输入的程序。
- 根据SLR分析表和词法分析的结果进行语法分析。
3、程序代码
具体代码请添加QQ：1277565476
4、测试结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| ===================文法预处理=======================
文法如下所示：
(1)E->E+T
(2)E->T
(3)T->T*F
(4)T->F
(5)F->i
(6)F->(E)
终结符：[+, *, i, (, )]
非终结符：[E, T, F]
===================First集如下=======================
文法的First集为：
First(E) = { i ( }
First(T) = { i ( }
First(F) = { i ( }
===================Follow集如下=======================
文法的Follow集为：
Follow(E) = { + ) $ }
Follow(T) = { $ * + ) }
Follow(F) = { $ * + ) }
===================项目集规范族如下=======================
I0：
START->·E
E->·E+T
E->·T
T->·T*F
T->·F
F->·i
F->·(E)
I1：
START->E·
E->E·+T
I2：
E->T·
T->T·*F
I3：
T->F·
I4：
F->i·
I5：
F->(·E)
E->·E+T
E->·T
T->·T*F
T->·F
F->·i
F->·(E)
I6：
E->E+·T
T->·T*F
T->·F
F->·i
F->·(E)
I7：
T->T*·F
F->·i
F->·(E)
I8：
F->(E·)
E->E·+T
I9：
E->E+T·
T->T·*F
I10：
T->T*F·
I11：
F->(E)·
================SLR预测分析表如下====================
+ * i ( ) $ E T F
0 0 0 s4 s5 0 0 1 2 3
1 s6 0 0 0 0 a0 0 0 0
2 r2 s7 0 0 r2 r2 0 0 0
3 r4 r4 0 0 r4 r4 0 0 0
4 r5 r5 0 0 r5 r5 0 0 0
5 0 0 s4 s5 0 0 8 2 3
6 0 0 s4 s5 0 0 0 9 3
7 0 0 s4 s5 0 0 0 0 10
8 s6 0 0 0 s11 0 0 0 0
9 r1 s7 0 0 r1 r1 0 0 0
10 r3 r3 0 0 r3 r3 0 0 0
11 r6 r6 0 0 r6 r6 0 0 0
===================句子识别=======================
请输入要识别的句子：i*(i+i)
------------------分析过程如下--------------------
栈 输入 动作
0 i*(i+i)$ 移进
0i4 *(i+i)$ 按F->[i]归约
0F3 *(i+i)$ 按T->[F]归约
0T2 *(i+i)$ 移进
0T2*7 (i+i)$ 移进
0T2*7(5 i+i)$ 移进
0T2*7(5i4 +i)$ 按F->[i]归约
0T2*7(5F3 +i)$ 按T->[F]归约
0T2*7(5T2 +i)$ 按E->[T]归约
0T2*7(5E8 +i)$ 移进
0T2*7(5E8+6 i)$ 移进
0T2*7(5E8+6i4 )$ 按F->[i]归约
0T2*7(5E8+6F3 )$ 按T->[F]归约
0T2*7(5E8+6T9 )$ 按E->[E, +, T]归约
0T2*7(5E8 )$ 移进
0T2*7(5E8)11 $ 按F->[(, E, )]归约
0T2*7F10 $ 按T->[T, *, F]归约
0T2 $ 按E->[T]归约
0E1 $ 接受
--------------------分析结束----------------------
SLR(1)分析法推导成功！
|