parsingbisonyaccreduce-reduce-conflict

Resolving reduce-reduce conflict


Problem part of grammar:

expr_var: var_or_ID
| expr_var '[' expr ']'
| NEW expr_var '(' expr_listE ')'
| expr_var '(' expr_listE ')'
| expr_var ARROW expr_var
| expr_var ARROW '{' expr_var '}'
| expr_var DCOLON expr_var 
| expr_var DCOLON '{' expr_var '}'
| '(' expr_var ')'
;

Description of that problem:

expr_var  ->  NEW expr_var '(' expr_listE ')' .   (rule 87)
expr_var  ->  expr_var '(' expr_listE ')' .   (rule 88)

DCOLON  reduce using rule 87 (expr_var)
DCOLON  [reduce using rule 88 (expr_var)]
ARROW   reduce using rule 87 (expr_var)
ARROW   [reduce using rule 88 (expr_var)]
'['     reduce using rule 87 (expr_var)
'['     [reduce using rule 88 (expr_var)]
'('     reduce using rule 87 (expr_var)
'('     [reduce using rule 88 (expr_var)]
$default    reduce using rule 87 (expr_var)

Each operator(ARROW,DCOLON...) is left-associative. Operator NEW is non-associative.

How can i resolve that conflict?


Solution

  • The issue here is the ambiguity in:

    new foo(1)(2)
    

    This could be parsed in two ways:

    (new foo(1))(2) // call the new object
    new (foo(1))(2) // function returns class to construct
    

    Which (if either) of these is semantically feasible depends on your language. It is certainly conceivable that both are meaningful. The grammar does not provide any hints about the semantics.

    So it is necessary for you to decide which (if either) of these is the intended parse, and craft the grammar accordingly.

    Precedence declarations will not help because precedence is only used to resolve shift/reduce conflicts: a precedence relationship is always between a production and a lookahead token, never between two productions.

    Bison will resolve reduced/reduce conflicts in favour of the first production, as it has done in this case. So if the syntax is legal and unambiguous then you could select which parse is desired by reordering the productions if necessary. That will leave you with the warning, but you can suppress it with an %expect-rr declaration.

    You could also suppress one or the other parse (or both) by explicitly modifying the grammar to exclude new expressions from being the first argument in a call and/or exclude calls from being the first argument of a new, by means of an explicit subset of expr_var.