Search code examples
compiler-constructiondfalr-grammar

Why does a LR(1) DFA doesn't have a Shift/Reduce conflict?

Given this grammar: enter image description here

For the LR(0) DFA I can clearly see why this is a Shift/Reduce conflict:

enter image description here

(partial DFA)

But I can't understand why the LR(1) DFA solves the problem?

enter image description here (partial DFA)

For me this is still a shift reduce conflict since the lookahead symbol is exactly the same for the B rule? How should the LR(1) parser distinguish them, but not the LR(0) one?

Solution

  • Because you can only reduce B→ε if the lookahead is a.

    In LR(0) you cannot take lookahead into account, but in LR(1) you can decide based on the next input symbol, and here the rule is simple: if the next symbol is b, shift it, and if it is a, do the epsilon reduction of B.