3.2.1 Recursive Descent Parsing

Consider the transformed CFG G1 again:

E ::= T E'
E' ::= + T E'
     | - T E'
     |
T ::= F T'
T' ::= * F T'
     | / F T'
     |
F ::= num
    | id

Here is a C program that parses this grammar:

E () { T(); E'(); }
E' () {
  if (current_token == PLUS)
     { read_next_token(); T(); E'(); }
  else if (current_token == MINUS)
     { read_next_token(); T(); E'(); };
}
T () { F(); T'(); }
T'() {
  if (current_token == TIMES)
     { read_next_token(); F(); T'(); }
  else if (current_token == DIV)
     { read_next_token(); F(); T'(); };
}
F () {
  if (current_token == NUM || current_token == ID)
     read_next_token();
  else error();
}

In general, for each nonterminal we write one procedure; For each nonterminal in the rhs of a rule, we call the nonterminal's procedure; For each terminal, we compare the current token with the expected terminal. If there are multiple productions for a nonterminal, we use an if-then-else statement to choose which rule to apply. If there was a left recursion in a production, we would have had an infinite recursion.

Please look at the following web page for a demo of the recursive descent algorithm using Java aplets: http://opal.cs.binghamton.edu/~zdu/parsdemo/recframe.html