如何移除同时存在左递归与右递归的文法中的左递归？

首先明确原文法：

E->a
E->E+E
E->S,E
E->(E)

S-> bS'
S'-> ;bS'
S'->ε

1. 识别直接左递归 #

E的产生式中，E->E+E是直接左递归，其余E的产生式（E->a、E->S,E、E->(E)）属于无左递归的基础候选式。S和S'的产生式本身没有左递归，无需修改。

2. 应用直接左递归消除规则 #

对于形如 A->Aα | β 的直接左递归，转化规则为：

• A->βA'
• A'->αA' | ε

对应到E的产生式：

• 基础候选式β：a、(E)、S,E
• 左递归部分的α：+E

因此改写后的E及新增的E'产生式为：

E->aE'
E->(E)E'
E->S,E E'
E'->+E E'
E'->ε

3. 最终无左递归文法 #

整合后完整的无左递归文法如下：

E->aE'
E->(E)E'
E->S,E E'
E'->+E E'
E'->ε

S->bS'
S'->;bS'
S'->ε

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