[Caml-list] Priority issue in an ocamlyacc grammar

[Caml-list] Priority issue in an ocamlyacc grammar

[David MENTRE]

Hello,

I'm trying to parse a logic language. In this language, I have
operators like '&' (AND), 'or' (OR) and '=' (EQUAL).

I have defined in my parser.mly file the following priorities:
"""
/* 30 */
%left IMPLY
/* 40 */
%left AND OR
/* 60 */
%left EQUAL
/* 115 */
%left COMMA
/* 120 */
%left COLUMN
/* 160 */
%left UNION MAPLET
/* 170 */
%left DOTDOT
/* 190 */
%left STAR
/* 220 */
%left DOT
"""

So, if I read the ocamlyacc manual correctly the EQUAL operator
(priority 60) should have higher priority than OR or AND operators
(priority 40).

Then, I define in my grammar a rule to parse an expression (exp):
"""
exp: LPAREN exp RPAREN { $2 }
| INT MAPLET IDENTIFIER %prec MAPLET { Enum_value($1, $3) }
| NOT LPAREN exp RPAREN { Not($3) }
| exp SPACES EQUAL SPACES exp %prec EQUAL { Equal($1, $5) }
| exp SPACES AND SPACES exp %prec AND { And($1, $5) }
| exp SPACES OR SPACES exp %prec OR { Or($1, $5) }
| exp SPACES IMPLY SPACES exp %prec IMPLY { Imply($1, $5) }
| exp SPACES EQUALEQUAL SPACES exp { Equalequal($1, $5) }
| exp UNION exp { Union($1, $3) }
| exp STAR exp { Star($1, $3) }
| exp COLUMN SPACES exp %prec COLUMN { In($1, $4) }
| exp COMMA exp { Goal($1, $3) }
| FIN LPAREN exp RPAREN { Fin($3) }
| POVERSION { POVersion($1) }
| UNDERSCORE_F { F($1) }
| GOAL_NAME { match $1 with a, b -> Goal_name(a, b) }
| COMMENT { Comment($1) }
| LBRACKET RBRACKET { Empty_set }
| enumerated_set { Enumerated_set($1) }
| LPAREN INT DOTDOT INT RPAREN %prec DOTDOT { Interval($2, $4) }
| IDENTIFIER { Identifier($1) }
;
"""

As far as I have correctly read the manual, I define the correct
precedence for each rule, e.g. rule parsing the AND operator have the
precedence of it. So far so good.

However, after parsing, I have the following kind of tree:
"""
  1|->POSITION: {m1}\/{m2}\/{m3}
  & not(2|->POSITION = m1) & not(2|->POSITION = m2) & not(2|->POSITION = m3)
    & 3|->POSITION
      = 1|->POSITION
        or 2|->POSITION: {m1}\/{m2}\/{m3}
           & not(1|->POSITION = m1)
             & not(1|->POSITION = m2) & not(1|->POSITION = m3)
             & 3|->POSITION = 2|->POSITION
           or 1|->POSITION: {m1}\/{m2}\/{m3}
              => 2|->POSITION: {m1}\/{m2}\/{m3}
              & 2|->POSITION: {m1}\/{m2}\/{m3}
                => 1|->POSITION: {m1}\/{m2}\/{m3}
"""

It appears that the OR operator binds more tightly than the EQUAL operator!

I should have:
"""
& 3|->POSITION = 1|->POSITION
or 2|->POSITION: {m1}\/{m2}\/{m3}
...
"""

Could somebody explain to me the point I'm missing? I'm using OCaml
3.10.2 if it has any relevance.

Sincerely yours,
david

[Caml-list] Re: Priority issue in an ocamlyacc grammar

[David MENTRE]

Hello,

2011/2/11 David MENTRE <dmentre@linux-france.org>:
> Then, I define in my grammar a rule to parse an expression (exp):
> """
> exp: LPAREN exp RPAREN { $2 }
> | INT MAPLET IDENTIFIER %prec MAPLET { Enum_value($1, $3) }
> | NOT LPAREN exp RPAREN { Not($3) }
> | exp SPACES EQUAL SPACES exp %prec EQUAL { Equal($1, $5) }
> | exp SPACES AND SPACES exp %prec AND { And($1, $5) }
> | exp SPACES OR SPACES exp %prec OR { Or($1, $5) }
> | exp SPACES IMPLY SPACES exp %prec IMPLY { Imply($1, $5) }
> | exp SPACES EQUALEQUAL SPACES exp { Equalequal($1, $5) }
...
> """
...
> It appears that the OR operator binds more tightly than the EQUAL operator!

I've found it: the SPACES token did not allow to chose the correct
rule while parsing. Removing it brings a correct parsed tree.

Regards,
david