修复CUP中的歧义语法

Question

我有一个我用来做CUP解析器的语法问题。语法如下: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 if = CExp in CExp 
| fun id -> CExp 
| Exp 
Exp  -> Exp op Exp 
| Exp Exp 
| {identifier} 
| {integer literal} 
| ( CExp ) 
op   -> + | - | * | / | < | ==

我的主要问题在于函数操作符Exp Exp "f "就像函数f的参数值是4。但是由于这个语法显然是模棱两可的(例如对于输入"5 * f 1")，我试图使它明确。

我试图使它明确，用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
;

我希望这样可以使它明确，但事实并非如此…
我试着用我的手去尝试CUP的优先规则，但我也没有得到任何地方它是一个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); :}
;