左遞歸

在计算机科学里面，左递归是一种递归的特殊状况。
在上下文无关文法内里的说法，若一个非终端符号（non-terminal）r有任何直接的文法规则或者透过多个文法规则，推导出的句型（sentential form）其中最左边的符号 又会出现r，则我们说这个非终端符号r是左递归的。
使用类似的方式我们可以定义出某文法本身是左递归的。

定义

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

在由上而下语法分析(top-down parsing)里容纳左递归

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

陷阱

上面的转换使用右递归的文法来避免掉左递归的出现；但是这样会改变规则的结合律。左递归会创造出向左的结合律；但是右递归则会创造出向右的结合律。
范例 :
一开始我们拿到以下文法：
在我们使用上面的转换方式来移除掉左递归之后，我们取得了以下文法：
我们将字串'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   
                                                 |
                                                Int
我们可以看出这棵树现在是往右边成长，意思上代表了a + ( a + a)。我们将'+'的结合律改变了, 变成是右结合的规则。 在处理加法的文法时这不是什么问题，但是如果我们现在处理的是减法，这就会变成是很严重的问题。
问题的关键在于有很多常用的算术规则要求左结合的规则。我们有几种解决办法： (a) 将规则重新改为左递归，(b) 使用更多的非终端符号来改写规则，以强迫文法合乎正确的结合(c) 如果使用YACC 或者Bison，他们有所谓算符宣告(operator declarations)， %left, %right and %nonassoc，这一些算符可以告诉语法分析器产生程式(parser generator)应该遵从哪一种结合。