左递归文法消除无限递归的原理及ε符号作用解析

一、为什么ε是必须的？ #

原文法 A → A α | B 能生成的字符串是 B 后面跟 0 个或多个 α，比如：

• 0个α：B
• 1个α：Bα
• 2个α：Bαα
• ...

改写后的文法把A拆成了 A → B A'，其中A'的作用就是处理B后面的α序列。如果A'只有 A' → α A' 这一条产生式，那A'必须至少匹配一次α，这样A只能生成 Bα、Bαα 这类带α的串，直接漏掉了原文法中最基础的B（0个α）的情况。

而 A' → ε 这条规则，正好对应**“0次匹配α”**的场景：当B后面没有α的时候，A'直接匹配空串ε，让A最终等于B，完美覆盖原文法的所有可能生成的串。没有ε，改写后的文法就和原文法不等价了。

二、如何消除自上而下分析的无限递归？ #

自上而下分析是从起始符号出发，尝试展开产生式来匹配输入串，核心问题是不能让产生式展开陷入无限循环。

原文法的问题在于：当分析A的时候，第一个产生式是 A → A α，如果优先选择这条规则，就会陷入无限展开：A → Aα → Aαα → Aααα → ...，永远停不下来，根本没法去匹配输入的B或者α。

改写后的文法彻底解决了这个问题：

1. 分析A时，首先展开为 B A'，第一步是去分析B——这是一个没有左递归的选择，直接进入对B的匹配，不会无限递归。
2. 分析完B后，再处理A'：
   • 如果当前输入符号能匹配α，就选 A' → α A'：先匹配α，然后再递归分析A'（这时候是在α之后继续处理剩下的α，不是无限循环，因为每次都会消耗一个输入符号）。
   • 如果当前输入符号无法匹配α（说明B后面没有α了），就选 A' → ε：直接结束A'的分析，整个A的分析就完成了。

整个过程每一步都有明确的终止条件（要么匹配完所有α后选ε，要么中途匹配失败回溯），完全避免了原文法的无限递归问题。

举个实际匹配例子：

• 输入串是B：A→BA'，A'选ε，匹配完成。
• 输入串是Bα：A→BA'，A'→αA'，然后A'选ε，匹配完成。
• 输入串是Bαα：A→BA'，A'→αA'，A'→αA'，然后A'选ε，匹配完成。

内容的提问来源于stack exchange，提问作者Will Ponczak