Show a complete bottomup parse including the parse stack con

Show a complete bottom-up parse, including the parse stack contents, input string, andaction for the string below using the parse table above.

(id + id) * id

Show a rightmost derivation for the string above, and show how the bottom-up parse
you completed above correctly finds all of the handles for the input string above.

I

C

Id

+

*

)

$

E

T

1

S4

S5

-

-

-

-

2

3

2

S6

S7

accept

3

R1

R1

R1

R1

4

S4

S5

8

3

5

R6

R6

R6

R6

6

S4

S5

9

7

S4

S5

10

8

S6

S7

S11

9

R2

R2

R2

R2

10

R3

R3

R3

R3

11

R5

R5

R5

R5

I	C	Id	+	*	)	$	E	T
1	S4	S5	-	-	-	-	2	3
2			S6	S7		accept
3			R1	R1	R1	R1
4	S4	S5					8	3
5			R6	R6	R6	R6
6	S4	S5						9
7	S4	S5						10
8			S6	S7	S11
9			R2	R2	R2	R2
10			R3	R3	R3	R3
11			R5	R5	R5	R5

Solution

Bottom-up Parsing Bottom-up parsing corresponds to the construction of a parse tree for an input string beginning at the leaves (the bottom nodes) and working up towards the root (the top node). It involves “reducing an input string ‘w’ to the Start Symbol of the grammar. in each reduction step, a perticular substring matching the right side of the production is replaced by symbol on the left of that production and it is the Right most derivation. For example consider the following Grammar: Bottom up parsing of the input string “id * id “is as follows

Bottom up parsing is classified in to 1. Shift-Reduce Parsing 2. Operator precedence parsing 3. Table Driven L R Parsing i. LR ( 1 ) ii. SLR( 1 ) iii. CLR ( 1 ) iv. LALR( 1 ) Shift-Reduce Parsing Shift-reduce parsing is a form of bottom-up parsing in which a stack holds grammar symbols and an input buffer holds the rest of the string to be parsed, We use $ to mark the bottom of the stack and also the right end of the input. And it makes use of the process of shift and reduce actions to accept the input string. Here, the parse tree is Constructed bottom up from the leaf nodes towards the root node. When we are parsing the given input string, if the match occurs the parser takes the reduce action otherwise it will goes for shift action. And it can accept ambiguous grammars also.