Top down approach tries to construct a leftmost derivation
for the given string
Top down parsing is constructing a parse tree for the input
starting from the root and create nodes of the parse tree in preorder (depth
first)
A general form of Top Down Parsing is the recursive descent
parsing
Top Down Parsing Algorithm
Construct the root node of the parse tree
Repeat until the leaves of the parse tree matches the input
string
- At a node labeled A, select a production with A on its left hand side and for each symbol on its right hand side, construct the appropriate child
- When a terminal symbol is added to the fringe and it doesn't match the fringe, backtrack
- Find the next node to expand
Top down parsing methods:
This method is broadly divided into
Backtracking
(Brute Force Method)
Predictive
Parser (without Backtrack)
Recursive
Descent
LL(1)
Parser
Input: ID + (ID + ID)
Build parse tree:
Start from start symbol to invoke: int input (void)
Home
|
