您可以自由地共享和演绎本文稿, 只需遵守开源协议[CC By 4.0]
如果这篇文章帮助到你, 可以请我喝一杯咖啡~
这一节的内容非常抽象，我觉得难度与数学分析或者复变函数相当。
我们的困境
上一节，我们简述了某些上下文无关文法可能会使递归下降语法分析陷入麻烦。因此，我们首先来解决这些麻烦。
左递归
我们在上一节的最后指出了递归下降语法分析可能会陷入单程递归的问题。这种问题主要是由重复调用同一个产生式，而且不获取新的词法单元而产生的。
产生这样的麻烦的产生式均形如：
\[A→ Ab|c\]这样的形式，由于A在产生式第一候选的最左边，我们称为左递归式文法。在从左到右的语法分析中，它会导致单程递归。
而这样的式子本质上是什么呢？我们可以推导一下：
这样的式子在推导的过程中会成为：
\[Abb...\]直到某一刻，它选了一次第二候选c，推导停止。
因此由A来的串都是形如
的。
那么我们可以将它写为：
\(A→ cA'\) \(A'→ bA' | \epsilon\)
那么，这个式子的左递归就被消除了。抽象为算法：
立即左递归消除算法
对于左递归表达式
\[A→ Aa_1|Aa_2|Aa_3|..|Aa_n|b_1|b_2|..|b_m\]我们对其重复单元$a_i$单设一个新的非终结符号A'。
我们将其不含A的所有终止产生式提前，置于A'之前
得到两个产生式：
\[A→ b_1A'|b_2A'|..|b_mA'\] \[A'→ a_1A'|a_2A'|a_3A'|..|a_nA'\]这就消除了直观的$A→Ab$类型的左递归，也称为立即左递归
间接左递归
但，某一类产生式虽然不具有立即左递归，但它经过若干次推导可以得到左递归的结果，即
\[A\rArr^*A...\]这样的情况我们同样不可接受，因此我们也需要消灭它。