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,canonical collection of SLR(0) items,how to construct slr parsing table, how to construct lr(0) parsing table, r16 jntuh compiler design notes, r16 jntuh compiler design lecture notes,jntuh r16 3-1 compiler design notes pdf,estudies4you


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.



Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment