Difference Between Top Down and 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.

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.

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. 

What is Bottom Up Parsing?

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.

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.

What is the Difference Between Top Down and Bottom Up Parsing?

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.

Summary – Top Down vs Bottom Up Parsing

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