消除文法左递归：以G2为例

消除文法左递归：以G2为例

已知上下文无关文法G2 (E为开始符号):

G2: E→ET+|T      T→TF*|F     F→(E)|i

消除左递归的步骤如下：

1. 提取公共左因子

G2: E → TG T → FH F → i | (E) H → *FH | ε G → +TG | ε

2. 消除直接左递归

G2: E → TG T → FH F → i | (E) H → *FH H' | ε H' → *FH H' | ε G → +TG G' | ε G' → +TG G' | ε

改写后的文法产生式如下：

E → TG T → FH F → iF' | (E) F' → ε | )F' H → *FH H' | ε H' → *FH H' | ε G → +TG G' | ε G' → +TG G' | ε