Do you think IIT Guwahati certified course can help you in your career?
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.
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
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.
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.
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'.
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
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.
83+ registered 