Parsing notes: "Shift-reduce" and "Reduce-reduce" conflicts in LR parsing

sr-rr-confilct.md

"Shift-reduce" and "Reduce-reduce" conflicts in LR parsing.

How to determine?

A full parsing table is not needed, only the canonical collection. In the canonical collection, find all final items (and only final items), and see if:

• There are both shift and reduce in the same item ("shift-reduce", s/r)
• There are two reduce actions in the same item ("reduce-reduce", r/r)

If none of these is true, there are no conflicts, even in LR(0). If there are some of the above, SLR(1) still may solve it.

LR(0):

• Puts reduce in an entire row, for every terminal
• If some column in the action part (a terminal) contains both, shift and reduce moves, it's a "shift-reduce" (s/r) conflict.

I5:

A -> b •
X -> X • a

Here we have transition on "a", and reduce by A -> b.

• If a state contains two reduce items, it's a "reduce-reduce" (r/r) conflict:

I5:

A -> a •
B -> b •

SLR(1):

To avoid some s/r and r/r conflicts, SLR(1) maintains Follow(LHS):

I5:

A -> b •
X -> X • a

• It's a s/r conflict if and only if transition symbol is in the Follow of LHS to reduce move. I.e.

Follow(A) = {"a", ...}, then it's a conflict. Otherwise, reduce won't be put in the "a" column (only shift is there), and it's not a conflict.

A -> a •
B -> b •

• It's an r/r conflict only if Follow(A) and Follow(B) sets intersect, otherwise it's not a conflict.

Follow(A) ∩ Follow(B) ≠ ø // conflict