Working of Bottom up parser

In this article, we are going to cover working of the bottom-up parser and will see how we can take input and parse it and also cover some basics of bottom-up parser. 

Pre-requisite – Parsing  

Bottom-up parser : 
 

• It will start from string and proceed to start.
• In Bottom-up parser, Identifying the correct handle (substring) is always difficult.
• It will follow rightmost derivation in reverse order.

Note : 
In bottom-up parser, no variable that’s why not have any derivation from the bottom but in reverse order it is looking like top-down, when you have rightmost derivation. 

Working of Bottom-up parser : 
Let’s consider an example where grammar is given and you need to construct a parse tree by using bottom-up parser technique. 

Example – 
 

S -> aABe
A -> Abc | b
B -> d

Now, let’s consider the input to read and to construct a parse tree with bottom-up approach. 

Input – 
 

abbcde$

Now, you will see that how bottom-up approach works. Here, you will see how you can generate a input string from the grammar for bottom-up approach. 
 

• First, you can start with A -> b.
• Now, expand A -> Abc.
• After that Expand B-> d.
• In the last, just expand the S -> aABe
• Final string, you will get abbcde.

Given below is the Diagram explanation for constructing bottom-up parse tree. You can see clearly in the diagram how you can generate the input string using grammar with bottom-up approach. 

From the above explanation and diagram, you can clearly see and can say it follows reverse of the rightmost derivation.