实现解析器生成器时左因子消除后仍存回溯的LL(1)适配疑问

一、示例语法的LL(1)适配问题 #

问题背景 #

参考《Engineering a Compiler》实现解析器生成器时，对以下语法做左因子消除：

A -> B m | B n | m
B -> m

转换为：

A -> B A' | m
B -> m
A' -> m | n

但转换后A、B、A'的First集均包含m，不符合LL(1)要求，疑问是否语法本身无法无回溯解析，或是操作有误？

解答 #

这个语法本身确实无法适配LL(1)解析器，和你的左因子消除操作无关。原因如下：

• 原始语法中，当输入token为m时，LL(1)无法区分应该选择A -> m还是A -> B m：因为B的First集就是{m}，两个产生式的First集完全重叠。
• 左因子消除仅解决了相同前缀导致的回溯，但如果消除后不同产生式的First集仍重叠，且没有可推导出ε的产生式（无法用Follow集辅助判断），LL(1)就无法处理。此例中B A'不可能推导出ε（B必生成m，A'必生成m或n），Follow集也无法提供区分依据，因此必须使用LR(1)这类更强的解析器。

二、玩具语法中declaration与assignment的First集冲突问题 #

问题背景 #

按「消除ε产生式→消除左递归→左因子消除→计算First/Follow集」步骤处理玩具语法后，得到规则：

statement => alt=[ declaration | assignment | ret | Id ( statement_p0 ], first=[Id, return, ;], follow=[,, }]
statement_p0 => alts=[ args ) ; | ) ;], first=[), Int, Str, Id], follow=[,, }]

其中declaration和assignment共享Id作为首token，无法通过无回溯测试。

解答 #

这种冲突的核心是未彻底消除公共前缀，可以通过以下方式解决：

• 提取公共前缀：如果declaration和assignment的结构是类似Id : Type ;和Id = Expr ;这种，虽然首token都是Id，但后续token（: vs =）可区分，此时需要进一步做左因子消除，重构语法：

  statement => Id stmt_rest | ret | ...其他分支...
  stmt_rest => : Type ; | = Expr ;
  

  重构后，statement遇到Id就进入stmt_rest，再根据下一个token选择具体分支，即可解决First集重叠问题。
• 检查左因子消除是否彻底：LL(1)要求同一个非终结符的所有产生式First集两两不相交（若有ε产生式，其Follow集需与其他产生式First集无交集）。对于First集重叠的分支，必须持续提取公共前缀，直到各分支的First集无重叠为止。

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