# Sheet 9, Task 3 c) / SLR(1)

I don't understand why B -> a, A-> a, A -> BA, B -> bB are written where they are. Maybe I am mixing it with LR(0) table, is there a difference? Well, for the grammar

```A -> a | BA
B -> a | bB
```

we obtain

```    First(A) = {a,b}
First(B) = {a,b}
```

and

```    Follow(A) = {\$}
Follow(B) = {a,b}
```

The parse table for a top-down parser would therefore not have unique decisions since the grammar is not LL(1). The LR(0) automaton is as follows: The action table for a LR(0) parser is now determined by the following rules (see slide 178):

• if q_i contains A → α.aβ with a ∈ T, and q_i′ is the state reached in the automaton from q_i reading a, then shift a on the stack and put q_i′ above
• if q_i contains S′ → S. and the input is ε, accept
• if q_i contains B → γ., then reduce with rule B → γ

This yields the following action table:

 state a b \$ A B q0 S(3) S(4) G(1) G(2) q1 A q2 S(3) S(4) G(5) G(2) q3 R(B->a) R(B->a) R(A->a) q4 S(7) S(4) G(6) q5 R(A->BA) q6 R(B->bB) R(B->bB) q7 R(B->a) R(B->a)

For instance, in state q0, we have the rule A ->.a which leads to a shift action for a that leads to the new state q3, and we we have the rule B -> .bB that leads to the shift action for b that leads to state q4. There is a reduce/reduce conflict in state 3 since we could reduce with A-> a. and also with B->a. as well.

Therefore, the grammar is not a LR(0) grammar and we need to construct the SLR(1) action table.  Here the third rule above becomes

• if q_i contains B → γ., then reduce with rule B → γ provided that the next input token is in FOLLOW(B)

and this resolves the reduce/reduce conflict.

by (147k points)
selected