SLR Parser Examples

Example 1:
Parsing of the input string id * id + id using the SLR parser table for the grammar
1. E → E + T
2. E → T
3. T → T * F
4. T → F
5. F → ( E )
6. F → id


Stack
Input
Next
1
0
id * id + id $
Shift
2
0 id5
 * id + id $
reduce by F →id
3
0 F3
 * id + id $
reduce by T → F
4
0 T2
 * id + id $
shift
5
0 T2 * 7
  id + id $
shift
6
0 T2 * 7 id 5
+ id $
Reduce by F → id
7
0 T2 * 7 F 10
+ id $
Reduce by T → T * F
8
0 T2
+ id $
Reduce by E → T
9
0 E 1
+ id $
Shift
10
0 E 1 + 6
id $
Shift
11
0 E1 + 6 id 5
i $
Reduce by F → id
12
0 E1 + 6 F 3
$
Reduce by T → F
13
0 E1 + 6 T 9
$
E → E + T
14
0 E1
$
Accept

Example 2:
Construct SLR parser for S → (S)S | ε
The augmented grammar is, S’ → S   S → (S)S   S → ε
The canonical collection of LR(0) items are
I0:
S’ → .S
S → .(S)
S’ → .
I1:
S’ → S.
I2:
S → (.S)S
S → .(S)S
S → .
I3:
S → (S.)S
I4:
S → (S).S
S → .(S)S
S → .
I5:
S → (S)S.
DFA from Canonical collection of LR(0) items:
The GOTO function of the canonical collection of set of items defines a DFA that recognizes the viable prefixes of the grammar
Each set of item becomes a state in the DFA
The DFA for the example 2 from its items is
SLR Parser Examples, exercises on slr parsers, slr parsers examples with explanation,jntuh r16 compiler design lecture notes, r16 jntuh compiler design syllabus,r16 jntuh compiler design teaching notes, jntu compiler design notes pdf unitwise,estudies4you,
 Construction SLR Parsing Table for Example 2
States
ACTION
GOTO
(
)
$
S
0
S2
r2
r2
1
1


Accept
-
2
S2
r2
r2
3
3

S4


4
S2
r2
r2
5
5

r1
r1


Parsing the Input String for Example 2
Stack
Input String
Action
$ 0
( ) $
Shift
$ 0 ( 2 ) $
) $
Reduce S E, goto[2, S] = 3
$ 0 ( 2 S 3
) $
Shift
$ 0 ( 2 S 3 ) 4
$
Reduce S E, goto[4, S] = 5
$ 0 ( 2 S 3 ) 4 S 5
$
Reduce S (S)S, goto[0, S] = 1
$ 0 S 1
$
Accept

Example 3:
Construct SLR Parser for S→ CC, C → Cc | d
Example 4:
Show that the grammar S → xAy | xBy | xAz   A → qS | q  B → q is not SLR(1)
Example 5:
Show that the grammar S → 0S0 | 1S1 | 10 is not SLR(1)
Example 6:
Show that the grammar S → AaAb | BbBa   A → ε  is not SLR(1)
Example 7:
Show that the grammar S → AS | b   A → SA | a is not SLR(1)
Example 8:
Show that S → L = R | R the grammar is not SLR(1),
                                                L → *  R |id
                                                R → L


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