- A top down parsing that executes a set of recursive procedure to process the input without backtracking is called recursive decent parser
- There is a procedure for each non terminal in the grammar
- Consider RHS of any production rule as definition of the procedure
- As it reads expected input symbol, it advances input pointer to next position
Example:
E->T {+T}* T->V{*V}* V-> id
Procedure proc_E: (tree_root);
var
a, b : pointer to a tree node;
begin
proc_T(a);
While (nextsymb = ‘+’) do
nextsymb = next source symbol;
proc_T(b);
a= Treebuild (‘+’, a, b);
tree_root= a;
return;
end proc_E;
Procedure proc_T: (tree_root);
var
a, b : pointer to a tree node;
begin proc_V(a);
While (nextsymb = ‘*’) do
nextsymb = next source symbol;
proc_V(b);
a= Treebuild (‘*’, a, b);
tree_root= a;
return;
end proc_T;
[wp_ad_camp_1]
Procedure proc_V: (tree_root);
var
a : pointer to a tree node;
begin If (nextsymb = ‘id’)
then nextsymb = next source symbol;
tree_root= tree_build(id, , );
else print “Error”;
return;
end proc_V;
Advantages
- It is exceptionally simple
- It can be constructed from recognizers simply by doing some extra work
Disadvantages
- It is time consuming method
- It is difficult to provide good error messages