Top-Down Parsing

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.

Recursive Descent Parsing

Recursive descent is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to right. It uses procedures for every terminal and non-terminal entity. This parsing technique recursively parses the input to make a parse tree, which may or may not require back-tracking. But the grammar associated with it (if not left factored) cannot avoid back-tracking. A form of recursive-descent parsing that does not require any back-tracking is known as predictive parsing.






Example (backtracking)
Consider the grammar
S ? cAd
A ? ab | a (Grammar 1)
and the input string w = cad
· To construct a parse tree for this string using top-down approach, initially create a tree consisting of a single node labeled S.


Fig 2

· An input pointer points to c, the first symbol of w.
· Then use the first production for S to expand the tree and obtain the tree (as in Fig 2(a)
· The leftmost leaf, labeled c, matches the first symbol of w.
· Next input pointer to a, the second symbol of w.
· Consider the next leaf, labeled A.
· Expand A using the first alternative for A to obtain the tree (as in Fig 2(b)).
· Now have a match for the second input symbol. Then advance to the next input pointer d, the third input symbol and compare d against the next leaf, labeled b. Since b does not match d, report failure and go back to A to see whether there is another alternative. (Backtracking takes place).
· If there is another alternative for A, substitute and compare the input symbol with leaf.
· Repeat the step for all the alternatives of A to find a match using backtracking. If match found, then the string is accepted by the grammar. Else report failure.
· A left-recursive grammar can cause a recursive-descent parser, even one with backtracking, to go into an infinite loop.