在CUP中修正歧义语法

Question

我有一个语法问题，我是用来做一个杯分析器。语法如下:在杯格式。

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 if = CExp in CExp 
      | fun id -> CExp 
      | Exp 
Exp  -> Exp op Exp 
      | Exp Exp 
      | {identifier} 
      | {integer literal} 
      | ( CExp ) 
op   -> + | - | * | / | < | ==

我的主要问题在于函数运算符Exp。“f4”指的是以值4作为参数的函数f。但是由于这个语法显然是模棱两可的(例如，对于输入"5 *f1“)，我试图使它明确无误。

我试图使它明确地在Exp Exp操作符之间迈出一步：

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)分析器，所以我也不能使用“看头”。如果有人能给我一个关于如何使这个语法不含糊的提示，我会很感激的。

Answer 1

这就是我想出的解决方案，我希望有人从中受益。这是相当简单的，我只需要解释联想，改变语法，使它明确，而不是依赖优先规则。

    /* ------------Declaration of Terminals and Non Terminals Section----------- */
   
//Terminals (tokens returned by the scanner).  
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, ter, plusExpr, multExpr, lessExpr, eqExpr , funcExpr;

precedence right EQ;
precedence right ARROW;

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(new ExprId(id), value, expression); :}
    | FUN ID:id ARROW cExpr:e
        {: RESULT = new ExprLambda(new ExprId(id), e); :}
    | plusExpr:e
        {:RESULT = e;:}
;
plusExpr ::=
    plusExpr:l PLUS multExpr:r
            {: RESULT = new ExprBinary(l, r, Operator.Plus); :}
    | plusExpr:l MINUS multExpr:r
            {: RESULT = new ExprBinary(l, r, Operator.Minus); :}
    | multExpr:t
            {: RESULT = t;:}
;

multExpr ::=
    multExpr:l TIMES lessExpr:r
            {: RESULT = new ExprBinary(l, r, Operator.Times); :}
    | multExpr:l DIV lessExpr:r
            {: RESULT = new ExprBinary(l, r, Operator.Div); :}
    | lessExpr:s
            {: RESULT = s;:}
;

lessExpr ::=
    lessExpr:l LESS eqExpr:r
            {: RESULT = new ExprBinary(l, r, Operator.Less); :}
    | eqExpr:u
            {: RESULT = u;:}
;

eqExpr ::=
    | eqExpr:l EQUALS funcExpr:r
            {: RESULT = new ExprBinary(l, r, Operator.Equals); :}
    | funcExpr:w
        {: RESULT = w;:}
;

funcExpr ::=
    funcExpr:exprFunc expr:arg
            {: RESULT = new ExprFuncApp(exprFunc, arg); :}
    | expr:e
        {:RESULT = e;:}
;

expr ::=
    ter:t
        {: RESULT = t ;:}
    | LPAREN cExpr:e RPAREN
         {: RESULT = e; :}
;

ter ::=
    NUMBER:n
        {: RESULT = new ExprNumber(n); :}
    | ID:i
        {: RESULT = new ExprId(i); :}
;