TEXTBOOK IS: Concepts of Programming Languages 11th Edition - LET ME KNOW IF YOU
ID: 3817126 • Letter: T
Question
TEXTBOOK IS: Concepts of Programming Languages 11th Edition - LET ME KNOW IF YOU NEED ANYTHING ELSE. THANKS!!!
4. (30 pts) Show a complete parse, including the parse stack contents, input string, and for the string (id id) id, using the LR paring table Fig. 4.5 on Page 189 together with the grammar rules for arithmetic expression on Page 188 of the textbook. You may use S for shift and R for reduce, Action Input String Parse Stack 44 6 S 8 S 9 S 10 S 11 S 12 S 13 S 14 S 15 S 16 S 17 S 18 S 19 S 20 SExplanation / Answer
S.NO
Parse Stack
Input String
Action
1
$ 0
( id + id ) * id $
Shift 4
2
$ 0 (4
id+id)*id $
Shift 5
3
$ 0 (4 id5
+ id)*id $
Reduce 6 use goto[0,F]
4
$0 (4 F3
+ id )*id $
Reduce 4 use goto[0,T]
5
$ 0 (4 T2
+ id ) * id $
Reduce 2 use goto[0,E]
6
$ 0 (4 E1
+ id ) *id $
Shift 6
7
$ 0 (4 E1 +6
id ) * id $
Shift 5
8
$ 0 (4 E1 +6 id 5
) * id $
Reduce 6 use goto[4,F]
9
$0 (4 E1 +6 F 3
) * id $
Reduce 4 use goto[4,T]
10
$ 0 (4 E1 +6 T 2
) * id $
Reduce 2 use goto[4,E]
11
$0 (4 E 8
) * id $
SHIFT 11
12
$ 0 (4 E8 ) 11
* id $
Reduce 5 Use goto[6,F]
13
$0 F 3
* id $
Reduce 4 Use goto[6,T]
14
$0 T 9
* id $
SHIFT 7
15
$0 T 9 * 7
Id $
Shift 5
16
$0 T9 * 7 id 5
$
Reduce 6 Use goto[7,F]
17
$0 T9 * 7 F 10
$
Reduce 3 Use goto[6,T]
18
$ 0 T 9
$
Reduce 1 Use goto[0,E]
19
$ 0 E 1
$
Accept
input tape have $ indicate the right end marker means end of the string.
S.NO
Parse Stack
Input String
Action
1
$ 0
( id + id ) * id $
Shift 4
2
$ 0 (4
id+id)*id $
Shift 5
3
$ 0 (4 id5
+ id)*id $
Reduce 6 use goto[0,F]
4
$0 (4 F3
+ id )*id $
Reduce 4 use goto[0,T]
5
$ 0 (4 T2
+ id ) * id $
Reduce 2 use goto[0,E]
6
$ 0 (4 E1
+ id ) *id $
Shift 6
7
$ 0 (4 E1 +6
id ) * id $
Shift 5
8
$ 0 (4 E1 +6 id 5
) * id $
Reduce 6 use goto[4,F]
9
$0 (4 E1 +6 F 3
) * id $
Reduce 4 use goto[4,T]
10
$ 0 (4 E1 +6 T 2
) * id $
Reduce 2 use goto[4,E]
11
$0 (4 E 8
) * id $
SHIFT 11
12
$ 0 (4 E8 ) 11
* id $
Reduce 5 Use goto[6,F]
13
$0 F 3
* id $
Reduce 4 Use goto[6,T]
14
$0 T 9
* id $
SHIFT 7
15
$0 T 9 * 7
Id $
Shift 5
16
$0 T9 * 7 id 5
$
Reduce 6 Use goto[7,F]
17
$0 T9 * 7 F 10
$
Reduce 3 Use goto[6,T]
18
$ 0 T 9
$
Reduce 1 Use goto[0,E]
19
$ 0 E 1
$
Accept
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.