TOP-DOWN PARSING, RECURSIVE -DESCENT
PREDICTIVE PARSING
Top-down parsing:
The top down construction of a parse tree is done by starting with the
root ,labeled with the starting non-terminal ,and repeatedly performing the
following two steps-
1. at node n, labeled with non-terminal A,select one of the productions for A
and construct
children at n for the symbols on the right side of the production
2. Find the next node at which the subtree is constructed.
For some grammars, the above steps can be implemented during a single left
to right scan of the input string. The current token being scanned on the input
is often called as the lookahead symbol . Initially the lookahead symbol is the
first i.e the leftmost token of the input string.
Let us consider the following grammar.
A -> BA
|a
| aa
B -> BB
|b
and now consider the input string “ bbaa”
The top-down parsing would look like this in different steps-
1. A
input : bbaa , the highlighted character indicates the lookahead.
2. A
, B A
3. A
B A
B B
4. A
B A
B B
b
5. input: bbaa
A
B A
B B
b b
6. input: bbaa A
B A
B B a a
b b
Here we have assumed that , at the first attempt the parser would know
which production to use to get the right output, but in general, the selection of a
production of a non-terminal may involve trial and error, that is we may have to
try a production and backtrack to try another production if the first is found to
be unsuitable. A production is unsuitable ,if after using the production, we
cannot complete the tree to match the input string .we will discuss this parsing
PREDICTIVE PARSING
Top-down parsing:
The top down construction of a parse tree is done by starting with the
root ,labeled with the starting non-terminal ,and repeatedly performing the
following two steps-
1. at node n, labeled with non-terminal A,select one of the productions for A
and construct
children at n for the symbols on the right side of the production
2. Find the next node at which the subtree is constructed.
For some grammars, the above steps can be implemented during a single left
to right scan of the input string. The current token being scanned on the input
is often called as the lookahead symbol . Initially the lookahead symbol is the
first i.e the leftmost token of the input string.
Let us consider the following grammar.
A -> BA
|a
| aa
B -> BB
|b
and now consider the input string “ bbaa”
The top-down parsing would look like this in different steps-
1. A
input : bbaa , the highlighted character indicates the lookahead.
2. A
, B A
3. A
B A
B B
4. A
B A
B B
b
5. input: bbaa
A
B A
B B
b b
6. input: bbaa A
B A
B B a a
b b
Here we have assumed that , at the first attempt the parser would know
which production to use to get the right output, but in general, the selection of a
production of a non-terminal may involve trial and error, that is we may have to
try a production and backtrack to try another production if the first is found to
be unsuitable. A production is unsuitable ,if after using the production, we
cannot complete the tree to match the input string .we will discuss this parsing
