Difference between top down and bottom-up parsing ques10

Previous Year Questions with Solutions

,

study material

,

Important questions

,

Sample Paper

,

video lectures

,

Extra Questions

,

Objective type Questions

,

mock tests for examination

,

shortcuts and tricks

,

Semester Notes

, ,

Free

,

Viva Questions

,

practice quizzes

,

ppt

,

Exam

, ,

past year papers

,

MCQs

, ,

pdf

,

Summary

;

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:

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.

Key Differences

Top-down ParsingBottom-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

The key difference between top down and bottom up parsing is that the top down parsing performs the parsing from the staring symbol to the input string while the bottom down parsing performs the parsing from input string to the starting symbol. Furthermore, another important difference between top down and bottom up parsing is that the top down parsing uses left most derivation and bottom down parsing uses right most derivation.

High-level languages help to write computer programs. They are easier to understand by the programmer but not by the computer. Therefore, the high-level program converts to machine code. The task of the compiler is to convert the human readable source code to machine readable machine code. A program goes through several steps to convert to machine code. This whole process is called Language processing System. One of them is the compilation. The syntax analyzer or the parser is in the compiler, and it performs the parsing task.

CONTENTS

1. Overview and Key Difference
2. What is Top Down Parsing
3. What is Bottom Up Parsing
4. Side by Side Comparison – Top Down vs Bottom Up Parsing in Tabular Form
5. Summary

What is Top Down Parsing?

Every programming language has a set of rules to represent the language. The syntax analyzer or the parse takes the input string and checks whether it is according to the grammar productions. In other words, the grammar should produce that string using a parse tree.

In top down parsing, the parsing happens from the starting symbol and will reach the given input string. Consider the following grammar production rules. The input string (w) is cad.

S -> cAd

A -> ab /a

The parse tree after performing top down parsing is as follows.

Difference between top down and bottom-up parsing ques10

Figure 01: Parse Tree 1 with Top Down Parsing

S produce c A d and A produces a b. The string is cabd. It is not the required string. So, it is necessary to do backtracking, which is to use the other alternatives.

Similarly, S produce c A d.  Applying the other option for A will give a. Now it gives the required string. Therefore, the parser accepts this input string. The parse tree after performing top down parsing is as follows.

Difference between top down and bottom-up parsing ques10

Figure 02: Parse Tree 2 with Top Down Parsing

When the input string (w) is abbcde

Consider the following grammar production rules.

S -> aABe

A -> Abc/b

B -> d

In top down parsing,

S -> aABe (Substituting A -> Abc)

S -> aAbcBe (Substituting A -> b)

S -> abbcBe (Substituting B ->d)

S -> abbcde

Substitution starts with the left most variable first and then to the next right position and so on. Therefore, it follows a left most derivation method. Furthermore, it is important to decide what production rule to choose when there is a variable. 

In bottom up parsing happens in the other way. The parsing happens from the input string to the starting symbol. Consider the following grammar production rules and let the input string be w ɛ cad

S -> cAd

A -> ab /a

The parse tree after performing bottom up parsing is as follows.

Difference between top down and bottom-up parsing ques10

Figure 03: Parse Tree with Bottom Up Parsing

The given string is cad. The a is generated by A. The c, A and d combines to get the starting symbol S.

When the input string(w)  is abbcde

Consider the following grammar production rules.

S -> aABe

A -> Abc/b

B -> d

In bottom up parsing,

S -> aABe (Substituting B ->d)

S -> aAde (Substituting A -> Abc)

S -> aAbcde (Substuting A -> b)

S -> abbcde

Substitution starts with the right most variable first and then moves to the next left position and so on. Therefore, it follows a left mot derivation method.

Top-down parsing is a parsing strategy that first looks at the highest level of the parse tree and works down the parse tree by using the rules of a formal grammar. Bottom up parsing is a parsing strategy that first looks at the lowest level of the parse tree and works up the parse tree by using the rules of a formal grammar. The parsing occurs from the starting symbol to the input string, in top down parsing.  On the other hand, parsing occurs from the input string to the starting symbol, in bottom up parsing.

Furthermore, the main decision in top down parsing is to select what production rule to use in order to construct the string while the main decision in bottom down parsing is to select when to use a production rule to reduce the string to get the starting symbol. Moreover, top down parsing uses left most derivation and bottom down parsing uses right most derivation.

The difference between top down and bottom up parsing is that top down parsing performs the parsing from the staring symbol to the input string while bottom down parsing performs the parsing from input string to the starting symbol.

Reference:

1.“Compiler Design Lecture 5 — Introduction to Parsers and LL(1) Parsing.” Compiler Design Lecture 5 — Introduction to Parsers and LL(1) Parsing, Gate Lectures by Ravindrababu Ravula, 22 May 2014. Available here