Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers

1.6k comments

529 users

0 votes

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?

in # Study-Organisation (Bachelor) by (380 points)

1 Answer

0 votes
 
Best answer

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 (166k points)
selected by

Related questions

Imprint | Privacy Policy
...