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

Question

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?

Answer 1

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.