Top-down parser generator

Parsing is classified into two categories, i.e. Top-Down Parsing, and Bottom-Up Parsing. Top-Down Parsing is based on Left Most Derivation whereas Bottom-Up Parsing is dependent on Reverse Right Most Derivation.

The process of constructing the parse tree which starts from the root and goes down to the leaf is Top-Down Parsing.

1. Top-Down Parsers constructs from the Grammar which is free from ambiguity and left recursion.
2. Top-Down Parsers uses leftmost derivation to construct a parse tree.
3. It allows grammar that is free from Left Factoring.

Classification of Top-Down Parsing

1. With Backtracking: Brute Force Technique

2. Without Backtracking:

1. Recursive Descent Parsing
2. Predictive Parsing or Non-Recursive Parsing or LL[1] Parsing or Table Driver Parsing

Recursive Descent Parsing

1. Whenever a Non-terminal spend the first time then go with the first alternative and compare it with the given I/P String
2. If matching doesnt occur then go with the second alternative and compare with the given I/P String.
3. If matching is not found again then go with the alternative and so on.
4. Moreover, If matching occurs for at least one alternative, then the I/P string is parsed successfully.

LL[1] or Table Driver or Predictive Parser

1. In LL1, first L stands for Left to Right and second L stands for Left-most Derivation. 1 stands for a number of Look Ahead tokens used by parser while parsing a sentence.
2. LL[1] parsing is constructed from the grammar which is free from left recursion, common prefix, and ambiguity.
3. LL[1] parser depends on 1 look ahead symbol to predict the production to expand the parse tree.
4. This parser is Non-Recursive.

Video liên quan