Construction of SLR Parsing Table

Construction of SLR Parsing Table

The parsing table has two fields associated with each state in the DFA known as action and goto. These are computed using the following algorithms:

Construct C ={I0,I1,…..In}, the collection of sets of LR(0) items for G’

State i is constructed from Ii. The parsing actions for state i are determined as follows:

                If [A→α.aβ] is in Ii and goto(Ii, a) = Ij, then set action[i, a] to “shift j.” Here, a is required to be a terminal

                If [A→α.] is in Ii then set action [i, a][ to “reduce A→ α] for all a in FOLLOW(A), here A may not be S’

                If [S’ → S.] is in Ii, then set action[i, $] to “accept”

If any conflicting actions are generated by the above rules, we say the grammar is not SLR(1). The algorithm fails to produce a parser in this case.

The goto transitions for state I are constructed for all non-terminals A using the rule: if goto(Ii, A) = Ij, then goto[i, A] =j

All entries not defined by rules (2) and (3) are made “error”

The initial state of the parser is the one constructed from the set containing item [S’ → S]

Number of productions in the grammar from onwards and use the production number while making a reduction entry

For example for the given grammar

                1. E → E + T

                2. E → T

                3. T → T * F

                4. T → F

                5. F → ( E )

                6. F → id

This construction requires FOLLOW of each non-terminal present in the grammar to be computed

The grammar that has a SLR parsing table is known as SLR(1) grammar. Generally, 1 is omitted

The canonical collection of SLR(0) items are

I0:

E’ → .E

E → .E + T

E → .T

T → .T * F

T → .F

F → .( E )

F → .id

I1:

E’ → E.

E → E.+ T

I2:

E → T.

T → T .* F

I3:

T → F.

I4:

F → (.E)

E → . E + T

E → .T

T → .T * F

T → .F

F → .( E )

F → .id

I5:

F → id.

I6:

E → E + .T

T → .T * F

T → .F

F → .( E )

F → .id

I7:

T → T * .F

F → .( E)

F → .id

I8:

F → ( E .)

E → E. + T

I9:

E → E + T.

T → T. * F

I10:

T → T * F.

I11:

F → ( E ).

The DFA for the canonical set of SLR items is

Construction of SLR Parsing Table for Example

STATE	ACTION						GOTO
	id	+	*	(	)	$	E	T	F
0	s5						1	2	3
1		s6		s4		ACC
2		r2	s7		r2	r2
3		r4	r4		r4	r4
4	s5			S4			8	2	3
5		r6	r6		r6	r6
6	s5			s4				9	3
7	s5			s4					10
8		s6			s11
9		r1	s7		r1	r1
10		r3	r3		r3	r3
11		r5	r5		r5	r5

Here , si means shift state i. ri means ‘reduce by using production number I’ and ACC means Accept, blank means error.

Canonical Construction of LR(0) Items

Home

LR Parser