Recursive Descent Parser in Compiler Design

Predictive Parser - Recursive Descent Parser (RDP)

A parser that uses a set of recursive procedures to recognize its input with no backtracking is called a recursive descent parser

For implementing a recursive descent parser for a grammar.

• The grammar must not be left recursive
• The grammar must be left factored that means it should not have common prefixes for alternates
• We need a language that has recursion facility

Left factoring Problems:

Eliminate Left recursion and then left factor the following grammar

                rexpr → reexpr + rterm | rterm

                rterm → rterm rfactor | rfactor

                rfactor → rfactor* | rprimary

                rprimary → a | b

Design:

• It can be written on the same lines as that of brute force approach that is one procedure for one non terminal
• The procedures need not return anything because they need not try another alternate as in brute force
• Only on failure we call some error routine to take care of the error

On can make use of different type of transition diagrams for designing a recursive descent parser as used in case of scanners.
The differences are

• There is one transition diagram for one non terminal
• The labels for edges may be terminals or non terminals
• Label is a terminal which means we must take that transition if the next input symbol is terminal

After elimination of left recursion and left factoring one can construct the transition diagram for the grammar as,
For each non-terminal A,

• Create an initial and final states
• For each production A → X₁, X₂,....X_n, create a path from initial to the final state with edges labeled X₁, X₂, .... X_n

Note:
If the transition diagram so constructed has non determinism, then a recursive descent parser can't be constructed for the grammar

Example:
Consider the Grammar
E → TE'
E' → +TE' | ε
T → FT'
T' → *FT' | ε
F → (E) | id
The transition diagrams for this grammar are:

As there is no non-determinism in the transition diagram the code for parser is:

We can further improve on the transition diagrams to better code the parser as, transition diagram for E' can be transformed as

Now E can be modifies as

After applying the same technique on T' and T, the final diagrams are:

Now, the code for these transition diagrams runs faster than the code written for the original transition diagram.

Now the code for parser is, from these reduced transition diagrams

Advantage:

• Easy to hand construct a recursive descent parser from an appropriate grammar

Limitations

• Recursive descent parser encodes state information in its run-time stack, or call stack, and this may not be particularly efficient
• Uses recursive procedure calls to implement a stack abstraction
• It is very difficult to automated

Backtracking

Home

Predictive Parser - LL(1)