编译原理LL1文法消除左递归

### LL(1) 文法中消除左递归的方法

对于LL(1)文法中的左递归，无论是直接还是间接形式，都需要通过特定方法来消除。这不仅有助于提高语法分析效率，还能够简化后续处理过程。

#### 识别并转换为无左递归的形式

当遇到形如 \( A \rightarrow A\alpha | \beta \)[^1] 的规则时，表明存在直接左递归现象。为了去除这种模式，可以将其重写成如下结构：

\[ A \rightarrow \beta A' \]
\[ A' \rightarrow \alpha A' | \epsilon \]

这里引入了一个新的非终结符\(A'\)，用于表示原生产式的剩余部分，并允许它重复出现直到不再匹配为止。

针对间接左递归的情况，则需先找出所有可能形成循环路径的非终结符组合，再按照上述方式逐一替换掉这些潜在问题点。具体操作上可遵循以下原则：

- 将涉及的所有非终结符按一定顺序排列；
- 对于每一个非终结符，在其后的每个定义里查找是否存在前序已处理过的非终结符作为开头；
- 如果发现这样的情况，则应用前述变换策略重构相应规则集；

#### 实际案例说明

考虑给定的一个简单例子——表达式求值器的一部分语法规则:

E -> E + T | T    (原始规则)
T -> num          (终端符号num代表数值常量)

显然这里的`E->E+T`构成了典型的直接左递归情形。依据前面介绍的技术手段改造后得到的新版本应该是这样子的：

E  -> TE'
E' -> +TE'| ε     （其中ε为空串）

如此这般便成功消除了原有的左递归特性，同时也保持了原有语言描述能力不变。