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.
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:
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 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.
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.
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.
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.
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.
Top-down Parsing | Bottom-up Parsing |
---|---|
"Root" initiation in case of Top-down parsing | "Leave" initiation in case of Bottom-up |
It is quite often used for "Backtracking" | It is used for managing & handling code |
"Leftmost derivation" is followed in Top-down parsing | "Rightmost derivation" is followed in Bottom-up parsing |
This post was last modified on June 23, 2021