左递归

递归"/>

左递归

空串产生式最常出现的情形——左递归的消除。

左递归是产生式的一种特殊形式。它的形式如下。

A→Aα $$A\rightarrow A \alpha$$

其中A是非终结符，而 α $\alpha$是由终结符和非终结符组成的字符串。注意， α $\alpha$不能是空串，否则产生式变为

A→A $$A\rightarrow A$$

没有任何意义。

左递归会对文法分析造成困扰。因为，根据产生式，我们可以不断进行如下推导。

A→→→→AαAααAααα... $$\begin{array}{lll} A&\rightarrow&A \alpha\\ &\rightarrow&A\alpha \alpha\\ &\rightarrow&A\alpha \alpha\alpha\\ &\rightarrow&... \end{array}$$

这样的推导可以无限进行下去，如果不对字符串做全面的分析，根本不知道哪里是尽头。而我们做语法分析，希望观察前面一个字符就能判断接下来使用哪个产生式。只有这样才能避免回溯，提高效率。

消除左递归，已经有一般化的公式。

先考虑如下一个简单的例子。

例： 考虑如下两个产生式。

A→Aα $$A\rightarrow A\alpha$$
A→β $$A\rightarrow \beta$$

其中A是非终结符， α $\alpha$和 β $\beta$非空，且 β $\beta$不以A开头。注意，对于文法中任何的非终结符，以它为左部的产生式不能全是左递归的。因为一个左递归函数，在自顶向下设计（前面几篇博文介绍的后缀表达式解析，以及去除注释，都是自顶向下设计。后面的博文会专门就这一问题展开讨论）中，左递归产生式对应着一个递归函数。而一个递归函数都需要有出口，即结束条件。而左递归产生式的出口，就是由非左递归产生式给出。

对于本例给出的这组产生式，可以转化为如下等价形式。

A→βR $$A\rightarrow \beta R$$
R→αR $$R\rightarrow\alpha R$$
R→ϵ. $$R\rightarrow\epsilon.$$

这两组产生式的等价性，我们不再证明。转化的主要思想是将左递归转化为右递归。这里仅声明一下，两组产生式等价的意义是指他们接受的字符序列的集合相同。

上面介绍的是一个左递归产生式，一个出口产生式的情形。在有的文法中可能有多个左递归产生式和出口产生式。

例： 对于如下一组包括左递归的产生式

A→Aα1A→Aα2A→Aα3A→β1A→β2 $$A\rightarrow A\alpha_1\\ A\rightarrow A\alpha_2\\ A\rightarrow A\alpha_3\\ A\rightarrow \beta_1\\ A\rightarrow \beta_2$$

其等价产生式为

A→β1RA→β2RR→α1RR→α2RR→α3RR→ϵ $$A\rightarrow \beta_1R\\ A\rightarrow \beta_2R\\ R\rightarrow \alpha_1R\\ R\rightarrow \alpha_2R\\ R\rightarrow \alpha_3R\\ R\rightarrow\epsilon\\ $$

例： 更一般地，对于如下产生式组

A→Aαi,1≤i≤I,A→Aβj,1≤j≤J, $$A\rightarrow A\alpha_i, 1\leq i \leq I,\\ A\rightarrow A\beta_j, 1\leq j \leq J,$$

其等价产生式为

A→βjR1≤i≤I,1≤j≤JR→αiR,1≤i≤IR→ϵ $$A\rightarrow \beta_j R 1\leq i \leq I, 1 \leq j \leq J\\ R\rightarrow\alpha_i R, 1\leq i \leq I\\ R\rightarrow \epsilon$$