Consider the transformed CFG G1 again:

E ::= T E' E' ::= + T E' | - T E' | T ::= F T' T' ::= * F T' | / F T' | F ::= num | idHere 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

2002-08-26