## Recursive Decent Parsing

Again Freestudy9 comes back with new post related to Recursive Decent Parsing. Similarly, we had tried to make it easy.

- 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 a definition of the procedure.
- As it reads the expected input symbol, it advances input pointer to the next position.

**Example of Recursive Decent Parsing**

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);roc_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);roc_V(a);

While (nextsymb = ‘*’) do

nextsymb = next source symbol;

proc_V(b);

a= Treebuild (‘*’, a, b);

tree_root= a;

return;

end proc_T;

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: Recursive Decent Parsing**

- It is exceptionally simple.
- So It can be constructed from recognizers simply by doing some extra work.

**Disadvantages: Recursive Decent Parsing**

- It is the time-consuming method.
- Moreover, It is difficult to provide good error messages.

**Terms: Recursive Decent Parsing**

- Augmented grammar: If grammar G having start symbol S then augmented grammar is the new grammar G’ in which S’ is a new start symbol such that S’ -> .S> .S.
- Kernel items: It is a collection of items S’ .S and all the items whose dots are not at the S’->S left the most end of the RHS of the rule.
- Non-Kernel items: It is a collection of items in which dots are at the leftmost end of that RHS of the rule.
- Viable prefix: It is a set of a prefix in right sentential form of the production A α, this settA->can appear on the stack during a shift-reduce action.

**Related Search**

Compiler Design, DFA without Constructing NFA, Front end and Back end, Free Study.

## Leave a Reply