11

Recursive descent parsing associates a procedure with each nonterminal in the grammar, it may require backtracking of the input string.

The simplest parsing method, for a large subset of context free grammars, is called recursive descent. It is simple because the algorithm closely follows the production rules of nonterminal symbols.
- Write 1 procedure per nonterminal rule


- Within each procedure,

a) match terminals at appropriate positions, and

b) call procedures for non-terminals.


- Pitfalls: left recursion is FATAL; must distinguish between several production rules, or potentially, one has to try all of them via backtracking. In particular provide a high-level general algorithm for how the terminal & nonterminal symbols are handled.

EXAMPLE:

The grammar

S -> A B C
A -> a A
A -> epsilon
B -> b
C -> c
maps to code like

procedure S()
  if A() & B() & C() then succeed
end

procedure A()
  if currtoken == a then # use production 2
     currtoken = scan()
     return A()
  else
     succeed # production rule 3, match epsilon
end

procedure B()
   if currtoken == b then
      currtoken = scan()
      succeed
   else fail
end

procedure C()
   if currtoken == c then
      currtoken = scan()
      succeed
   else fail
end