Difference between Top-down and Bottom-up Parsing

In this article, we’re going to understand what “Parsing” is and also the key differences between Top-down and Bottom-up parsing in detail.

Let’s start by discussing “Parsing” thoroughly:

Parsing can be defined as the process or technique of converting one type/ form of data into another type/form of data.

All this is done immediately after the lexical analysis phase of the compilation. For the record, the lexical analysis phase is the one in which the source code (containing various lines of code) is broken down into series of tokens, the comments are removed along with the white spaces.

How to explain parsing in simple terms?

In layman’s terms, parsing can be defined as the mechanism which changes the program data to another form so that it is more understandable from the machine’s point of view.

Technically speaking, Parsing can be defined as the phenomenon which changes the program data to another form so that it is more understandable from the machine point of view.

There are basically two types of Parsing methods, namely:

• Top-down Parsing
• Bottom-up Parsing

Top-down Parsing

The top-down parsing can be defined as the parsing method in which there is a parse tree generated from top to bottom. Or in other words, we can say that the parse tree is generated from root to the leaves. This method derives the leftmost string and when it so happens that the string matches the requirement, it is then terminated.

• The top-down parsing is also called as “Predictive parsing” or “Recursive parsing”.
• The parsing starts from the root of the derivation tree and then fills in.

Bottom-up Parsing

The bottom-up parsing can be defined as the inverse of the top-down parsing, which means that the parse tree is generated from bottom to top. In this method firstly, the input string is taken and then using the grammar the string is reduced.

• The bottom-up parsing is also called as “Shift-reduce parsing”.
• The parsing starts from the leaves and then fills in.

The differences between Top-down and Bottom-up Parsing are as follows:

• Initiated From

When it comes to the top-down parsing then this parsing method is always initiated from the Root; whereas; when it comes to the Bottom-up parsing then this parsing method is always initiated from the Leaves.

• Working Mechanism

In the case of the top-down parsing, it so happens that the production is dedicated to derive and find out the similarity in the string; whereas; In the case of the bottom-up parsing, it so happens that the process starts from token and then it proceeds towards the start symbol.

• Method Uses

When it comes to the top-down parsing then this parsing method is most often used for Backtracking; whereas; when it comes to the bottom-up parsing then this parsing method is most often used for handling and managing the code.

• Derivation Type

In the case of the top-down parsing, it so happens that this parsing method always follows the leftmost derivation; whereas; in the case of the bottom-up parsing, it so happens that this parsing method always follows the rightmost derivation.

Key Differences