Explain recursive descent parsing with example

Recursive Descent Parsing

Recursive-descent parsing is a top-down parsing technique where we write a set of recursive procedures, one for each non-terminal in the grammar. These procedures attempt to parse the input by applying productions and matching input symbols.

Key Points from the PDF

• It builds the parse tree top-down, starting from the start symbol.
• It follows the grammar rules to derive the input string.
• At each step, the parser chooses a production for a non-terminal and tries to match the input.
• Backtracking may be required if the wrong choice is made.

Example

Grammar:

S → cAd  
A → ab | ad

Input string: cad

Step-by-step parsing:

1. Start with S → cAd
   • Match c with first input symbol c
   • Move to parsing A
2. A → ab is tried first:
   • Match a with input
   • Now input has d, but expected b ⇒ Mismatch
3. Backtrack and try A → ad:
   • Match a
   • Match d

So, final derivation:
S → cAd → ca d d

Parser accepts the string cad.

Note on Left Recursion:

• A grammar like A → Aα | β (left-recursive) can cause an infinite loop in recursive descent.
• Such grammars must be restructured before applying this parsing method.

Summary

• Recursive-descent parsing is simple and intuitive.
• Requires no table, just a set of procedures.
• Suitable for LL(1) grammars (i.e., no left recursion or ambiguity).
• Can include backtracking, though it’s inefficient.
• Predictive parsers (a type of recursive-descent parser) avoid backtracking by using lookahead and FIRST/FOLLOW sets.