Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Top-Down Parsing?
3.
Example of Top-Down Parsing
4.
Classification of Top-Down Parsing
5.
Recursive Descent Technique
5.1.
Back-tracking
5.1.1.
Example 
5.2.
Non- back-tracking
5.2.1.
Predictive Parser
5.2.2.
LL Parser
6.
Frequently Asked Questions
6.1.
What are the advantages of top-down parsing?
6.2.
What is top-down parsing with backtracking?
6.3.
What do you mean by top-down parsing?
6.4.
What are the types of top-down parsing?
6.5.
What is top-down parsing in compiler design with example?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Top Down Parsing

Author Muskan Gupta
2 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @
Top Down Parsing

Introduction

Syntax analysis or parsing is the process of analyzing the string of symbols using grammar rules. Parsing is divided into two types: bottom up parsing and top down parsing. It is breaking something down into its constituent parts, for example, breaking a sentence down to explain what its verb does. 

For data, the compiler unit performs the sequential parsing operation in top-down and bottom-up parsing after its tokenizer, lexer, or scanner has produced its tokens. 

This blog covers the concept of top down parsing along with its classification and topics such as Predictive Parser and LL Parser.

What is Top-Down Parsing?

Top-down parsing means parsing the input and constructing the parse tree, starting from the root and going down to the leaf. It uses left most derivation to build a parse tree. On the contrary, bottom-up parsing is based on reverse rightmost derivation. The function of top-down parsers is to construct from the grammar (free from left recursion and ambiguity). Top-down parsing allows the grammar free from left factoring.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example of Top-Down Parsing

Examples of top-down parsing algorithms include recursive descent parsing and LL parsing. Recursive descent parsing involves writing a set of recursive procedures to recognize the language of a grammar, while LL parsing involves building a predictive parsing table from a given grammar and using it to parse the input. Both of these techniques use a top-down approach to parse the input, starting with the highest-level nonterminal symbol and working downwards. Top-down parsing is useful for LL(1) grammars, which are a subset of context-free grammars, and is widely used in compiler construction and other applications involving the analysis of structured data.

Classification of Top-Down Parsing

Following is the flowchart that depicts the classification of top-down parsing:

      

Classification of top-down parsing

Classification of top-down parsing

Recursive Descent Technique

It is a technique of top-down parsing in which the construction of a parse tree happens from the top, and input is read from left to right. It uses CFG(context-free grammar ), which is why it is recursive. In this technique, procedures are used for each terminal and non-terminal entity. And, it parses the input recursively to make a parse tree with or without using back-tracking. But, if the associated grammar is not a left factor, it cannot avoid back-tracking. If this technique does not require back-tracking, it is known as predicate parsing. 

Back-tracking

If the derivation of the input string fails in one production of a non-terminal, then the parser has to return to the place where it has picked the production. And begin deriving the string likewise using another production of the exact non-terminal. The process may require repeatedly scanning over the input string, referred to it as back-tracking.

Example 

The following is a grammar rule:

S -> r P d

P -> m | m n

Input string: 'rmnd.'

Building the parse tree will start with the symbol S, and the input pointer is pointing to the first symbol of the given input string, 'r .'Since the start symbol 'S' has single production in its production body. So, the symbol 'S' will be expanded.

                                                                       

Illustration Image

The leftmost leaf of the tree 'r' matches with the first symbol of the string given in input which is 'r .'Thus, we will extend the input pointer to the next symbol of the input string, which is 'm'.

The next leaf of the parse tree 'P' has two production rules. Let's expand the symbol 'P' with the given first production of 'P,' i.e., 'm' we get the following parse tree.

                                                                         

Illustration Image

Here, the second input symbol, 'm', matches. So, we will extend the input pointer to the point next symbol of the input string, i.e., 'n.'

We get a mismatch when comparing the third input symbol 'n' against the next leaf labeled 'd'. Therefore, the parser must return to the symbol 'P' and look for the other alternative.

The other alternative for the production of 'P' is 'mn .'Also, the input pointer must be back-tracked and reset to the position where it was first before we expanded the symbol 'P .'It means the input pointer must point to 'm' again.

We will again expand 'P' with the following alternative production. The parse tree label 'm' leaf matches the second input symbol 'm'.
 

                                   

Illustration Image

 

So, the input pointer is extended and points to the third input symbol, 'n .'And the next leaf of the tree labeled 'n' matches the third input symbol.

Further, the input pointer is extended to point to the fourth input symbol 'd'. And this matches the next leaf of the tree labeled 'd'.

Non- back-tracking

The recursive Descent Technique parses the input to make a parse tree with or without using back-tracking. If the associated grammar is a left factor, it can use non-back-tracking.

Non-backtracking techniques include a predictive parser and an LL parser. They are explained below:

Predictive Parser

                                                   Predictive Parser

                                         Table-driven Predictive recursive parsing

Predictive parsing is a straightforward form of recursive descent parsing. And it does not requires back-tracking. Instead, it can determine which production must be selected to derive the input string. Predictive parsing selects the correct production by looking at the input string. It allows looking at a fixed number of input symbols from the input string.

Components of Predictive top-down parsing

Following are the components of predictive top-down parsing:-

Stack

A predictive parser sustains a stack, including a sequence of grammar symbols.

Input Buffer

It includes the input string that the predictive parser needs to parse.

Parsing Table 

With the entries present in this table, it becomes effortless for the top-down parser to choose the production to be applied. Input buffer and stack both include the end marker '$'. It denotes the bottom of the stack and the input string's end in the input buffer. In the beginning, the grammar symbol on the top of $ is the beginning symbol.

Steps to perform predictive parsing

The parser first views the grammar symbol present on the top of the stack saying 'X'. And compares it with the existing input symbol, say 'a' present in the input buffer.

  • If X is a non-terminal, then the parser selects a product of X from the parse table, conferring the entry M [X, a].
  • In case X is a terminal, then the parser scans it for a match with the present symbol' a'.

This is how predictive parsing recognizes the right production. In this way, it successfully derives the input string.

LL Parser

The LL parser is a predictive parser. It does not require back-tracking. LL (1) parser takes only LL (1) grammar.

  • First L in LL (1) implies that the parser scans the input string from left to right.
  • Second, L defines the leftmost derivation for the input string.
  • The '1' in LL (1) demonstrates that the parser lookahead a single input symbol from the input string.

LL (1) grammar does not comprise left recursion and no ambiguity.

Frequently Asked Questions

What are the advantages of top-down parsing?

a)Top-down parsing is very uncomplicated.
b)It is very easy to recognize the action conclusion of the top-down parser.

What is top-down parsing with backtracking?

Backtracking allows the parser to investigate various choices when the chosen production fails to match the input in top-down parsers, which start with the starting grammar symbol and recursively expand non-terminals.

What do you mean by top-down parsing?

Top-down parsing is a parsing technique in which the parser starts with the highest-level nonterminal symbol of the grammar and works downwards to derive the input string. It involves choosing a production rule for the current nonterminal symbol and recursively expanding it.

What are the types of top-down parsing?

There are two main types of top-down parsing: recursive descent parsing and LL parsing. Recursive descent parsing involves writing a set of recursive procedures. LL parsing, on the other hand, involves building a predictive parsing table from a given grammar.

What is top-down parsing in compiler design with example?

In compiler design, top-down parsing is a parsing technique that involves starting with the highest-level nonterminal symbol of the grammar and working downward to derive the input string. An example of top-down parsing is recursive descent parsing.

Conclusion

In this article, we have extensively discussed the concepts of top down parsing along with its classification and topics such as Predictive Parser and  LL Parser and frequently asked questions. 

We hope this blog has helped you enhance your knowledge regarding top down parsing and if you would like to learn more, check out our articles on the lexical-analysis-in-compiler-design

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Do upvote our blog to help other ninjas grow. Happy Coding!

Previous article
Syntax Analysis
Next article
LL Parser in Compiler Design
Live masterclass