龍進在自顶向下的语法分析中，我们会遇到回溯的问题以及无限循环的问题。
无限循环
递归下降解析器的无限循环问题主要来自于左递归文法。
直接左递归文法
以下文法，就是一个直接左递归文法：
$$E \Rightarrow E+T | E-T | T $$
$$T \Rightarrow T*F | T/F | F$$
$$F \Rightarrow (E) | id$$
当我们尝试使用$E -> E + T$进行最左推导时，会出现：不断的使用推导结果最左边的这个E，去应用产生式$E \Rightarrow E + T$，最终导致无限循环。
我们将含有$A \Rightarrow A \alpha$形式的产生式的文法称为是直接左递归的文法。
消除直接左递归
首先我们要理解直接左递归文法推导出来的到底是什么东西。
对于这样的一个产生式：
$$ A \Rightarrow A \alpha | \beta \ (\alpha \ne \varepsilon) $$且$beta$不以$A$开头。
我们每次都选择左边这个产生式进行推导，那么我们将会得到这样的一个结果：
$$ A \Rightarrow A \alpha \cdots \alpha $$
最终我们再使用$A -> \beta $来替换上述产生式右部的$A$，得到：
$$ A \Rightarrow \beta \alpha \cdots \alpha $$
所以，本质上是产生了一个一$\beta$开头的，拥有任意个$\alpha$的字符串。
用正则表达式描述即为：
$$ r = \beta \alpha^* $$
在理解上面这个本质之后，我们就可以知道，我们要消除左递归，其实就是想要写出另一组产生式，能够等价的，不含直接左递归的产生式，能够表示上面这个正则表达式的意思即可。
由于最终推导出来的字符串以$\beta$开头，因此我们引入一个$A’$，用来代表$\alpha^*$.
因此我们得到了
$$A \Rightarrow \beta A’$$
接着，$A’$的任务就是生成若干个$\alpha$，因此我们将$A’$定义如下：
$$A’ \Rightarrow \alpha A’ \ | \varepsilon $$
观察可以看到，我们新列出来的这组产生式，完成的功能与原来的是相同的。事实上，这个消除的过程就是把左递归换成了右递归，使得递归下降解析器能正常工作。
天下没有免费的午餐，消除左递归需要付出的代价就是，引入了新的非终结符和新的$\varepsilon \_ $产生式。
对于更一般的情况，则有：
$$ A \Rightarrow Aa_1 \ | \ Aa_2\ \cdots \ | \ Aa_n \ | \ b_1 \ | \ b_2…… \ | \ b_m $$
其中，$a_i \ne \varepsilon, \ \beta_j$不以$A$开头。
转换为：
$$ A \Rightarrow b_1A’ \ | \ b_2A’ \ \cdots \ | \ b_mA’ $$
$$A’ \Rightarrow a_1A’ \ | \ a_2A’ \ \cdots \ | \ a_nA’ \ | \ \varepsilon$$
间接左递归文法
存在经过多步推导得到的左递归产生式的文法称为间接左递归文法。
比如，下面这个文法就是一个间接左递归文法：
$$ S \Rightarrow Aa \ | \ b $$
$$ A \Rightarrow Ac \ | \ Sd \ | \ \varepsilon $$
显然，我们能看出具有以下的间接左递归：
$$S \Rightarrow Aa \Rightarrow Sda$$
对于间接左递归文法，我们可以通过带入的方式，不断的穷举、替换，把它转换成直接左递归文法，然后用消除直接左递归的方法来做。
比如对于上面这个例子，我们可以将$S$的定义带入第二条产生式，得到：
$$ A \Rightarrow Ac \ | \ Aad \ | \ bd \ | \ \varepsilon $$
这样就转换为了直接左递归，然后再使用消除直接左递归的方法来解决了。
通用的方法
对于不含循环推导和空产生式的文法G，有以下方法来消除左递归：
回溯问题
对于回溯问题，则是由于公共左因子的存在，解析器暂时还没有获得足够的信息，无法做出确定的决策，不知道到底应该转移到哪个状态。因此，我们只需要提取公共左因子，将其作为一个新的非终结符，这样就能推迟解析器作出决策的时机，从而解决回溯问题。
如果一次提取不能解决问题，则进行多次提取即可。
转载请注明来源：https://longjin666.cn/?p=1617
欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~
