Top Down Parser constructs Parse tree starting from Root and proceeding towards Leaf node.
Top-Down Parser uses Left Most Derivation(L.M.D).
for example-
S -> AB
A -> a
B -> b
Types of Top-Down Parser-
Backtracking(Brute Force Method)-:
Backtracking is a technique in which for expansions of Non-terminal symbols we choose one alternative and if some mismatch happens then we try another alternative if any.
for example:
S -> rXd | rZd
X -> oa | ea
z -> ai
From the given grammar we have to check that the string " re ad " is a member of the given grammar or not?
from starting symbol S(because it is Top-Down Parser) we will start here and write its first alternative S -> rXd -
from X its first Alternate is X -> oa , we add that production in the parse tree -
Since from the first alternative, we can't get our desired string. Then Backtrack on the symbol X again. Now add another alternative i.e. X -> ea.
Adding that production on the parse tree.
Finally, we get our desired string " read ".
Time Complexity:
The Time Complexity of Backtracking is O(2^n) which is exponential.