编译原理 消除间接左递归的例子

### 编译原理中消除间接左递归的具体例子

在编译原理课程里，处理文法中的间接左递归是一个重要主题。当存在形如 A → Bα 和 B → Aβ 的规则时，则认为有间接左递归现象发生。

考虑如下含有间接左递归的简单算术表达式文法规则：

E -> T E'
E'-> + T E' | - T E' | ε
T -> F T'
T'-> * F T' | / F T' | ε
F -> ( E ) | id

这里 `E` 到 `T` 再回到 `E` 形成了一个循环路径，这便是典型的间接左递归情况[^1]。

为了消除上述文法里的间接左递归，可以按照以下方式重构这些产生式：

#### 改造前后的对比

改造之前：
- \( E \to T E'\)
- \( E' \to + T E' | - T E' | \epsilon\)

改造之后：
- \( E \to TE''\)
- \( E'' \to E'T | \epsilon\)
- \( E' \to + T | - T |\epsilon\)

同样的逻辑应用于其他部分：
- \( T \to FT''\)
- \( T'' \to T'F|\epsilon\)
- \( T' \to * F|/ F|\epsilon\)[^2]

通过这样的转换，原本可能导致无限循环的情况被有效避免了，并且保持了解析能力不变。值得注意的是，在实际应用过程中还需要进一步调整以确保新引入的状态不会再次引发新的问题。

对于更复杂的案例，比如涉及多个非终结符之间的相互调用形成的多层嵌套结构，同样可以通过类似的思路逐步拆解并最终达到完全去除所有形式的左递归的目的。