I am having problems with a grammer I am using to make a CUP Parser. The grammer is as follows: In CUP format.
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; :}
;
Or written out:
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 -> + | - | * | / | < | ==
My main problem resides with the function operator Exp Exp. "f 4" would mean something like function f with value 4 as argument. But as this grammer is obviously ambiguous (for example for the input "5 * f 1") i tried to make it unambiguous.
I tried to make it unambiguous was making a step inbetween with the Exp Exp operator:
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
;
This way i hoped it would make it unambigous, which is not the case...
I tried my hand on trying with precedence rules of CUP but I also did not get anywhere with that.\
It is a LR(0) Parser, so i also couldn't use look aheads.
If someone could give me a tip on how to make this grammer unambiguous i would appreciate it.
This is the solution i came up with, I hope someone benefits from it. It is pretty simple and i only needed to account for associativity and change the grammer to make it unambiguous, instead of relying on precedence rules.