求助：修复CUP解析器中函数应用的语法歧义问题

算力阿峰

2026-8-13

解决CUP构建LR(0)解析器的函数应用语法歧义问题

问题核心

使用CUP构建LR(0)解析器时，函数应用规则Exp Exp（如f 4表示将4传入函数f）导致语法歧义。以输入5 * f 1为例，存在两种解析逻辑：

先执行乘法再函数应用：(5 * f) 1
先执行函数应用再乘法：5 * (f 1)
此前尝试引入中间非终结符rExpr并调整优先级规则，但未解决歧义，且因LR(0)解析器无法使用前瞻机制，需从文法结构本身入手修复。

原CUP语法

terminal           PLUS, MINUS, TIMES, DIV, EQUALS, LESS, IF, THEN, ELSE, LET, EQ, IN, FUN
                    , ARROW, LPAREN, RPAREN, INVALID_TOKEN, APPL;
terminal String   NUMBER, ID;
   
// Non terminals used in the grammar section.
//non terminal exprList;
non terminal Expr expr, cExpr;

precedence left LPAREN, RPAREN;
precedence left  PLUS, MINUS;
precedence left TIMES, DIV;
precedence left LESS;
precedence left EQUALS;
precedence right EQ;
precedence right ARROW;

start with cExpr;
/* ----------------------------Grammar Section-------------------- */
// to do: implement function application

cExpr ::=
    IF cExpr:ifExp THEN cExpr:thenExp ELSE cExpr:elseExp
        {: RESULT = new ExprIfThenElse(ifExp, thenExp, elseExp); :}
    | LET ID:id EQ cExpr:value IN cExpr:expression
        {: RESULT = new ExprLetIn(id, value, expression); :}
    | FUN ID:id ARROW cExpr:e
        {: RESULT = new ExprLambda(id, e); :}
    | rExpr:e
        {:RESULT = e;:}
;

expr ::=
    expr:l PLUS expr:r
        {: RESULT = new ExprBinary(l, r, Operator.Plus); :}
    | expr:l TIMES expr:r
        {: RESULT = new ExprBinary(l, r, Operator.Times); :}
    | expr:l DIV expr:r
        {: RESULT = new ExprBinary(l, r, Operator.Div); :}
    | expr:l MINUS expr:r
        {: RESULT = new ExprBinary(l, r, Operator.Minus); :}
    | expr:l LESS expr:r
        {: RESULT = new ExprBinary(l, r, Operator.Less); :}
    | expr:l EQUALS expr:r
        {: RESULT = new ExprBinary(l, r, Operator.Equals); :}
    |expr:exprFunc expr:arg
        {: RESULT = new ExprFuncApp(exprFunc, arg); :}
    | NUMBER:n
        {: RESULT = new ExprNumber(n); :}
    | ID:i
        {: RESULT = new ExprId(i); :}
    | LPAREN cExpr:e RPAREN
         {: RESULT = e; :}
;

语法文本表示

CExp -> if CExp then CExp else CExp 
      | let id = CExp in CExp 
      | fun id -> CExp 
      | Exp 
Exp  -> Exp op Exp 
      | Exp Exp 
      | {identifier} 
      | {integer literal} 
      | ( CExp ) 
op   -> + | - | * | / | < | ==

修改后的尝试版本

terminal           PLUS, MINUS, TIMES, DIV, EQUALS, LESS, IF, THEN, ELSE, LET, EQ, IN, FUN
                    , ARROW, LPAREN, RPAREN, INVALID_TOKEN, APPL;
terminal String   NUMBER, ID;
   
// Non terminals used in the grammar section.
//non terminal exprList;
non terminal Expr expr, cExpr,rExpr;


precedence left LPAREN, RPAREN;
precedence left  PLUS, MINUS;
precedence left TIMES, DIV;
precedence left LESS;
precedence left EQUALS;
precedence right EQ;
precedence right ARROW;
precedence left APPL;

start with cExpr;
/* ----------------------------Grammar Section-------------------- */
// to do: implement function application

cExpr ::=
    IF cExpr:ifExp THEN cExpr:thenExp ELSE cExpr:elseExp
        {: RESULT = new ExprIfThenElse(ifExp, thenExp, elseExp); :}
    | LET ID:id EQ cExpr:value IN cExpr:expression
        {: RESULT = new ExprLetIn(id, value, expression); :}
    | FUN ID:id ARROW cExpr:e
        {: RESULT = new ExprLambda(id, e); :}
    | rExpr:e
        {:RESULT = e;:}
;

expr ::=
    expr:l PLUS rExpr:r
        {: RESULT = new ExprBinary(l, r, Operator.Plus); :}
    | expr:l TIMES rExpr:r
        {: RESULT = new ExprBinary(l, r, Operator.Times); :}
    | expr:l DIV rExpr:r
        {: RESULT = new ExprBinary(l, r, Operator.Div); :}
    | expr:l MINUS rExpr:r
        {: RESULT = new ExprBinary(l, r, Operator.Minus); :}
    | expr:l LESS rExpr:r
        {: RESULT = new ExprBinary(l, r, Operator.Less); :}
    | expr:l EQUALS rExpr:r
        {: RESULT = new ExprBinary(l, r, Operator.Equals); :}
    | NUMBER:n
        {: RESULT = new ExprNumber(n); :}
    | ID:i
        {: RESULT = new ExprId(i); :}
    | LPAREN cExpr:e RPAREN
         {: RESULT = e; :}
;
rExpr ::=
    expr:e
        {:RESULT = e;:}
    |rExpr:exprFunc expr:arg
        {: RESULT = new ExprFuncApp(exprFunc, arg); :} %prec APPL
;

可行解决方案

由于LR(0)解析器无法依赖前瞻或优先级规则解决冲突，必须通过层级化非终结符重构文法，从结构上强制运算顺序，消除歧义。核心思路是按优先级从高到低划分表达式层级：
函数应用 > 乘除运算 > 加减运算 > 关系运算

最终CUP语法实现

terminal           PLUS, MINUS, TIMES, DIV, EQUALS, LESS, IF, THEN, ELSE, LET, EQ, IN, FUN
                    , ARROW, LPAREN, RPAREN, INVALID_TOKEN;
terminal String   NUMBER, ID;
   
non terminal Expr cExpr, expr, addExpr, mulExpr, appExpr, primaryExpr;

start with cExpr;

/* ----------------------------Grammar Section-------------------- */
cExpr ::=
    IF cExpr:ifExp THEN cExpr:thenExp ELSE cExpr:elseExp
        {: RESULT = new ExprIfThenElse(ifExp, thenExp, elseExp); :}
    | LET ID:id EQ cExpr:value IN cExpr:expression
        {: RESULT = new ExprLetIn(id, value, expression); :}
    | FUN ID:id ARROW cExpr:e
        {: RESULT = new ExprLambda(id, e); :}
    | expr:e
        {: RESULT = e; :}
;

// 关系表达式：优先级最低（<、==）
expr ::=
    addExpr:e
        {: RESULT = e; :}
    | expr:l LESS addExpr:r
        {: RESULT = new ExprBinary(l, r, Operator.Less); :}
    | expr:l EQUALS addExpr:r
        {: RESULT = new ExprBinary(l, r, Operator.Equals); :}
;

// 加减表达式：优先级高于关系运算
addExpr ::=
    mulExpr:e
        {: RESULT = e; :}
    | addExpr:l PLUS mulExpr:r
        {: RESULT = new ExprBinary(l, r, Operator.Plus); :}
    | addExpr:l MINUS mulExpr:r
        {: RESULT = new ExprBinary(l, r, Operator.Minus); :}
;

// 乘除表达式：优先级高于加减运算
mulExpr ::=
    appExpr:e
        {: RESULT = e; :}
    | mulExpr:l TIMES appExpr:r
        {: RESULT = new ExprBinary(l, r, Operator.Times); :}
    | mulExpr:l DIV appExpr:r
        {: RESULT = new ExprBinary(l, r, Operator.Div); :}
;

// 函数应用表达式：优先级最高，左结合
appExpr ::=
    primaryExpr:e
        {: RESULT = e; :}
    | appExpr:func primaryExpr:arg
        {: RESULT = new ExprFuncApp(func, arg); :}
;

// 原子表达式：不可拆分的最小单元
primaryExpr ::=
    NUMBER:n
        {: RESULT = new ExprNumber(n); :}
    | ID:i
        {: RESULT = new ExprId(i); :}
    | LPAREN cExpr:e RPAREN
        {: RESULT = e; :}
;

方案说明

层级化结构消除歧义：每个层级的表达式只能引用更高优先级的表达式作为操作数，确保函数应用总是先于乘除、加减等运算执行，比如5 * f 1会被强制解析为5 * (f 1)，符合预期语义。
适配LR(0)要求：文法无任何移进/归约冲突，每个状态下的动作唯一，不需要依赖前瞻或优先级规则即可正确解析。
符合函数式语言习惯：函数应用采用左结合规则，f a b会被解析为(f a) b，与Haskell、OCaml等语言的行为一致。

内容的提问来源于stack exchange，提问作者Gabriel Sánchez

求助：修复CUP解析器中函数应用的语法歧义问题

问题核心 #

原CUP语法 #

语法文本表示 #

修改后的尝试版本 #

可行解决方案 #

最终CUP语法实现 #

方案说明 #