函数式语言文法转LL(1)遇冲突：函数应用产生式如何处理？

问题根源分析 #

你把函数应用和二元运算符放在同一个扩展非终结符exp'中，同时在let/if的产生式后多余添加了exp'，导致文法出现冗余，进而引发first/follow冲突。核心遗漏点是未通过文法分层明确函数应用与二元运算符的优先级——函数式语言中函数应用的优先级通常高于所有二元运算符，且函数应用是左结合（如f a b等价于(f a) b），这是构造LL(1)文法的关键前提。

修正后的LL(1)文法 #

prg           -> defs
defs          -> def defs'
defs'         -> ; def defs' | ε
def           -> vars = exp
vars          -> var vars'
vars'         -> var vars' | ε
loc_defs      -> loc_def loc_defs'
loc_defs'     -> ; loc_def loc_defs' | ε
loc_def       -> var = exp
exp           -> exp_binop
exp_binop     -> exp_app exp_binop'
exp_binop'    -> binop exp_app exp_binop' | ε  # 二元运算，左结合转右递归
exp_app       -> exp_factor exp_app'
exp_app'      -> exp_factor exp_app' | ε       # 函数应用，左结合转右递归
exp_factor    -> let loc_defs in exp
               | if exp then exp else exp
               | unop exp_factor
               | atom
binop         -> and | or | == | < | + | - | * | /
unop          -> not | neg
atom          -> var | num | bool

关键设计说明 #

1. 分层消除优先级歧义

   • exp_factor：处理最高优先级结构，包括原子表达式、一元运算、let表达式、if表达式，这些结构可直接作为函数应用的参数或被一元运算符修饰。
   • exp_app：处理函数应用，通过exp_app'实现左结合的右递归转换，确保其优先级高于二元运算。
   • exp_binop：处理二元运算符，通过exp_binop'实现左结合的右递归转换，优先级低于函数应用。

2. LL(1)条件验证

   • 所有非终结符的产生式first集两两无交集：
     • defs'/vars'/loc_defs'的first集仅包含;，与ε的first集无交集。
     • exp_binop'的first集为二元运算符集合，与ε的first集无交集，且follow集（;、in、then、else、EOF）与first集无重叠。
     • exp_app'的first集为exp_factor的first集（let、if、not、neg、var、num、bool），follow集为二元运算符集合+exp_binop的follow集，两者无交集。
   • 所有nullable产生式的first集与对应非终结符的follow集无重叠，完全满足LL(1)无冲突要求。

3. 冗余修正
   移除原文法中let/if产生式后多余的exp'，因为exp本身已包含完整的表达式扩展逻辑，避免了重复解析导致的冲突。

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