如何消除无β产生式的文法左递归？以A→A*B等为例

首先明确：你给出的文法A -> A*B | A+CDE | Aab是无法生成任何合法终结符串的，因为所有产生式都是左递归形式——每次推导都只会把A替换成A加上某个后缀（*B、+CDE、ab），永远无法得到不含A的符号串，本质上这个文法定义的是空语言。

关于左递归消除的可行性 #

标准的直接左递归消除方法依赖于文法存在至少一个非左递归的基础产生式（也就是你例子里的A -> b这类β部分），作为推导的“入口”。如果没有这类产生式：

1. 形式上可以套用消除规则，但结果没有实际意义：

   • 按照消除逻辑，因为没有β产生式，所以A的产生式集合为空；
   • 辅助非终结符A'的产生式为：A' -> *BA' | +CDEA' | abA' | ε
     但此时起始符号A无法推导出任何串（没有对应的产生式），整个文法的语言仍然是空集。

2. 从实用角度看，这种文法本身是有缺陷的，需要补充至少一个非左递归的产生式（比如A -> b、A -> ε或者其他不以A开头的产生式），才能让文法定义出有意义的语言，此时才能进行有效的左递归消除。

内容的提问来源于stack exchange，提问作者Sakib Arifin