无公共前缀文法的左因子化可行性咨询及左递归消除验证

我们逐个分析原文法和消除左递归后文法的非终结符候选式：

原文法分析 #

原文法的产生式如下：

R -> R + T | T
T -> T F | F
F -> F * | P
P -> a | b

• 非终结符R的两个候选式R+T和T没有公共前缀；
• 非终结符T的两个候选式T F和F没有公共前缀；
• 非终结符F的两个候选式F *和P没有公共前缀；
• 非终结符P的两个候选式a和b没有公共前缀。

所有非终结符的候选式均无公共前缀，因此原文法确实无法进行左因子化。

消除左递归后的文法分析 #

消除左递归后的产生式如下：

R  -> T R'
R' -> + T R' | ε
T  -> F T'
T' -> F T' | ε
F  -> P F'
F' -> * F' | ε
P  -> a | b

• R、T、F都只有单个候选式，不存在需要左因子化的场景；
• R'的候选式+T R'和ε前缀分别为+和空串，无公共前缀；
• T'的候选式F T'和ε前缀分别为F和空串，无公共前缀；
• F'的候选式* F'和ε前缀分别为*和空串，无公共前缀；
• P的候选式a和b仍无公共前缀。

因此消除左递归后的文法同样无法进行左因子化，你的理解完全正确。

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