Parsing - Introduction to Compiler Construction in a Java World - page 88

Example. Such grammars are not unusual. For example, the first context-free grammar
we saw (3.8) describes the same language as does the (LL(1)) grammar (3.21). We repeat
this grammar as (3.27).

E ::= E + T
E ::= T
T ::= T * F
T ::= F
F ::= ( E )
F ::= id

(3.27)

The left recursion captures the left-associative nature of the operators + and * . But
because the grammar has left-recursive rules, it is not LL(1). We may apply the left-recursion
removal rule (3.26) to this grammar.
First, applying the rule to E to produce

E ::= T E 0
E 0 ::= + T E 0
E 0 ::=

Applying the rule to T yields

T ::= F T 0
T 0 ::= * F T 0
T 0 ::=

Giving us the LL(1) grammar

E ::= T E 0
E 0 ::= + T E 0
E 0 ::=
T ::= F T 0
T 0 ::= * F T 0
T 0 ::=
F ::= ( E )
F ::= id

(3.28)

Where have we seen this grammar before?

Much less common, particularly in grammars describing programming languages, is in-
direct left recursion. Algorithm 3.6 deals with these rare cases.

Algorithm 3.6 Left Recursion Removal for a Grammar G = (N;T;S;P)
Input: a context-free grammar G = (N;T;S;P)
Output: G with left recursion eliminated
Arbitrarily enumerate the non-terminals of G : X 1 ;X 2 ;:::;X n
for i := 1 to n do
for j := 1 to i 1 do
Replace each rule in P of the form Xi i ::= X j by the rules Xi i ::= 1 j 2 j:::j k
where X j ::= 1 j 2 j:::j k are the current rules defining Xi i
Eliminate any immediate left recursion using (3.25)
end for
end for