Editing LR parser (section)

=== Conflicts in the constructed tables ===

The automaton is constructed in such a way that it is guaranteed to be deterministic. However, when reduce actions are added to the action table it can happen that the same cell is filled with a reduce action and a shift action (a ''shift-reduce conflict'') or with two different reduce actions (a ''reduce-reduce conflict''). However, it  can be shown that when this happens the grammar is not an LR(0) grammar. A classic real-world example of a shift-reduce conflict is the [[dangling else]] problem.

A small example of a non-LR(0) grammar with a shift-reduce conflict is:
: (1) E → 1 E
: (2) E → 1

One of the item sets found is:
: '''Item set 1'''
: E → 1 <big>{{color|#f7f|•}}</big> E
: E → 1 <big>{{color|#f7f|•}}</big>
: '''+''' E → <big>{{color|#f7f|•}}</big> 1 E
: '''+''' E → <big>{{color|#f7f|•}}</big> 1

There is a shift-reduce conflict in this item set: when constructing the action table according to the rules above,  the cell for  [item set 1, terminal '1'] contains '''s1''' (shift to state 1) '''and r2''' (reduce with grammar rule 2).

A small example of a non-LR(0) grammar with a reduce-reduce conflict is:
: (1) E → A 1
: (2) E → B 2
: (3) A → 1
: (4) B → 1

In this case the following item set is obtained:
: '''Item set 1'''
: A → 1 <big>{{color|#f7f|•}}</big>
: B → 1 <big>{{color|#f7f|•}}</big>

There is a reduce-reduce conflict in this item set because in the cells in the action table for this item set there will be both a reduce action for rule 3 and one for rule 4.

Both examples above can be solved by letting the parser use the follow set (see [[LL parser]]) of a nonterminal ''A'' to decide if it is going to use one of ''A''s rules for a reduction; it will only use the rule ''A'' → ''w'' for a reduction if the next symbol on the input stream is in the follow set of ''A''. This solution results in so-called [[Simple LR parser]]s.