Skip to content

Instantly share code, notes, and snippets.

@lin
Last active June 3, 2024 09:15
Show Gist options
  • Save lin/dc83bb38eb458ded3ff01aec4a327d54 to your computer and use it in GitHub Desktop.
Save lin/dc83bb38eb458ded3ff01aec4a327d54 to your computer and use it in GitHub Desktop.
Simple examples to distinguish LR(0), SLR(1), LR(1), LALR(1), LR(k)

1. Grammar that is SLR(1), but not LR(0)

S -> a A c | a B d.
A -> z.
B -> z.

The test string can be azc.

Click for more about the above grammar, LR(0) Item Sets

1

The reason it's not LR(0) is that after reading the same token a, and same token z, you have two choices to reduce. (state 5)

But you can distinguish A and B by comparing the follow sets of A and B. where {c} for A and {d} for B.

2. Grammar that is LR(1), but not SLR(1) (But it's LALR(1))

S -> a A c | a B d | B c.
A -> z.
B -> z.

The test string can be azc.

Click for more about the above grammar

It's not SLR(1) since the follow set of B also includes c.

But you can trace the path of DFA to further examine the follow set. This is why LR(1) is more flexible when conflicts occur. It's a little hard to understand. It's helpful to see the DFA of both SLR:

SLR

and LR:

LR

3. Grammar that is LR(1), but not LALR(1)

S -> a A c | a B d | b A | b B c.
A -> z.
B -> z.

The test string can be azc.

Click for more about the above grammar

If you know the procedure to get LALR. You can see that, in the DFA of LR(1):

LR

state 9 and state 6 can be merged. That's why production S -> a A c | a B d | b A | b B part is introduced (not adding the last c).

It leads to a similiar state with same core as in SLR(1) DFA. As long as .A and .B is in the same state, it will lead to state 9 and state 6. After the merge, we got the DFA of LALR(1):

LALR

Now, we add the trailing c to the production S -> a A c | a B d | b A | b B c, after the merge, both the follow set of A_8 and B_8 contains c. Thus it has reduce-reduce conflicts.

4. Grammar that is LR(2), but not LR(1)

S -> a A c | a B c d.
A -> z.
B -> z.

The test string can be azc. This one is trivial.

LR(2)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment