上下文无关文法：带左递归的非终结符B如何消除λ产生式？

前置判断：确定可空非终结符 #

首先识别所有可推导出λ的非终结符：

• A：存在直接产生式A -> λ，可空
• C：存在产生式C -> A，A可空因此C可空
• B：存在直接产生式B -> λ，且可推导到可空的C，可空
• S：存在产生式S -> B，B可空因此S可空

消除B的λ产生式操作 #

基础操作（仅移除B直接的λ产生式，保留其他非终结符的λ推导能力） #

如果只要求删除B的直接B->λ规则，不需要切断B到λ的所有间接路径，按如下规则改写：

1. 移除B -> λ产生式
2. 对B的其他产生式右部，生成所有省略任意数量可空B的变体，排除全空的变体：
   • 原B -> BB的合法变体：BB | B（两个B全删的变体为λ，直接排除）
   • 原B -> C无B符号，直接保留
3. 删去无用的单位产生式B -> B，得到B的新规则：B -> BB | C
4. 如果原文法需要保留空串的推导能力，给起始符S补充产生式S -> λ即可，不会引入B的λ推导。

进阶操作（彻底避免B的任何推导路径出现λ） #

如果要求B的所有推导路径都不能生成λ，需要同步消除A、C的λ产生式，切断间接空推导路径：

1. 处理A的产生式：
   • 移除A -> λ
   • 改写A -> aAb，补充省略A的变体ab，得到新规则：A -> aAb | ab
2. 处理C的产生式：
   现在A已经无法推导λ，C不存在空推导路径，因此原有C -> A | aCc规则可以直接保留，此时C的所有推导结果长度都≥2，不存在λ。
3. 处理B的产生式：
   移除B -> λ，改写B -> BB的非空变体后删除无用的单位产生式，最终B的规则为B -> BB | C，此时B的所有推导路径最终都会落到C，不可能生成λ，彻底避免了递归出现λ的问题。
4. 同样如果需要保留原语言的空串，仅给起始符S补充S -> λ即可。

最终文法示例（彻底消除B的λ推导版本） #

S -> B | λ
A -> aAb | ab
B -> BB | C
C -> A | aCc

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