10.1 LL(1) 分析法基本流程

为了解释什么是 LL(1) 法，首先来看一个简单的例子，语法为：

S -> aS | bS | c

需要解析的句子为 abac ，按上一章最后一节的方法，解析过程如下：

下面，一步一步跟踪这个解析过程，查看每一步是如何选择出需要的产生式的。首先，我们的目标是将起始符号 S 展开到 最终句子 abac 。把它们写在同一行来进行比较，如下：

假设有一个 strcmp 函数来比较符号串 “S” 和 “abac” ，从左向右一个符号一个符号的比较，找到第一个不匹配的符号，也就是 “S” 和 “a” ，上面的表格中，将第一个不匹配的符号加粗表示了。

因此，此时必须将中间句子中的 “S” 展开，才能得到最终句子。那如何展开呢？将最终句子中不匹配的这个 “a” ，和 S 的三个产生式的右边 aS 、 bS 和 c 相比，可以看出，只能选择 S -> aS 展开，才可以和 “a” 匹配上，展开后得到中间句子 aS ：

再次比较此时的中间句子 “aS” 和最终句子 “abac” ，找到的第一个不匹配的符号分别为 “S” 和 “b” ，将 “b” 和 S 的三个产生式比较，发现只能选择 S -> bS ，展开后得到中间句子 abS ：

按以上原则，每次都对中间句子和最终句子进行比较，找到第一个不匹配的符号，然后利用不匹配的符号挑选出需要的产生式，最终展开到最终句子：

因此 LL(1) 法的基本思路为：

每个推导步中，从左向右比较中间句子和最终句子，找到第一个不匹配的符号，如：中间句子为 u X v 、最终句子为 u a w 。显然，a 一定是终结符， X 则可能为非终结符，也可能为终结符，有以下 4 种情况：

情况 A ： X 为终结符，这种情况表明无论怎么展开都不可能展开到最终句子，即最终句子不合语法，此时终止推导。

情况 B ： X 为非终结符，假设它的所有产生式为 X -> u1 | u2 | … | un ，将 a 和这些产生式的右边 u1, u2, … , un 相比较，找出可以和 a 匹配的 ui ，将 ui 代替中间句子 u X v 中的 X ，得到下一个中间句子 u ui v，然后开始下一轮展开。

情况 C ： X 为非终结符，但它的所有产生式的右边 u1, u2, … , un 中，没有一个可以和 “a” 匹配上，这种情况表明最终句子不合语法，此时终止推导。

情况 D ： X 为非终结符，但它的所有产生式的右边 u1, u2, … , un 中，有两个或以上的 ui 可以和 “a” 匹配上，这种情况表明此语法不适于用 LL(1) 分析法，需要修改语法。

以上算法中，有一个重要的问题没有讲清楚，那就是怎么找出可以和 a 匹配的 ui 来，上面这个例子当然是简单的，直接比较产生式的第一个字符和 a 就可以找到，但遇到复杂的情况，比如产生式的最前面是一连串的非终结符怎么办？ 比如 X 可以展开成空串时怎么办？这个问题，我们稍后再讲，先来对这个算法稍微优化一下，先把基本的流程搞清楚。

上面的算法中可以优化的地方在于，其实没必要每次都从头开始比较中间句子和最终句子，上一轮推导步中已经比较过了的部分就没必要再比较了，比如说这一轮的中间句子为 u X v ，最终句子为 u a w ，可以应用的产生式是 X -> ui ，那么下一轮，可以把中间句子改为 ui v ，把最终句子改为 a w ，也就是把已经匹配的符号都去掉。这样每次不匹配的第一个符号就是最左边的符号。

按此思路，在展开的过程中插入一个 Match 动作，将已经匹配的符号去掉。另外，在起始符号和最终句子的末尾添加一个结束符 EOF （用 $ 表示），整个推导过程如下：

上面的过程中，Match 动作是将中间句子和最终句子最左边已匹配的符号去掉，这样每次不匹配的第一个符号就是最左边的符号，因此只需要根据最左边的两个符号来选择需要的动作。

Predict 动作就是应用一个产生式，将中间句子中的最左边的非终结符替换成该产生式的右边。

上面的列表的表头中，原来的 Working-string 改成了 Stack ，原来的 Final-string 改成了 Input ，这是因为这两列的符号串的操作方式就像一个栈和一个输入流一样。

以上分析的具体步骤为：

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

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

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

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

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

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

情况 C1 ： 在 X 的所有产生式 X -> u1 | u2 | … | un 的右边中，只有一个 ui 可以与 a 匹配上。此时，执行动作 Predict X -> ui ，将 X 出栈，将 ui 入栈，转到（3）；

情况 C2 ： 在 X 的所有产生式 X -> u1 | u2 | … | un 的右边中，没有一个 ui 可以与 a 匹配上。此情况表明最终句子不合语法，终止解析。

情况 C3 ： 在 X 的所有产生式 X -> u1 | u2 | … | un 的右边中，有两个或以上的 ui 可以与 a 匹配上。此情况表明此语法不适于用 LL(1) 分析法，需要修改语法。

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

以上就是 LL(1) 分析法的基本流程，所谓的 LL(1) ，第一个 L 表示从左向右扫描输入流，第二个 L 表示每一步展开的时候取中间句子中左边第一个非终结符进行展开，括号里面的 1 表示每次只读入 1 个符号，每次只利用这 1 个符号的信息来挑选产生式。

事实上，还有 LL(2) 、LL(3) 、 LL(k) 等分析法，每次一次性读入多个符号，然后利用这些符号的信息来挑选产生式。

以上所说的 Predict 动作，之所以叫 Predict ，是因为这个动作是预测的，只看到了第一个符号 a ，就预测接下来的一串符号必须是 ui 。