Types of Top down Parsing

The compiler universe is quite wide and intriguing. From concepts like compiler design to input buffering in compiler design to parsing, you will come across several useful concepts.

One such concept that we are going to discuss in this blog post is top-down parsing!

Top-down parsing is considered to be a crucial concept of compiler design!

When it comes to top-down parsing, a parse tree is created from top till bottom. These roots are considered as the starting grammar symbols.

Did you know that the parser is touted to be the phase of a compiler that takes the token string as the input to convert it into an ideal representation.

Moreover, when we discuss top-down parsing, there is no chance of leaving its vital categories.

In this blog post, we have discussed in detail about the categories of top-down parsing and their uses.

Read till the end of this blog to fill your knowledge gap!

Top-down parsing - an overview

Parsing or syntax analysis is considered as the process to analyse the symbols by using grammar rules. It is mainly divided into bottom-up and top-down parsing. It breaks down things into its constituent parts. For instance; breaking a given sentence to explain its verbs.

The compiler unit also performs parsing operations in the bottom-up and top-down manner. When we talk about top-down parsing, it means parsing the required input to construct a parse tree by starting it from the root. Then goes down till leaf.

It then uses the leftmost derivation for building a tree. Take a look at the example given below:

Let's look at a recursive descent parser which involves the set of several instructions to recognize grammatical language. Though, the LL parser builds a parsing table from grammar and uses it as the input. Both these techniques will make the use of top-down approach in an aligned order.

Types of top down parsing

In compiler design, the term top-down parsing is defined as a software application where parsing generally occurs at the compilation stage. There are various crucial categories of top-down parsing that every computer aspirant should know to enhance their knowledge arena.

When we discuss the types of top down parser, it is generally of below-mentioned types:

Recursive descent technique

It is a popular top-down parsing technique where we construct a parse tree that happens to be at the top and read the input from left to right. It also uses the concept of context-free grammar which is considered to be recursive.

Here, in the case of a recursive descent parser, procedures are termed as terminal or non-terminal entities. It will parse an input recursively in order to parse a tree that is associated with the grammar. Though, it cannot avoid the concept of backtracking.

Back-tracking

If a derivation in an input string fails in case of non-terminal, the parser will get returned to its place in order to pick the production. To begin the derivation in case of string, you will use the production of a non-terminal.

The process will be repeated to scan the input string and is referred to as the process of backtracking.

For example;

Consider this grammar rule;

S -> rPd

P - > m / m n

The input string would be rmnd

Read more...