左递归

"一个文法是左递归的，若我们可以找出其中存在某非终结符号A，最终会推导出来的句型(sentential form)里面包含以自己为最左符号(left-symbol)的句型"^[1]

直接左递归

直接左递归（Immediate left recursion）以下面的句型规则出现：

${\displaystyle A\to A\alpha \mid \beta }$ 

这里${\displaystyle \alpha }$ 跟${\displaystyle \beta }$ 代表不同的非终结符号跟终结符号组成的序列，并且${\displaystyle \beta }$ 不一定要包含${\displaystyle A}$ 。举例来说，以下规则

${\displaystyle {\mathit {Expr}}\to {\mathit {Expr}}+{\mathit {Term}}}$ 

就是一个直接左递归的例子。 这规则的递归下降分析器(recursive descent parser)可能会像这样：

function Expr()
{  
    Expr();  match('+');  Term();
}

然后这个递归下降分析器在尝试去解析包含此规则的文法时，会陷入一个无穷的递归。

间接左递归

间接左递归(indirect left recursion)最简单的形式如下：

${\displaystyle A\to B\alpha \mid C}$ 

${\displaystyle B\to A\beta \mid D,}$ 

这规则可能产生 ${\displaystyle A\Rightarrow B\alpha \Rightarrow A\beta \alpha \Rightarrow \ldots }$  这种生成。

简单的说，间接左递归就是，并非在一条规则内完成左递归，而是在许多条规则之后，于产生的句子最左边出现了一开始的非终结符号。

更一般化的说法，对非终结符号${\displaystyle A_{0},A_{1},\ldots ,A_{n}}$ ，间接左递归被定义为以下的型态：

${\displaystyle A_{0}\to A_{1}\alpha _{1}\mid \ldots }$ 

${\displaystyle A_{1}\to A_{2}\alpha _{2}\mid \ldots }$ 

${\displaystyle \cdots }$ 

${\displaystyle A_{n}\to A_{0}\alpha _{n+1}\mid \ldots }$ 

这里的${\displaystyle \alpha _{1},\alpha _{2},\ldots ,\alpha _{n}}$ 都是一堆终端与非终结符号的序列。

一个包含左递归的形式文法不能以简易的 递归下降分析器进行语法分析，除非将文法转变为weakly equivalent 的右递归形式 (相对的，在LALR分析器里面则比较偏好左递归，因为比起右递归来说会使用比较少的堆叠)；然而，比较复杂的由上而下(top-down)语法分析器里面可以借由使用缩减(by use of curtailment)来实做一般的上下文无关文法。 在2006年, Frost 和 Hafiz 提出一个算法，可以容纳包含直接左递归生成规则的 模糊文法（英语：ambiguous grammer）(ambiguous grammers)。^[2] 在2007年，Frost，Hafiz和Callaghan 将此算法延伸为一个完整的，可以适用并在多项式时间内处理直接或间接左递归，而且可以为高度模糊文法接近指数数目的分析树，产生小一些多项式空间的表示法。^[3]这些人后来在Haskell编程语言里面以这个算法实做了一个的分析器组合(parser combinator)的集合。^[4]

移除直接左递归

一个一般化后移除直接左递归的算法如下所述。 这个方法已经有过许多的改进，包括Robert C. Moore所撰写，名为"Removing Left Recursion from Context-Free Grammars"的改进。^[5]

对于每个规则如下

${\displaystyle A\rightarrow A\alpha _{1}\,|\,\ldots \,|\,A\alpha _{n}\,|\,\beta _{1}\,|\,\ldots \,|\,\beta _{m}}$ 

(注意这里：

• A 是一个有左递归的非终端符号
• ${\displaystyle \alpha }$  是一个终端与非终端符号的序列，而且不为空字串 (${\displaystyle \alpha \neq \epsilon }$ )
• ${\displaystyle \beta }$  是一个不以A开头的，以终端与非终端符号组成的序列)

将A的规则改成以下规则：

${\displaystyle A\rightarrow \beta _{1}A^{\prime }\,|\,\ldots \,|\,\beta _{m}A^{\prime }}$ 

然后对新创造出来非终端符号的规则

${\displaystyle A^{\prime }\rightarrow \epsilon \,|\,\alpha _{1}A^{\prime }\,|\,\ldots \,|\,\alpha _{n}A^{\prime }}$ 

这个新创造出来的符号常被称为"尾巴"(tail)，或者"rest"(剩余)

举例，考虑以下规则

${\displaystyle Expr\rightarrow Expr\,+\,Expr\,|\,Int\,|\,String}$ 

我们可以改写为

${\displaystyle Expr\rightarrow Int\,ExprRest\,|\,String\,ExprRest}$ 

${\displaystyle ExprRest\rightarrow \epsilon \,|\,+\,Expr\,ExprRest}$ 

然后最后一个规则可以缩短改写为

${\displaystyle ExprRest\rightarrow \epsilon \,|\,+\,Expr}$ 

来避免掉左递归的出现

移除间接左递归

如果文法内不存在 ${\displaystyle \epsilon }$ (代表空字串)的生成 (不存在${\displaystyle A\rightarrow \ldots |\epsilon |\ldots }$ 这样的规则)，而且不是循环(cyclic)的文法(对所有非终端符号A，不存在像是${\displaystyle A\Rightarrow \ldots \Rightarrow A}$ 这种形式的规则)，以下这个一般化的算法可以用来去除文法的间接左递归：

将所有非终端符号以某个固定的顺序${\displaystyle A_{1},\ldots A_{n}}$ 排列

从 i = 1 到 n {

从 j = 1 到 i – 1 {

• 设${\displaystyle A_{j}}$ 的生成规则为

${\displaystyle A_{j}\rightarrow \delta _{1}|\ldots |\delta _{k}}$ 

• 将所有规则 ${\displaystyle A_{i}\rightarrow A_{j}\gamma }$ 换成

${\displaystyle A_{i}\rightarrow \delta _{1}\gamma |\ldots |\delta _{k}\gamma }$ 

• 移除${\displaystyle A_{i}}$ 规则中的直接左递归

}

}

上面的转换使用右递归的文法来避免掉左递归的出现；但是这样会改变规则的结合律。左递归会创造出向左的结合律；但是右递归则会创造出向右的结合律。

范例 :

一开始我们拿到以下文法：

${\displaystyle Expr\rightarrow Expr\,+\,Term\,|\,Term}$ 

${\displaystyle Term\rightarrow Term\,*\,Factor\,|\,Factor}$ 

${\displaystyle Factor\rightarrow (Expr)\,|\,Int}$ 

在我们使用上面的转换方式来移除掉左递归之后，我们取得了以下文法：

${\displaystyle Expr\rightarrow Term\ Expr'}$ 

${\displaystyle Expr'\rightarrow {}+Term\ Expr'\,|\,\epsilon }$ 

${\displaystyle Term\rightarrow Factor\ Term'}$ 

${\displaystyle Term'\rightarrow {}*Factor\ Term'\,|\,\epsilon }$ 

${\displaystyle Factor\rightarrow (Expr)\,|\,Int}$ 

我们将字串 'a + a + a'用一个LALR分析器(这种分析器可以处理左递归的文法)使用原先的文法来分析，会得到下面的分析树(parse tree)：

                            Expr
                         /   |   \
                       Expr   +   Term
                     /  |  \        \
                   Expr  + Term      Factor
                    |      |       |
                   Term    Factor    Int
                    |      |
                  Factor    Int
                    |
                   Int  

整个分析树是往左边长，代表在这里的规则，'+'这个符号是左结合(left associative)的，或者说这规则代表(a + a) + a。

但是我们改变了文法之后，那这个分析树会变成：

                            Expr ---
                           /        \
                         Term      Expr' --
                          |       /  |     \ 
                        Factor   +  Term   Expr' ------
                          |          |      |  \       \
                         Int       Factor   +  Term   Expr'
                                     |           |      |
                                    Int        Factor   ${\displaystyle \epsilon }$ 
                                                 |
                                                Int

我们可以看出这棵树现在是往右边成长，意思上代表了a + ( a + a)。我们将'+'的结合律改变了, 变成是右结合的规则。 在处理加法的文法时这不是什么问题，但是如果我们现在处理的是减法，这就会变成是很严重的问题。

问题的关键在于有很多常用的算术规则要求左结合的规则。我们有几种解决办法： (a) 将规则重新改为左递归，(b) 使用更多的非终端符号来改写规则，以强迫文法合乎正确的结合(c) 如果使用YACC 或者Bison，他们有所谓算符宣告(operator declarations)， %left, %right and %nonassoc，这一些算符可以告诉语法分析器产生程式(parser generator)应该遵从哪一种结合。

• 尾部递归

1. ^ Notes on Formal Language Theory and Parsing （页面存档备份，存于互联网档案馆）, James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02
2. ^ Frost, R.; R. Hafiz. A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time.. ACM SIGPLAN Notices. 2006, 41 (5): 46–54 [2010-10-11]. doi:10.1145/1149982.1149988. （原始内容存档于2020-06-28）.  引文使用过时参数coauthors (帮助)
3. ^ Frost, R.; R. Hafiz and P. Callaghan. Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars. (PDF). 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE (Prague). June 2007: 109–120 [2010-10-11]. （原始内容 (PDF)存档于2011-05-27）.  引文使用过时参数coauthors (帮助)
4. ^ Frost, R.; R. Hafiz and P. Callaghan. Parser Combinators for Ambiguous Left-Recursive Grammars. (PDF). 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN. January 2008, 4902 (2008): 167–181 [2010-10-11]. doi:10.1007/978-3-540-77442-6_12. （原始内容存档 (PDF)于2008-12-21）.  引文使用过时参数coauthors (帮助)
5. ^ Moore, Robert C. Removing Left Recursion from Context-Free Grammars (PDF). 6th Applied Natural Language Processing Conference. May 2000: 249–255. （原始内容 (PDF)存档于2006-09-16）. 

• CMU lecture on left-recursion （页面存档备份，存于互联网档案馆）
• Practical Considerations for LALR(1) Grammars （页面存档备份，存于互联网档案馆）
• X-SAIGA （页面存档备份，存于互联网档案馆） - eXecutable SpecificAtIons of GrAmmars