Skip to content

Instantly share code, notes, and snippets.

@DmitrySoshnikov
Last active May 13, 2024 13:09
Show Gist options
  • Save DmitrySoshnikov/b8639c2cc39f8dc9ba95 to your computer and use it in GitHub Desktop.
Save DmitrySoshnikov/b8639c2cc39f8dc9ba95 to your computer and use it in GitHub Desktop.
Parsing notes: "Shift-reduce" and "Reduce-reduce" conflicts in LR parsing

"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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment