12 LR0 SLR PDF

LR(0) and SLR parse table construction
Wim Bohm and Michelle Strout

CS, CSU
CS453 Lecture
Building LR Parse Tables
parse
Parse table for List grammar

0: S S$ 1: S( L ) 2: Sx
3: LS
4: LL , S
(
0
s2
r2
s2
s1
r2
r2
S
g3
r2
r2
s1
g6
s5
s7
r1
r1
r1
r1
r1
r3
r3
r3
r3
r3
s2
r4
CS453
s1
r4
r4
g8
r4
r4
g4
(x,(x))$
stack
0
0(2
0(2x1
0(2S6
0(2L4
0(2L4,7
0(2L4,7(2
0(2L4,7(2x1
0(2L4,7(2S6
0(2L4,7(2L4
0(2L4,7(2L4)5
0(2L4,7S8
0(2L4
0(2L4)5
03S
Shift-reduce Parsing
input
action
(x,(x))$
s2
x,(x))$
s1
,(x))$ r2: Sx
,(x))$ r3: LS
,(x))$ s7
(x))$ s2
x))$ s1
))$ r2: Sx
))$ r3: LS
))$ s5
)$ r1: S (L)
)$ r4: LL,S
)$ s5
$ r1:S(L)
$ a
2
LR(0) table construction

Example grammar for Nested Lists:
0: S S$
1: S( L )
2: Sx
3: LS
4: LL , S
We start with an empty stack and with a complete S$ sentence on input

We indicate this as follows: S. S$
this (a rule with a dot in it) is called an item,
it indicates what is in the stack (left of .)
and what is to be expected on input (right of .)
The input can start with anything S can start with, eg an x or a (
We indicate this as follows:
S.S$
(we are making a DFA
S.x
through another sub-set closure
S.(S)
remember the NFA DFA)
We call this a state: state 0, the start state with an empty prefix (V[])
CS453
Shift, reduce, goto actions in LR(0) table construction

S.S$
S .x
S.(L)
0:V[]
shift action:
In state 0 we
can shift an x
or shift a (
S x.
1:V[x]
S(.L)
L.L,S
L.S
S .x
S.(L)
2:V[(]
goto action:
Also in state 0
we could have
reduced to S
SS.$
3:V[S]
In state 1 we are at the end

of an item. This will give rise
to a reduce action
Transitions: the shifts and gotos explicitly connect the states. The
reduces implicitly move to another state by popping the rhs off the
stack, after which a goto with the lhs will produce a new next state
CS453
LR(0) states and transitions

x
S.S$
S .x
S.(L)
0:V[]
S
(
SS.$
3:V[S]
S
L S.
6:V[(S]
CS453
S x.
1:V[x]
x
S(.L)
L.L,S
L.S
S.x
S.(L)
2:V[(]
L L,.S
S.x
S.(L)
7:V[(L] ,
S (L.)
L L.,S
4:V[(L]
)
S (L).
5:V[(L)]
L L,S.
8:V[(L,S]
List grammar
0: S S$
1: S( L )
2: Sx
3: LS
4: LL , S
LR(0) Closure, Goto, State Diagram, Reduce

Closure(I): // state I
repeat
for any item A . X
for any X
I+= X .
until I does not change
Goto(I,X): // state I , symbol X

if X==$ return {} // no gotos for $
J = {}
// new state
for any item A . X in I
J+= AX .
return Closure(J) // close it
State Diagram construction

Reduce(T):
T = Closure({ S .S$ } ); // states
R = {}
E = {}
// edges (gotos and shifts)
for each state I in T
repeat until no change in E or T
for each item A .
for each state I in T
R += (I, A )
for each item A . X in I
J = Goto(I,X);
T +=J ;
E += (X: (I,J)) // the edge (I,J) labeled X
CS453
Applying the Algorithm to the Nested Lists Example

List grammar
0: S S$
1: S( L )
2: Sx
3: LS
4: LL , S
S.S$
0:V[]
CS453
LR(0) states and transitions

x
S.S$
S .x
S.(L)
0:V[]
S
(
SS.$
3:V[S]
S
L S.
6:V[(S]
CS453
S x.
1:V[x]
x
S(.L)
L.L,S
L.S
S.x
S.(L)
2:V[(]
L L,.S
S.x
S.(L)
7:V[(L] ,
S (L.)
L L.,S
4:V[(L]
)
S (L).
5:V[(L)]
L L,S.
8:V[(L,S]
List grammar
0: S S$
1: S( L )
2: Sx
3: LS
4: LL , S
LR(0) parse table construction
Parse table
rows: states
columns: terminals (for shift and reduce actions)
non-terminals (for goto actions)
For each edge (X: (I, J))
if X is terminal, put shift J at (I, X)
if X is non-terminal, put goto J at (I, X)
if I contains SS . $ , put accept at (I, $)
if I contains A . where A . has grammar rule number n
for each terminal x, put reduce reduce n at (I, x)
CS453
parse
Parse table for List grammar

0: S S$ 1: S( L ) 2: Sx
3: LS
4: LL , S
(
L
0
1
2
3
4
5
6
7
8
s2
r2
s2
r1
r3
s2
r4
CS453
r2
s1
r2
s1
s5
r1
r3
r4
r1
r3
s1
r4
S
g3
r2
r2
g6
a
s7
r1
r3
g4
r1
r3
g8
r4
r4
(x,(x))$
stack
input
0
(x,(x))$
0(2
x,(x))$
0(2x1
,(x))$
0(2S6
,(x))$
0(2L4
,(x))$
0(2L4,7
(x))$
0(2L4,7(2 x))$
0(2L4,7(2x1 ))$
0(2L4,7(2S6 ))$
0(2L4,7(2L4 ))$
0(2L4,7(2L4)5 )$
0(2L4,7S8
)$
0(2L4
)$
0(2L4)5
$
03S
$
action
s2
s1
r2: Sx
r3: LS
s7
s2
s1
r2: Sx
r3: LS
s5
r1: S (L)
r4: LL,S
s5
r1:S(L)
a
10
Building the LR Parse Table for LR(0), nested parens example

[0] S -> ( S )
[1] S -> S EOF
[2] S -> ID
CS453 Lecture
11
LR(0) states for nested parens example
CS453 Lecture
12
Building the Table from the State Diagram

Action
State
s3
r2
r2
2
3
CS453 Lecture
r2
ID
s1
r2
accept
s3
4
5
Goto
s1
s5
r0
r0
r0
r0
13
Suggested Exercise: Building the LR Parse Table for LR(0)

(0) S -> E $
(1)E -> E || B
(2)E -> B
(3)B -> t
(4)B -> f
CS453 Lecture
14
Problem with LR(0): shift reduce conflict

If there is an item A . item in I , we reduce for all terminals
This can cause CONFLICTS:
E E+T
E.E+T
E T
E.T
T T*F
T.T*F
0
In state 1:
we reduce (ET.) AND we shift
ET.
TT . *F
TT * . F
2
(TT . *F)
What should we do?
CS453
15
LR(0) shift reduce conflict
We can resolve the conflict by looking at a right most derivation:

ETT*FT*idF*idid*id
Stack
id
F
T
T*
T*id
T*F
T
E
CS453
input
action
id*id$
S
*id$ R: Fid
*id$ R: FT
*id$ S
id$ S
$ R: Fid
$ R: TT*F
$
R:E
$
accept
We should shift. WHY?
16
SLR parsing
SLR parsing is LR(0) parsing, but with a different reduce rule:
For each edge (X: (I, J))
if X is terminal, put shift J at (I, X)
if I contains A . where A . has rule number n
for each terminal x in Follow(A), put reduce reduce n at (I, x)
Build an SLR parser for our expression grammar

0: SE$ 1:EE+T 2:ET 3:TT*F 4:TF 5:F(E) 6:Fid

Need to build the transiAon diagram and follow sets
to decide where to put the reduce acAons in the SLR table
CS453
17
0: SE$ 1:EE+T 2:ET 3:TT*F 4:TF 5:F(E) 6:Fid

SLR parse table (reduces only for follows)

State id + * ( ) $ E T F
0 s5 s4 g1 g2 g3
1 s6 a
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 g8 g2 g3
5 r6 r6 r6 r6
6 s5 s4 g9 g3
7 s5 s4 g10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
CS453
Stack input ac+on

0 a*(b+c)$ s5
0a5 *(b+c)$ r6: Fid
0F3 *(b+c)$ r4: TF
0T2 *(b+c)$ s7
0T2*7 (b+c)$ s4
0T2*7(4 b+c)$ s5
0T3*7(4b5 +c)$ r6: Fid
0T3*7(4F3 +c)$ r4: TF
0T3*7(4T2 +c)$ r2: ET
0T3*7(4E8 +c)$ s6
0T3*7(4E8+6 c)$ s5
0T3*7(4E8+6c5 )$ r6: Fid
0T3*7(4E8+6F3 )$ r4: TF
0T3*7(4E8+6T9 )$ r1: EE+T
0T3*7(4E8 )$ S11
0T3*7(4E8)11 $ r5: F(E)
0T3*7F10 $ r3: TT*F
0T2 $ r2: ET
0E1 $ a
18
EE+T | T TT*F | F F (E) | id

Stack input ac+on
a*(b+c)$ S

a *(b+c)$ R: Fid
F *(b+c)$ R: TF
T *(b+c)$ S
T* (b+c)$ S
T*( b+c)$ S
T*(b +c)$ R: Fid
T*(F +c)$ R: TF
T*(T +c)$ R: ET
T*(E +c)$ S
SE$
input: a*(b+c)$
Stack input ac+on

T*(E+ c)$ S
T*(E+c )$ R: Fid
T*(E+F )S R: TF
T*(E+T )$ R: EE+T
T*(E )$ S
T*(E) $ R: F(E)
T*F $ R: TT*F
T $ R: ET
E $ accept
SE$T$T*F$T*(E)$T*(E+T)$T*(E+F)$ T*(E+id)$T*(T+id)$
T*(F+id)$T*(id+id)$ F*(id+id)$id*(id+id)$
Rightmost deriva/on in reverse
CS453
19

12 LR0 SLR PDF

Uploaded by

Copyright:

Available Formats

12 LR0 SLR PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

12 LR0 SLR PDF

Uploaded by

Copyright:

Available Formats

LR(0) and SLR parse table construction

Wim Bohm and Michelle Strout

Building LR Parse Tables

Parse table for List grammar

LR(0) table construction

We start with an empty stack and with a complete S$ sentence on input

Shift, reduce, goto actions in LR(0) table construction

In state 1 we are at the end

LR(0) states and transitions

LR(0) Closure, Goto, State Diagram, Reduce

Goto(I,X): // state I , symbol X

State Diagram construction

Applying the Algorithm to the Nested Lists Example

LR(0) states and transitions

LR(0) parse table construction

Parse table for List grammar

Building the LR Parse Table for LR(0), nested parens example

Building LR Parse Tables

LR(0) states for nested parens example

Building LR Parse Tables

Building the Table from the State Diagram

Building LR Parse Tables

Suggested Exercise: Building the LR Parse Table for LR(0)

Building LR Parse Tables

Problem with LR(0): shift reduce conflict

What should we do?

LR(0) shift reduce conflict

We can resolve the conflict by looking at a right most derivation:

We should shift. WHY?

Build an SLR parser for our expression grammar

0: SE$ 1:EE+T 2:ET 3:TT*F 4:TF 5:F(E) 6:Fid

Stack input ac+on

EE+T | T TT*F | F F (E) | id

Stack input ac+on

You might also like