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.