Recursive Descent Parsing and Backtracking

Recursive Descent Parsing
Recursive Descent Parsing

Recursive Descent Parsing is the top-down parsing technique.

Back-tracking

Top-down parsers start from the root node (For example, with a start symbol S) and match the input string with the production rules to replace them. To understand it in an easy way, Suppose we have a CFG.

S → mXn | mZn

X → pq | sq

Z → qr

Suppose we want to read a string of “msqn” from the give CFG. Figure shows how Recursive Descent Parsing works with Backtracking if the machine does not read the correct alphabet.

Recursive Descent Parsing and Backtracking
Recursive Descent Parsing and Backtracking

Predictive Parsing

In predictive parsing, the compiler does not require any back-tracking.

Prof. Fazal Rehman Shamil