Top-Down Parsing
Top-Down Parsing may be considered as an attempt to build a parse tree for an input string in preorder, that is starting from the root.
It can also be considered as an attempt to construct a leftmost derivation for an input string. A top-down parser constructs the leftmost derivation.
A top-down parser constructs the leftmost derivation from the start symbol of the grammar. Then, it selects a suitable production rule such that it can move the input string from the left to right in the sentential form.
If there is more than one production rule for a leftmost non-terminal, then the selection of production rule is dependent on whether the parse tree can backtrack, it can scan the input string repetitively and try out all the possibilities in the order until it has succeeded in parsing the string.
On the other hand, if backtracking is not permitted then the parser has to make the right selection of the production rule, which is a crucial task in such parsers.
Types of Top-Down Parsing
The different types of top-down parsing techniques are:
- Recursive Descent Parsing
- Non-Recursive Predictive Parsing
Reference Link