By: Prof. Dr. Fazal Rehman | Last updated: March 3, 2022
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
