语法分析——自底向上方法（移入规约法）
本文将继续介绍用于语法分析的方法——自底向上法。
自底向上的语法分析
所谓自底向上，和自顶向下相反，并不是从开始符号起，从上至下根据输入构造语法分析树，而是从输入的词法单元向上构造分析树，直到处理完全部输入为止。 虽然研究如何从输入构造出语法分析树非常直观，但是翻译时通常不会显示地构造出语法分析树，而是利用语法制导翻译直接进行翻译。 自底向上的语法分析也有许多方法，这里我们主要介绍移入-规约法（Shift-reduce）。 移入-规约法，顾名思义，在每次读取一个词法单元时选择“移入”或“规约”。
以这个方法为框架，我们还可以构造一些通用的方法，称为LR语法分析技术。
这种技术构造一个状态机来做出移入与规约的决定。
我们将主要介绍三种LR分析技术：简单LR技术（SLR）、规范LR技术（CLR）和向前看LR技术（LALR）。
除此之外，还有一种称为通用LR技术（GLR）的方法，这种方法以时间复杂度为代价极大地拓展了能处理的文法，甚至可以处理二义性的文法。
由于LR语法分析技术也使用移入与规约，有些时候可以把它们看作移入规约技术的一个子集。
移入规约技术
我们回到这个具有左递归的表达式文法： \(\begin{aligned} E \quad &\to \quad E + T \; | \; T \\ T \quad &\to \quad T * F \; | \; F \\ F \quad &\to \quad (E) \; | \; \mathbf{id} \end{aligned}\) 以其为例进行下面的讨论。
规约
规约指的把输入串的某一个子串按产生式替换成对应的产生式头部的操作。 所谓自底向上的语法分析，可以看作是把输入串规约成开始符号的过程。 在这个过程中，关键点在于，规约哪个子串，又用哪个产生式规约这个子串。
我们考虑这个规约过程： \(\mathbf{id} * \mathbf{id} \; \to \; F * \mathbf{id} \; \to \; T * \mathbf{id} \; \to \; T * F \; \to \; T \; \to \; E\) 考虑第三次规约的过程，即$T * \mathbf{id} \; \to \; T * F$。 此时我们有两个选择：使用产生式$E \to T$或使用产生式$F \to \mathbf{id}$。 我们选择了第二个产生式。
不难发现，规约实际上就是推导的逆运算，因此自底向上分析对应于反向构造一个推导过程。 上面的规约过程对应于下面这个推导过程： \(E \Rightarrow_{rm} T \Rightarrow_{rm} T * F \Rightarrow_{rm} T * \mathbf{id} \Rightarrow_{rm} F * \mathbf{id} \Rightarrow_{rm} \mathbf{id} * \mathbf{id}\) 不难发现，正如图中标出的，这个推导实际上是最右推导。
句柄
我们首先定义句柄的概念：
如果存在最右推导 \(S \Rightarrow^*_{rm} \alpha A w \Rightarrow_{rm} \alpha \beta w\) 其中$w$是一个终结符号串（否则推导不是最右的），那么称紧跟$\alpha$的产生式$A \to \beta$是$\alpha \beta w$的一个句柄（Handle）。 为方便起见，我们通常把产生式体$\beta$而非这个产生式称为句柄。
通俗地讲，句柄就是和某个产生式体匹配的子串。 比如，在上一个例子中的第一次规约中，使用的句柄就是$\mathbf{id}$，而对应的产生式为$F \to \mathbf{id}$。 需要注意在第三次规约$T * \mathbf{id} \to T * F$中使用的句柄是$\mathbf{id}$而非$T$。 这是因为不存在推导$E \cancel{\Rightarrow^*_{rm}} E * \mathbf{id} \Rightarrow_{rm} T * \mathbf{id}$。 因此，并非所有和产生式体匹配的最左子串都是句柄。
如果一个文法是二义性的，那么可能存在多个句柄，但如果文法是无二义性的，那么每个最右句型都只有一个句柄。
如果已经知道每个句型的句柄，那么如何进行规约以得出最右推导呢？
假设输入串为$w$，而我们需要寻找这样的最右推导： \(S \Rightarrow_{rm} \gamma_1 \Rightarrow_{rm} \gamma_2 \Rightarrow_{rm} \cdots \Rightarrow_{rm} \gamma_n = w\) 我们直接在$\gamma_n$中寻找句柄，记为$\beta_n$，然后把它用产生式$A_n \to \beta_n$替代掉，就可以生成$\gamma_{n-1}$了。 这个过程可以很方便地用我们马上就要介绍的移入-规约分析技术实现。
那么如果给定一个输入和文法如何寻找句柄呢？ 这就是LR语法分析的用途了。
移入规约分析器
移入规约分析器是自底向上分析器的最常见形式。 和预测分析器相似，这种分析器也采用一个栈来保存文法符号。 同理，我们也只用栈和输入缓冲区来表示这种分析器的运行时状态，称为格局。
一个移入规约语法分析器对每一种可能的格局都会做出四种动作：
- 移入：将下一个输入的词法单元移入栈顶；
- 规约：利用某个产生式把栈顶的若干文法符号替换为产生式头部；
- 接受：当栈中只有开始符号而输入已经为空时，宣布语法分析已经完成；
- 错误：发现一个语法错误，并进行错误恢复。
移入规约分析过程具有一个重要的性质：对每次规约，其句柄必然在栈的顶部。 我们考虑两种两次连续最右推导的情况：
- $\alpha A z \Rightarrow_{rm} \alpha \beta B y z \Rightarrow_{rm} \alpha \beta \gamma y z$；
- $\alpha B x A z \Rightarrow_{rm} \alpha B xyz \Rightarrow_{rm} \alpha \gamma xyz$。
回忆一下，小写字母表示终结符号串，希腊字母表示任意符号串。 所有两次连续的最右推导必然是这两者之一：第一种表示第二次推导展开了第一次推导中的非终结符号，第二种表示第二次推导展开了第一次所使用的非终结符号左边的非终结符号。 注意如果出现第二种，那么第一次推导产生的符号必须都是终结符号，正如展示的那样。
显然，在这两个推导中，$\alpha \beta \gamma y z$和$\alpha \gamma xyz$的句柄都是$\gamma$； 而$\alpha \beta B y z$的句柄为$\beta B y$，$\alpha B xyz$的句柄为$y$。
下面反向考察它们在移入规约分析器中的表现。
对第一种情况，考察栈为$αβγ而输入为yz$的情况。
由于γ为句柄，我们进行规约，栈变为$αβB而输入不变。
现在栈顶没有句柄，因此进行移入，栈变为$αβBy而输入变为z$。
我们在栈顶又发现了句柄βBy，因此再次进行规约变为$αA。
此时又没有句柄，我们选择移入，栈变为αAz。
我们可以发现，对第一种情况，只考察栈顶是否出现句柄就可以顺利构造出最右推导。
对第二种情况同理。
这样，我们就证明了移入规约分析器对任何最右推导都只需要观察栈顶是否出现句柄即可给出正确的分析。
移入规约语法分析中的冲突
类比LL(k)文法，如果对于一个文法，只需要向前看$k$个（有限个）输入，就可以确定任何格局是采用移入还是规约，那么就称这个文法为LR(k)的。
其中，L表示从左向右扫描，R表示构造最右推导。
然而仍然存在一些文法，即使可以查看任意有限个输入，仍然不能决定下一步的行动，这个文法就是非LR的。 如果我们不能解决的是采用移入还是规约，那么称这个冲突为移入/规约冲突； 如果我们不能决定的是使用哪个产生式进行规约，那么这个冲突称为规约/规约冲突。
考虑经典的悬空-else问题，如果对一个移入规约分析器出现如下格局：
栈为$ ... "if" expr "then" stmt，输入为"else" ... $，那么分析器无法决定是进行移入（相当于把else和最近的if ... then ...匹配）还是进行规约（相当于把else和更前面的语句匹配），这就产生了一个移入/规约冲突。
现在我们假设存在一种语言，其数组下标访问和函数调用的语法一致，都是id(x,y,...,z)的形式，其文法如下：
stmt ::= id ( parameter_list )
parameter_list ::= parameter_list, parameter | parameter
parameter ::= id
expr ::= id ( expr_list ) | id
expr_list ::= expr_list, expr | expr
注意这个文法是左递归的，因此不是LL的。
现在考虑如下格局：
栈为$ ... id ( id，输入为, id ) ... $。
显然此时必须将栈顶的id规约，否则就永远无法消去它了。
问题在于，到达是使用expr还是parameter规约它，这就产生了一个规约/规约冲突。
解决方法之一需要使用符号表。
我们把表示函数名的词法单元名改为procid，而非id，这样第一个产生式就变成stmt ::= procid ( parameter_list ) ，从而不会产生冲突了。
但是，这就要求词法分析器区分procid和id，而这两者的正则表达式通常是相同的。
因此，词法分析器不得不查看符号表，以确定当前的标识符到底表示的是函数名还是变量名。
这样当语法分析器进入前述格局时就会采用expr ::= id进行规约。
注意我们使用了非栈顶元素（第二个id）来判定使用哪个产生式，尽管并没有使用它来规约。
在早期使用YACC生成前端的gcc/g++中，就使用了这个技巧来应对x * y的二义性。