Recursive Descent Parsing

In this class, We discuss Recursive Descent Parsing.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of syntax analysis basics. Click Here.

The recursive descent parsing is a top-down method.

The recursive descent parsing uses backtracking.

First, We will take a simple example and understand recursive descent parsing.

The concept is extended to the example CFG used previously to identify statements and expressions.

The below example is simple context-free grammar.

S – aAb

A – ab | a

In our example, S and A are non-terminals.

In recursive descent parsing, we write a function for each non-terminal.

The below example shows the function for non-terminal S.

We write a loop to choose each production in the non-terminal.

In the loop, we write a condition to check the productions.

The second loop will take the symbols in the production one by one and check the conditions.

We call the function related to non-terminal if the symbol is non-terminal.

Suppose the symbol is terminal check the match for the input symbol. If input matches, move one step on input.

We stop checking the current production if the input is not matched. We take the next production and continue.

If all the productions fail, we stop and return an error message.

Here we are going back and taking the next production is called backtracking.

Understanding Back Tracking with an example:

The below example shows the backtracking example.

The input string is chosen, cad.

The first tree checks for the input symbol ‘c’ and its matches.

The second tree is expanding with the production S – ab.

The production S – ab is not matching the input string.

So backtrack and take the next production.

After backtracking, the production S – a is matching to input cad.

Example Expression Grammar.

The below example shows the CFG to identify expressions.

We write functions for each non-terminal.

Problem with Recursive Descent Parsing:

In our previous class, we wrote CFG to find four different pascal language statements.

Similarly, Think complexity to writing CFG for identifying all the statements symbols in the C programming language.

How many functions should be written?

Recursively calling many functions lead to space constraint.