左递归

在计算机科学的形式语言理论中，左递归是递归的一个特例，一个字符串通过分解成同一语言的一个字符串（在左边）和一个后缀（在右边）的事实，被识别为一个语言的一部分。比如说1+2+3{displaystyle1+2+3}可以被识别为一个总和，因为它是一个后缀。可以被识别为一个和，因为它可以被分解为1+2{displaystyle1+2}，也是一个和。这也是一个和，以及+3{displaystyle{}+3}，也是一个和。，是一个合适的后缀。就上下文自由语法而言，如果一个非终端在其一个产物中的最左边的符号是它自己（在直接左递归的情况下），或者可以通过一些替换序列使它自己（在间接左递归的情况下），那么这个非终端就是左递归。

一个语法是左递归的，当且仅当存在一个非终端符号A{displaystyleA}可以派生出一个以其自身为最左边符号的句法形式。在符号上。{displaystyle`Rightarrow{+}}表示进行一个或多个替换的操作。表示进行一个或多个替换的操作，而α{displaystyle`alpha}是任何终端和非终端符号的序列。是任何终端和非终端符号的序列。

直接左递归发生在只有一个替换就能满足定义的情况下。它需要一个规则，其形式为{displaystylealpha}是一个非终端和终端的序列。是一个非终结者和终结者的序列。例如，规则{displaystyle{mathit{Expression}}to{mathit{Expression}}+{mathit{Term}}直接是左递归。｝是直接向左递归的。这个规则的从左到右的递归解析器可能是这样的voidExpression(){Expression();match('+');Term();}。而这样的代码在执行时将落入无限递归。

当左递归的定义通过几个替换被满足时，就会发生间接左递归。它需要一组规则，其模式为{displaystylealpha_{0},alpha_{1},ldots,alpha_{n}}可以是任何终端和非终端符号序列。可以是任何终端和非终端符号的序列。请注意，这些序列可能是空的。

左递归经常给解析器带来问题，要么是因为它导致解析器进入无限递归（如大多数自上而下的解析器的情况），要么是因为它们期望规则的正常形式禁止它（如许多自下而上的解析器的情况，包括CYK算法）。因此，一个语法经常被预处理以消除左递归。

消除直接左递归的一般算法如下。这个方法已经有了一些改进。对于一个左递归的非术语{displaystyleA{prime}rightarrow{alpha_{1}A{prime}mid{ldots}mid{alpha_{n}A{prime}mid{epsilon}}。重复这个过程，直到没有直接的左递归存在。