Search code examples
parsingbisonreduce-reduce-conflict

Why doesn't this grammar have a reduce/reduce conflict?

Consider the following (admittedly nonsensical - it has been vastly simplified to illustrate the point) grammar:

negationExpression
    : TOK_MINUS constantExpression %prec UNARYOP
    | testRule
    ;

constantExpression
    : TOK_INTEGER_CONSTANT
    | TOK_FLOAT_CONSTANT
    ;

testRule
    : negationExpression constantExpression  // call this Rule 1
    | constantExpression   // Rule 2
    ;

Bison does not complain about a reduce/reduce conflict when ran on this grammar, but to me it seems like there is one. Assume we have parsed a negationExpression and a constantExpression; to me it seems there are two things the parser could now do, based on the above definition:

  1. Reduce the sequence into a testRule using Rule 1 above
  2. Reduce the constantExpression into a testRule using Rule 2 above (the negationExpression would be left untouched in this case, so the parse stack would look like this: negationExpression testRule)

However no warnings are emitted, and when I look at the .output file Bison generates, it seems there is no ambiguity whatsoever:

state 5

    6 testRule: constantExpression .

    $default  reduce using rule 6 (testRule)
...
state 9

    5 testRule: negationExpression constantExpression .

    $default  reduce using rule 5 (testRule)

According to the Bison docs:

A reduce/reduce conflict occurs if there are two or more rules that apply to the same sequence of input.

Isn't this precisely the case here?

Solution

  • No, it doesn't apply here.

    "Sequence of input" is an unfortunate phrasing; what is meant is really "same input", or possibly more explicitly, "same prefix subsequence of a valid input". In other words, if there are two or more rules which could apply to the entire input, up to the current read point (and taking into account the lookahead).

    In your grammar, testRule never follows anything. It (and negationExpression ) can only be reduced at the very beginning of some derivation. So if the (partially-reduced) input ends with negationExpression constantExpression, it is impossible to reduce constantExpression to testRule because no derivation of the start symbol can include testRule at a non-initial position.