11.1 LR 分析法基本思路

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

S –> E
E –> T
E -> E + T
T –> id
T -> ( E )

要解析的句子为 (id + id) 。根据观察，可知其折叠过程为：

  (id + id) => (T + id) => (E + id) => (E + T) => (E)  =>  T  =>  E => S
   ^^           ^               ^^      ^^^^^     ^^^      ^      ^
T->id        E->T            T->id   E->E + T  T->(E)   E->T   S->E

每一步的折叠部位和应用的产生式都标注在上面了。

下面，还是一步一步的跟踪整个过程，查看每一步是如何挑选出需要的产生式来的。

首先，最开始的中间句子为 (id + id) ，要使它发生折叠，只有当它的有子串可以与某一个产生式的右边匹配才有可能。将 (id+id) 和所有产生式的右边 E, T, E+T, id, (E) 进行比较，发现只有 id 能匹配上，但是 (id+id) 中有两处匹配上的子串，此处只选择最左边的那个，将此子串进行折叠，得到 T + id ，如下列表，下表中将中间句子和所有产生式都写到同一行，并加粗标出了最左边的匹配子串和相应的产生式：

再将此时的中间句子 T + id 与 E, T, E + T, id, (E) 进行比较，找到了两个匹配的子串，还是只选择最左边的，也就是 T ，将其折叠为 E 后，得到 (E+id) ，如下：

到了这里，情况就变得复杂了，此时的中间句子 (E+id) 可以和产生式 S->E, T->id 匹配上，那还是选择最左边的匹配子串吗？也就是折叠成 (S+id) ？不行，因为这样后面无论如何也无法折叠到 S 了。因此这里只能选择后面的 id 来折叠，折叠后得到 (E+T) ：

按以上原则，继续折叠，过程如下，每一步都加粗显示了中间句子中的、和某一个产生式的右边匹配的子串：

从以上可以看出 LR 分析法的复杂性，每个折叠步中，中间句子可能有好几个子串可以和某个产生式的右边匹配上，也就是说可以采取好几个不同方式进行折叠，但怎么挑选折叠方式却暂时没有明确的法则。在进一步讨论这个问题之前，先把上面的这个折叠过程改一下，改成一个基于栈和输入流的分析过程，按以下原则进行：

（1） 起始状态：栈内无任何符号，可以认为栈上是一个空串。

（2） 每个分析步：如果栈上的符号串不可折叠，则从输入流中读入一个符号，放到栈上的符号串的最后；否则，折叠此符号串，将需折叠的子串的所有符号出栈，并将折叠得到的非终结符放到栈的末尾。

具体流程如下表，表中的 shift 动作表示 “从输入流中读入一个符号，并放到栈顶（符号串的末尾）” ， reduce 动作表示一个折叠动作， $ 表示结束符 EOF 。

从以上过程可以看出，每次折叠栈上的符号串的时候，一定是对其后缀（右子串）进行折叠，即发生的折叠一定是这样的情况：栈上的符号串为 uv 、应用的产生式为 A -> v 、折叠后栈上的符号串为 uA ，而不可能发生这样的情况：栈上的符号串为 uvw （w不是空串）、应用的产生式为 A -> v 、折叠后栈上的符号串为 uAw （因为如果存在这样的折叠，那早已在前面的分析步中折叠过了）。

这就是 LR 分析法的命名原因，第一个 L 表示从左向右扫描输入流，第二个 R 表示每次折叠一定发生在栈上符号串的最右边。

上面的流程中，最重要的几个问题仍然没有说清楚，那就是： 栈上的符号串不可折叠是什么意思？什么样的符号串可折叠？怎么找出可行的折叠？如果有多个可行的折叠怎么办？

为了回答第一、二个问题，先介绍合法符号串和合法前缀等概念：

合法符号串（viable string） ： 如果一个符号串可由起始符号经过有限步展开得到，则称此符号串为合法符号串。

前缀（prefix）、后缀（sufix） ： 一个符号串 X1 X2 … XN 的前缀有 ε 、X1 、 X1 X2 、 X1 X2 … Xn ，后缀有 ε 、Xn 、 Xn-1 Xn 、 X1 X2 … Xn ，本站也称为左子串和右子串。

合法前缀（viable prefix） ：一个符号串如果是语法 G 中的合法符号串的前缀，则称其为合法前缀。

显然，任何时候，栈上的符号串都应该是一个合法前缀。因此，前面描述的流程中，还应该在 shift 动作的时候增加一个检查： shift 之后，栈上的符号串是一个合法前缀。而 reduce 动作之后，栈上的符号串也应该是一个合法前缀。因此， “可折叠” 的定义为：

可折叠的（reduceable） ： 若一个合法前缀 vu 应用产生式 A -> u 进行折叠后的符号串 vA 仍然是合法前缀，则称原符号串 vu 是可折叠的。

至于如何解决第三、四个问题，就不是一件容易的事情了，要找出可行的折叠，先要判断折叠前后的符号串是否是合法前缀，而一个语法 G 可能有无限多个合法前缀，要判断一个符号串是否是合法前缀几乎是和判断一个句子是否符合语法同样困难的事情。为了解决这个问题，需要引入 状态 和 形态 的概念，下一节中介绍这两个概念，同时，介绍如何利用这两个概念来构造 LR 分析表和动作表。注意，本节所描述的分析流程只是一个基本思路，真正的 LR 分析法流程仅仅是在思路和操作方式上有所类似。