Search code examples
c++parsingyacclex

How to solve Ambiguity and Conflicts LR parser?


I learned LR parser conflict when (shift vs reduce) and (reduce vs reduce). if (shift vs reduce) conflict, conduct shift. if (reduce vs reduce) conflict, conduct first production rule.

why that?? why select shift and first production rule??


Solution

  • Easy one first: reduce-reduce conflicts are usually bad. Parser generators that let you get away with it employ a consistent rule like "take the first one" so that you can choose which one you want by reordering the rules in your grammar.

    Shift-reduce conflicts are actually pretty common. The parser generator will select the shift in these cases, because it's almost always what you want. The classic example is a sentence like:

    if (A) if (B) C else D;
    

    In an LR grammar that allows this, there is usually a shift-reduce conflict on the "else", and its ambiguous which "if" it applies to. Selecting the shift means that it applies to the "if(B)", which is usually the rule in languages that allow this sort of thing.