Solution in shift/reduce conflict at bison grammar

Question

I'm trying to write a parser for tiny Visual Basic language. And I can't resolve next shift/reduce conflict. I have these rules:

simple_type_name:
    qualified_type_name
    | primitive_type_name;

qualified_type_name:
    ID
    | qualified_type_name PERIOD ID;

primitive_type_name: BOOLEAN|CHAR|STRING|BYTE|SBYTE|USHORT|SHORT|UINTEGER|INTEGER|ULONG|LONG|SINGLE|DOUBLE;

Bison says me:

simple_type_name  ->  qualified_type_name .   (rule 20)
qualified_type_name  ->  qualified_type_name . PERIOD ID   (rule 23)

PERIOD  shift, and go to state 41

PERIOD  [reduce using rule 20 (simple_type_name)]
$default reduce using rule 20 (simple_type_name)

So, what is the right solution in this conflict?

Do you reference qualified_type_name anywhere else in your grammar? — Josh
You need to show where simple_type_name is referenced in the grammar as that's the source of the problematic reduction that causes the conflict. — Chris Dodd

Chris Dodd Chris Dodd · Accepted Answer · 2013-12-03T17:27:32

You must have some other rule in the grammar where simple_type_name is followed by a PERIOD. Something like:

expression: simple_type_name PERIOD expression

perhaps?

The problem is that it needs more lookahead to determine if what comes after the PERIOD is a simple ID that makes this a qualified type name or something else that would make it a simple type name.

One possible solution (impossible to tell, as you don't show enough of your grammar) is to unfactor simple_type_name where it is followed by a period -- duplicate the rule, replacing simple_type_name with both qualified_type_name and primitive_type_name. With the above expression example, that would be:

expression: qualified_type_name PERIOD expression
          | primitive_type_name PERIOD expression

Depending on the rest of your grammar it might be necessary or desirable to completely unfactor simple_type_name, replacing all mentions of it with duplicated rules and deleting the simple_type_name rule itself

edit

Ok, you've linked more of your grammar, so we can see that the problematic use of simple_type_name is in a trailing context (at the end of the rhs of a rule), so simple unfactoring is not enough. You may be able to fix it by repeated unfactoring (unfactor simple_type_name as described above, then unfactor simple_expression and/or type_name as well). The goal is to push the unfactoring to a rule that has

    ... some-nonterminal PERIOD ...

on the right side, and replace that with rules

    ... other-nonterminal PERIOD ... | ... qualified_type_name PERIOD ...

where other-nonterminal is a duplicate of some-nonterminal with the rules that lead to a single qualified_type_name removed.

Unfortunately this can easily lead to an exponential blowup in the size of the grammar, so may be impractical. In that case the only option may be to use a more powerful parsing method, such as bison's %glr-parser option or backtracking with btyacc.

Solution in shift/reduce conflict at bison grammar

1 Answers