一、什么是左递归
在编译原理中，左递归指的是文法中存在左递归产生式的情况。左递归产生式指的是产生式中的某一非终结符A可以通过一系列产生式推导出自己，且A在推导过程中以A作为产生式的第一个符号，即A → Aα（α为任意符号串）。
例如，文法E → E + T | T中，E → E + T这个产生式就是一个左递归产生式，因为E在这个产生式中作为第一个符号。
二、左递归的问题
虽然左递归产生式可以用来描述某些语言的结构，但是在语法分析的时候会带来一定的麻烦。具体来说，处理左递归产生式时容易陷入无限递归的状态。
例如，对于文法E → E + T | T，如果我们采用自顶向下的递归下降算法，那么在处理E的时候会一直递归下去，直到栈溢出。
三、消除左递归的方法
3.1 直接左递归的消除
针对形如A → Aα1 | Aα2 | …… | Aαn这样的产生式，可以通过以下方法消除直接左递归：
A → Aα1 | Aα2 | …… | Aαn 变为 A → β1A' | β2A' | …… | βnA' A' → α1A' | α2A' | …… | αmA' | ε
其中，A’为新的非终结符，α1,α2,…,αm为原产生式右部开头不含A的符号串，β1,β2,…,βn为原产生式右部除去α部分以外剩余部分，即α1,α2,…,αn之后的部分，ε表示空字符串。此时，原文法中的所有产生式都不含直接左递归。
3.2 间接左递归的消除
针对形如A → Bα这样的产生式，且存在B → Aβ这样的产生式，即B可以推导出A，并且A又可以推导出B，这就是间接左递归。可以通过以下方法消除间接左递归：
A → Bα | γ1 | …… | γn B → Aβ1 | δ1 | …… | δm 变为 A → γ1A' | …… | γnA' A' → β1A' | δ1A' | …… | δmA' | α1 | …… | αk | ε B → α1A' | …… | αkA'
其中，A’为新的非终结符，α1,α2,…,αk为能够推导出某个终结符的非终结符集合，即F={X | X → x， x∈Vt}，Vt为终结符集合，ε表示空字符串。
四、实际应用
下面以一个具体的例子来说明如何通过消除左递归改善语法分析。
假设有以下文法：
S → S + T | T T → T * F | F F → ( S ) | id
在这个文法中，S存在直接左递归产生式S → S + T。我们可以先将其消除：
S → TS' S' → + TS' | ε T → FT' T' → * FT' | ε F → ( S ) | id
然后，我们可以将这个文法转化为LL(1)文法。具体来说，我们可以先把每个符号的FOLLOW集合求出来：
FOLLOW(S) = {$, )}
FOLLOW(S') = FOLLOW(S) = {$, )}
FOLLOW(T) = {+, $, )}
FOLLOW(T') = FOLLOW(T) = {+, $, )}
FOLLOW(F) = {* , + , $, )}
可以发现，在FOLLOW(S)和FOLLOW(S’)中都含有$，说明我们可以通过S的FIRST集合来选择S → ε。具体来说，如果下一个符号是$或者)时，我们就使用S → ε来进行归约。因此，我们需要将FIRST(S’)加上$和)，即：
FIRST(S') = + $ )
然后，我们可以根据FIRST和FOLLOW集合来构造预测分析表：
| ( | ) | id | * | + | $ | |
|---|---|---|---|---|---|---|
| S | S → TS’ | S → TS’ | ||||
| S’ | S’ → +TS’ | S’ → ε | S’ → ε | S’ → ε | ||
| T | T → FT’ | T → FT’ | ||||
| T’ | T’ → ε | T’ → *FT’ | T’ → ε | T’ → ε | ||
| F | F → (S) | F → id |
这样，我们就可以使用LL(1)分析器来分析符合这个文法的语句了。
五、总结
消除左递归是编译原理中比较基础的内容，对于语法分析有着重要的意义。在实际应用中，我们可以使用一些常见的算法，如上述的消除左递归的方法和构造LL(1)文法的方法来处理左递归情况，从而使得语法分析更加高效。