ANTLR语法解析异常：Lambda表达式体与加法运算匹配错误

我懂你碰到的这个糟心问题——明明想让fun x -> x + 1被解析成fun x -> (x + 1)，结果ANTLR愣是把它拆成了(fun x -> x) + 1。这背后的核心原因是原语法的规则顺序和优先级分层不合理，导致加法运算的优先级意外盖过了Lambda表达式。

为什么原语法会出错？ #

在你的原语法里，所有表达式都挤在同一个expression规则中，而且加法这类二元运算（AdditionExpr）是左递归规则，还放在了LambdaExpr的后面。ANTLR的规则匹配逻辑是：同一规则中，左递归的二元运算优先级更高，并且会优先结合左边的表达式。所以当解析fun x -> x + 1时，ANTLR会先把fun x -> x识别成一个完整的Lambda表达式，然后把后面的+ 1和这个Lambda组合成加法运算，完全忽略了x + 1应该是Lambda的body。

修复方案：分层表达式优先级 #

要解决这个问题，我们需要按照编程语言的常规优先级，把表达式拆分成不同层级的规则，让Lambda表达式拥有最高优先级，这样它的body就能包含所有低优先级的运算（比如加法）。以下是调整后的语法：

// 最低优先级：控制流表达式（let、if）
expression : letExpr | ifExpr | equalityExpr;

// 相等运算（==）
equalityExpr : booleanExpr (EQ booleanExpr)*;

// 布尔运算（&&、||）
booleanExpr : additiveExpr (AND additiveExpr | OR additiveExpr)*;

// 加减运算
additiveExpr : multiplicativeExpr (ADD multiplicativeExpr | SUB multiplicativeExpr)*;

// 乘除运算
multiplicativeExpr : callExpr (MUL callExpr | DIV callExpr)*;

// 函数调用（优先级高于二元运算）
callExpr : primaryExpr (primaryExpr)+;

// 最高优先级：原子表达式
primaryExpr : number # NumberExpr
            | bool # BooleanExpr
            | 'fun' args=ID+ '->' body=expression # LambdaExpr
            | name=ID # VarExpr
            | '(' inner=expression ')' # ParensExpr;

// Let表达式规则
letExpr : 'let' name=ID '=' value=expression 'in' body=expression # LetExpr;

// If-Else表达式规则
ifExpr : 'if' test=expression 'then' then=expression 'else' else_=expression # IfThenElseExpr;

// 词法规则示例
ID : [a-zA-Z_][a-zA-Z0-9_]*;
number : INT | FLOAT;
INT : [0-9]+;
FLOAT : [0-9]+ '.' [0-9]+;
bool : 'true' | 'false';
ADD : '+';
SUB : '-';
MUL : '*';
DIV : '/';
AND : '&&';
OR : '||';
EQ : '==';
WS : [ \t\n\r]+ -> skip;

调整后的关键变化 #

1. 分层优先级：从高到低依次是：原子表达式（Lambda、数字、变量等）→ 函数调用 → 乘除 → 加减 → 布尔运算 → 相等运算 → 控制流（let、if）。这样Lambda的优先级最高，它的body可以引用任何低优先级的表达式。
2. Lambda归为原子表达式：把LambdaExpr放到primaryExpr里，确保它会被优先完整匹配，不会被后面的二元运算拆分。
3. 修正函数调用的优先级：让调用基于原子表达式，这样f x + y会被解析成(f x) + y，符合常规函数式语言的语义。

现在再解析fun x -> x + 1时，ANTLR会先识别fun x ->，然后把x + 1（通过expression规则匹配到完整的加法运算）作为Lambda的body，完全符合你的预期。

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