消除左递归

在进行语法分析的过程中，我们需要根据文法构建语法分析树。如果分析树构建成功则说明语法正确，反之语法错误。因此，如何构建一棵语法分析树非常重要

构建语法分析树有两种方式，一种是自上而下的分析方法（由根部开始构建语法分析树），另一种是自下而上的分析方法。本文采用的是自上而下的分析方法

自上而下的分析方法存在一个问题：文法中存在左递归怎么办？

什么是左递归？假设存在一个文法 E → E+E，可能会存在以下的推导过程

$$ E→E+E→E+E+E→E+E+E+E→... $$

没完没了，陷入左递归状态，因此我们需要消除左递归

左递归的类型有以下两种：

直接左递归较为直观，以上文提到的 $A→A\alpha|\beta$ 为例，我们对他进行推导

$$ A→A\alpha→A\alpha\alpha→A\alpha\alpha\alpha→...→\beta \alpha...\alpha $$

可以看出，此文法生成的串一定以 $\beta$ 开头，后面跟随若干个 $\alpha$，且 $\alpha$ 的个数可以为 0

因此我们可以定义一个新的非终结符 $A'$，且新的文法满足以下条件

因此新的文法如下

$$ \begin{align*} A&→\beta A\\ A'&→\alpha A'|\epsilon \end{align*} $$

事实上，消除左递归的过程就是把左递归转换成了右递归

再举个例子，消除下面文法的左递归

$$ \begin{align*} E&→E+T|T\\ T&→T*F|F\\ F&→(E)|id \end{align*} $$

仔细观察上述文法，发现只有产生式 1 和产生式 2 有左递归。对于产生式 1，可以将 +T 看成一个整体 $\alpha$，T 看成是 $\beta$，于是产生式 1 就可以看成是

$$ E→E\alpha|\beta $$

根据第一个例子中消除左递归的方式，产生式 1 消除左递归后变为

$$ \begin{align*} E&→\beta E'\\ E'&→\alpha E'|\epsilon \end{align*} $$

再将 $\alpha,\beta$ 换回原来的符号

$$ \begin{align*} E&→TE'\\ E'&→+TE'|\epsilon \end{align*} $$

同理，对于产生式 2，将 *F 看成一个整体 $\alpha$，F 看成是 $\beta$，于是产生式 2 消除左递归后变为

$$ \begin{align*} T&→FT'\\ T'&→*FT'|\epsilon \end{align*} $$

如果某条产生式具有直接左递归，例如

其中，$\alpha_i\neq \epsilon$ 且 $\beta$ 不以 $A$ 开头

我们将其转换成不含左递归的产生式

$$ \begin{align*} A&→\beta_1A'|\beta_2A'|...|\beta_mA'\\ A'&→\alpha_1A'|\alpha_2A'|...|\alpha_nA'|\epsilon \end{align*} $$

消除左递归是要付出代价的，引进了一些非终结符和 $\epsilon$ 产生式

例如以下文法

$$ \begin{align*} S&→Aa|b\\ A&→Ac|Sd|\epsilon \end{align*} $$

随便推导一下

$$ S→Aa→Sda $$

可以发现推导了两步就出现了左递归。消除间接左递归的方法也很简单，对于上面的例子

$$ A→Ac|Aad|bd|\epsilon $$

$$ \begin{align*} A→bdA'|A'\\ A'→cA'|adA'|\epsilon \end{align*} $$

消除间接左递归的方法总结下来，分以下 3 步