Compiler Design and Construction - Old Questions

5.  Explain in detail about the recursive-descent parsing with example.

Recursive decent parsing is a top-down parsing technique that uses a set of recursive procedure to scan its input from left to right. It may involve backtracking. It starts from the root node (start symbol) and use the first production, match the input string against the production rules and if there is no match backtrack and apply another rule.

Rules:

1. Use two pointers iptr for pointing the input symbol to be read and optr for pointing the symbol of output string that is initially start symbol S.

2. If the symbol pointed by optr is non-terminal use the first production rule for expansion.

3. While the symbol pointed by iptr and optr is same increment the both pointers.

4. The loop at the above step terminates when

    a. A non-terminal is encountered in output 

    b. The end of input is reached. 

    c. Symbol pointed by iptr and optr is unmatched.

5. If 'a' is true, expand the non-terminal using the first rule and goto step 2

6. If 'b' is true, terminate with success

7. If 'c' is true, decrement both the pointers to the place of last non-terminal expansion and use the next production rule for non-terminal

8. If there is no more production and 'b' is not true report error.

Example:

Consider a grammar

S → cAd

A → ab | a

Input string is “cad”

Initially, iptr = optr = 0