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 Java program that parses this grammar:

static void E () { T(); Eprime(); }
static void Eprime () {
  if (current_token == PLUS)
     { read_next_token(); T(); Eprime(); }
  else if (current_token == MINUS)
     { read_next_token(); T(); Eprime(); };
}
static void T () { F(); Tprime(); }
static void Tprime() {
  if (current_token == TIMES)
     { read_next_token(); F(); Tprime(); }
  else if (current_token == DIV)
     { read_next_token(); F(); Tprime(); };
}
static void 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://www.upb.de/cs/ag-kastens/uebi/parsdemo/