能力倾向|门CS 1998 |问题61

考虑语法

S →  Aa | b
A → Ac | Sd | ε

构造一个没有左递归且产生式规则数最少的等价文法。 答复: 说明： 鉴于

S →  Aa | b
A → Ac | Sd | ε 

我们可以把这个语法写成-

S →  Aa | b
A → Ac | Aad | bd | ε 

去除左因子后，我们得到：-

S → Aa | b
A → A’ | bdA’
A’ → cA’ | adA’ |  ε 

这个问题的小测验