将上下文无关文法G转换为等价LL(1)文法遇阻，求解决方案

冲突原因分析 #

原文法中，非终结符Y的两个产生式Y -> ZS和Y -> epsilon在lookahead符号为b或c时产生冲突：

• FIRST(ZS) = {b, c}，因此b/c属于Y可选Y->ZS的触发符号
• FOLLOW(Y) = {$, ), b, c}，因此b/c也属于Y->epsilon的触发符号

这导致LL(1)分析表的[Y,b]和[Y,c]单元格出现多重入口，违反LL(1)文法要求。

修改后的LL(1)文法 #

通过拆分Y为两个非终结符，分别处理两种触发场景，消除冲突：

S -> a Y_opt | ( S ) Y_opt | u Y_opt | v Y_opt | z S Y_opt
Y_opt -> Y_eps | Y_zs
Y_eps -> epsilon
Y_zs -> Z S Y_opt
Z -> b S | c S

验证LL(1)条件 #

计算各非终结符的FIRST和FOLLOW集：

• FIRST(S) = {a, (, u, v, z}
• FIRST(Y_opt) = {ε, b, c}
• FIRST(Y_eps) = {ε}，FOLLOW(Y_eps) = {$, )}
• FIRST(Y_zs) = {b, c}，FOLLOW(Y_zs) = {$, ), b, c}
• FIRST(Z) = {b, c}，FOLLOW(Z) = {a, (, u, v, z}

分析表构造验证：

• 对于Y_eps，仅当lookahead为$或)时选择Y_eps->epsilon，无冲突
• 对于Y_zs，仅当lookahead为b或c时选择Y_zs->Z S Y_opt，无冲突
• 其他非终结符的产生式均满足LL(1)唯一选择要求

这样修改后的文法与原文法等价，且满足LL(1)文法的分析表无冲突条件。

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