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

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

无限循环

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

直接左递归文法

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

$$E\Rightarrow E+T|E-T|T$$

$$T\Rightarrow T\ast 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 \epsilon )$$且$beta$不以$A$开头。

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

$$A\Rightarrow A\alpha \cdots \alpha$$

最终我们再使用$A->\beta$来替换上述产生式右部的$A$，得到：

$$A\Rightarrow \beta \alpha \cdots \alpha$$

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

用正则表达式描述即为：

$$r=\beta {\alpha }^{\ast }$$

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

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

因此我们得到了

$$A\Rightarrow \beta A^{\prime }$$

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

$$A^{\prime }\Rightarrow \alpha A^{\prime }|\epsilon$$

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

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

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

$$A\Rightarrow A{a}_1|A{a}_2\cdots |A{a}_n|b_1|b_2\dots \dots |b_m$$

其中，$a_i\ne \epsilon ,{\beta }_j$不以$A$开头。

转换为：

$$A\Rightarrow b_1{A}^{\prime }|b_2{A}^{\prime }\cdots |b_m{A}^{\prime }$$
$$A^{\prime }\Rightarrow a_1{A}^{\prime }|a_2{A}^{\prime }\cdots |a_n{A}^{\prime }|\epsilon$$

间接左递归文法

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

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

$$S\Rightarrow Aa|b$$

$$A\Rightarrow Ac|Sd|\epsilon$$

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

$$S\Rightarrow Aa\Rightarrow Sda$$

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

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

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

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

通用的方法

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

回溯问题

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

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

转载请注明来源：https://longjin666.cn/?p=1617

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~