10.3 LL(1) 动作表及 LL(1) 解析

LL(1) 动作表用 M 表示，可以看成一个二维数组，或一个字典，动作表中的 M[A, a] 保存了在解析过程中当栈顶为非终结符 A 、读入的符号为 a 时所应采取的动作。动作表的构造过程为：

对语法中的每条产生式： A -> u ：

（1） 对 First(u) 中的所有终结符 a （不含 ε ），置 M[A, a] = “A -> u” ；

（2） 若 First(u) 含 ε ，则对 Follow(A) 中的所有符号 a （可含 $ ），置 M[A, a] = “A -> u” 。

构造出动作表后，解析步骤为：

（1） 将结束符 $ 和起始符号 S 压入栈中；

（2） 从输入流中读入下一个终结符，赋给 a ，也就是执行一次 a = yylex() ；

（3） 设栈顶符号为 X ，有以下三种情况：

情况 A ： X == a 且 a == $ ，解析成功，终止解析；

情况 B ： X == a 且 a != $ ，执行 Match 动作，将 X 出栈，转到（2）；

情况 C ： X != a 且 X 是非终结符，有两种情况：

情况 C1 ： M[X, a] = “X -> u”，执行 Predict 动作，将 X 出栈，压入 u ，转到（3）；

情况 C2 ： M[X, a] 未定义，输入不合语法，终止解析；

情况 D ： X != a 且 X 是终结符，输入不合语法，终止解析。

下面来练习一下 LL(1) 分析法，语法为：

E   –>  T E'
E'  –>  + T E' | ε
T   –>  F T'
T'  –>  * F T' | ε
F   –> ( E ) | int

要解析的句子为： int + int * int 。

首先计算出所有非终结符的 first set 和 follow set ：

First(E)  = First(T) = First(F) = { ( int }
First(T') = { * ε}
First(E') = { + ε}
Follow(E) = Follow(E') { $ ) }
Follow(T) = Follow(T') = { + $ ) }
Follow(F) = { * + $ ) }

下面开始构造动作表 M 。

首先看第一个产生式： E -> T E’ 。 First(T E’) = { ( int } 。因此 M[E, (] = “E -> T E’” ， M[E, int] = “E -> T E’” 。写成表格的形式：

接下来看第二个产生式： E’ –> + T E’ 。 First( + T E’ ) = { + } 。因此 M[E’, +] = “E’ -> + T E’”。

再看第三个产生式： E’ -> ε 。 First( ε ) = { ε } ，且 Follow(E’) = { $ ) } ，因此 M[E’, $] = M[E’, )] = “E’ -> ε” 。都写到表格里面：

重复以上方法，最终的分析表为：

下面来解析句子 int + int * int ：