Compiler Design

LR(0) & SLR Parsing / Solved Problem: SLR

PreviousNext

SLR Solved Problem: E → BB, B → cB | d

Let us construct the complete SLR(1) parsing table for the following grammar and trace the verification process for the string ccdd:

(0) E' → E (1) E  → BB (2) B  → cB (3) B  → d
  • FIRST(E) = { c, d }
  • FIRST(B) = { c, d }
  • FOLLOW(E) = { $ }
  • FOLLOW(B) = { c, d, $ }
    (Since E → BB, the first B is followed by FIRST(B) = {c, d}, and the second B is at the end of the production, inheriting FOLLOW(E) = {$})
State I0 (Initial State):
E' -> • E
E  -> • BB
B  -> • cB
B  -> • d
Goto(I0, E) = I1 | Goto(I0, B) = I2 | Goto(I0, c) = I3 | Goto(I0, d) = I4
State I1 (Accept State):
E' -> E •
State I2:
E -> B • B
B -> • cB
B -> • d
Goto(I2, B) = I5 | Goto(I2, c) = I3 | Goto(I2, d) = I4
State I3:
B -> c • B
B -> • cB
B -> • d
Goto(I3, B) = I6 | Goto(I3, c) = I3 | Goto(I3, d) = I4
State I4 (Reduce State):
B -> d •  [r3]
State I5 (Reduce State):
E -> BB •  [r1]
State I6 (Reduce State):
B -> cB •  [r2]

Note: sN indicates Shift to state N; rN indicates Reduce using production rule N; acc means Accept.

StateACTION TableGOTO Table
cd$EB
0s3s4—12
1——acc——
2s3s4——5
3s3s4——6
4r3r3r3——
5——r1——
6r2r2r2——
StepStackInput BufferAction
10c c d d $Shift to state 3 (s3)
20 c 3c d d $Shift to state 3 (s3)
30 c 3 c 3d d $Shift to state 4 (s4)
40 c 3 c 3 d 4d $Reduce by B → d (r3). Pop d 4, Goto(3, B) = 6. Push B 6.
50 c 3 c 3 B 6d $Reduce by B → cB (r2). Pop c 3 B 6, Goto(3, B) = 6. Push B 6.
60 c 3 B 6d $Reduce by B → cB (r2). Pop c 3 B 6, Goto(0, B) = 2. Push B 2.
70 B 2d $Shift to state 4 (s4)
80 B 2 d 4$Reduce by B → d (r3). Pop d 4, Goto(2, B) = 5. Push B 5.
90 B 2 B 5$Reduce by E → BB (r1). Pop B 2 B 5, Goto(0, E) = 1. Push E 1.
100 E 1$Accept (acc)
Back to LR(0) & SLR ParsingCLR(1) & LALR Parsing