Bottom up Parsing with example

Question

What do you mean by the term bottom up Parsing with appropriate example?

Answer 1

The Parsing is a technique in which the Parse tree is made from the input language string beginning from the leaves and going up to the root node.

• Bottom-Up parsing is as well termed shift-reduce parsing due to its implementation.
• The YACC supports the shift-reduce parsing.

Example: Assume that there is a grammar G having a production E:

E->E*E

and an input string x*y.

The left hand side of any production is termed as Handles. Therefore the handle for this instance is E.

The shift action is just pushing an input symbol on the stack. If the right hand side of a production is matched with the stack elements which are popped and replaced by the corresponding Handle. This is the reduce action.