自顶向下分析：解决回溯及无限循环问题

在自顶向下的语法分析中，我们会遇到回溯的问题以及无限循环的问题。

无限循环

递归下降解析器的无限循环问题主要来自于左递归文法。

直接左递归文法

以下文法，就是一个直接左递归文法：

当我们尝试使用E -> E + TE \Rightarrow E + T，最终导致无限循环。

我们将含有A \Rightarrow A \alpha形式的产生式的文法称为是直接左递归的文法。

消除直接左递归

首先我们要理解直接左递归文法推导出来的到底是什么东西。

对于这样的一个产生式：

且

我们每次都选择左边这个产生式进行推导，那么我们将会得到这样的一个结果：

最终我们再使用A -> \beta A，得到：

所以，本质上是产生了一个一\beta开头的，拥有任意个\alpha的字符串。

用正则表达式描述即为：

在理解上面这个本质之后，我们就可以知道，我们要消除左递归，其实就是想要写出另一组产生式，能够等价的，不含直接左递归的产生式，能够表示上面这个正则表达式的意思即可。

由于最终推导出来的字符串以\beta开头，因此我们引入一个A’，用来代表\alpha^*.

因此我们得到了

接着，A’的任务就是生成若干个\alpha，因此我们将A’定义如下：

观察可以看到，我们新列出来的这组产生式，完成的功能与原来的是相同的。事实上，这个消除的过程就是把左递归换成了右递归，使得递归下降解析器能正常工作。

天下没有免费的午餐，消除左递归需要付出的代价就是，引入了新的非终结符和新的\varepsilon \_ 产生式。

对于更一般的情况，则有：

其中，a_i \ne \varepsilon, \ \beta_j不以A开头。

转换为：

间接左递归文法

存在经过多步推导得到的左递归产生式的文法称为间接左递归文法。

比如，下面这个文法就是一个间接左递归文法：

显然，我们能看出具有以下的间接左递归：

对于间接左递归文法，我们可以通过带入的方式，不断的穷举、替换，把它转换成直接左递归文法，然后用消除直接左递归的方法来做。

比如对于上面这个例子，我们可以将S的定义带入第二条产生式，得到：

这样就转换为了直接左递归，然后再使用消除直接左递归的方法来解决了。

通用的方法

对于不含循环推导和空产生式的文法G，有以下方法来消除左递归：

回溯问题

对于回溯问题，则是由于公共左因子的存在，解析器暂时还没有获得足够的信息，无法做出确定的决策，不知道到底应该转移到哪个状态。因此，我们只需要提取公共左因子，将其作为一个新的非终结符，这样就能推迟解析器作出决策的时机，从而解决回溯问题。

如果一次提取不能解决问题，则进行多次提取即可。