如何在Antlr中实现Haskell风格的左结合函数应用语法解析

问题原因 #

你当前的文法存在两个核心问题：

• 所有表达式规则平级放在expression下，没有按优先级拆分层级，ANTLR4对直接左递归规则的优先级按规则顺序从上到下递减，你把函数应用规则放在了中缀运算符规则之后，优先级设置不符合函数应用优先级高于中缀运算符的通用逻辑。
• 平级的expression (expression)+写法虽然是直接左递归，但ANTLR4对这种右部是多表达式的规则，会优先归约右部的表达式，最终表现为右结合，自然就会把f a b解析为f (a b)。
  你尝试的expression+ expression写法本质和原写法等价，且会触发左递归检测报错，自然无法运行。

解决方案 #

你需要按优先级拆分表达式规则，把优先级最高的原子表达式、左结合的函数应用、优先级更低的中缀运算符分成不同层级：

1. 首先定义优先级最高的atom规则，包含所有不可拆分的原子表达式：

atom :
      unit #UnitExpression
    | IntegerLiteral #IntExpression
    | FloatLiteral #FloatExpression
    | CharLiteral #CharExpression
    | StringLiteral #StringExpression
    | LSquareParen (expression (Comma expression)*)? RSquareParen #ListExpression
    | LParen expression RParen #ParenExpression
    | LParen (expression (Comma expression)+) RParen #TupleExpression
    | variableIdentifier #VariableExpression
;

2. 定义函数应用层application，用左递归规则保证左结合，优先级低于原子表达式、高于中缀运算符：

application :
      application atom #FunctionApplicationExpression
    | atom #AtomicExpression
;

3. 最上层的expression规则只保留中缀运算符相关逻辑：

expression :
      expression operatorIdentifier expression #OperatorApplicationExpression
    | application #ApplicationExpression
;

如果你的中缀运算符有不同的优先级和结合性要求，可以给对应运算符添加<assoc=left>/<assoc=right>标注，或者继续拆分expression为更多层级，只要保证函数应用层的优先级高于所有中缀运算符即可。

效果验证 #

修改后：

• f a b会被解析为((f a) b)，符合左结合要求。
• 函数应用的右项只能是单个原子表达式，不存在把多个字面量先归约为函数应用再作为右项的可能，f "a" "b"不会再被错误解析为f ("a" "b")，完全符合你对字面量优先级的预期。

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