Next: Left factoring
Up: Contextfree grammars
Previous: Elimination of ambiguity.
LEFT RECURSION.
Let G be a contextfree grammar.
A production of G is said left recursive if it has
the form
A A 
(20) 
where A is a nonterminal and
is a string of grammar symbols.
A nonterminal A of G is said left recursive
if there exists a string of grammar symbols
such that we have
A A 
(21) 
Such derivation is also said left recursive.
The grammar G is left recursive if it has
at least one left recursive nonterminal.
Remark 4
Topdown parsing is one of the methods that
we will study for generating parse trees.
This method cannot handle left recursive grammars.
We present now an algorithm for transforming
a left recursive grammar G into a grammar G' which is not
left recursive and which generates the same language as G.
THE BASIC TRICK is to replace the production
where
is assumed.
Observe that this trick eliminates left recursive productions.
Applying this trick is not enough to remove all derivations
of the form
A A.
However this trick is sufficient for many grammars.
THE CASE OF SEVERAL LEFT RECURSIVE APRODUCTIONS. Assume that the set of all Aproductions has the form
A A  A  ^{ ... }A    ^{ ... } 
(25) 
where no begins with an A and where
holds for every
i = 1^{ ... }m.
Then we repalce these Aproductions by
A 

A'  A'  ^{ ... } A' 
A' 

A'  A'  ^{ ... } A'  

(26) 
Remark 5
Let us consider the following grammar.
The nonterminal S is left recursive since we have
S Aa Sda 
(28) 
However there is no left recursive Sproductions.
We show now how to deal with these left recursive derivations.
REMOVING ALL LEFT RECURSIVE DERIVATIONS. Let us assume that nonterminals are numbered:
A_{1}, A_{2},..., A_{n}.
The goal is to remove any possible circuit for all
1 j < i n
The idea is for
i = 1^{ ... }n
 To make sure that every A_{i}production does
not have a form
A_{i} A_{j} for some j < i.
 To remove any left recursive A_{i}production.
The method in more detail:
 remove all left recursive A_{1}productions
(by the above trick)
 remove A_{1} from the righthand side of each
A_{2}production of the form
A_{2} A_{1}
(by applying all A_{1}productions)
 remove all left recursive A_{2}productions
 remove A_{j} from the righthand side of each
A_{3}production of the form
A_{3} A_{j}
for j = 1, 2.
 remove all left recursive A_{3}productions
 ...
 remove A_{j} from the righthand side of each
A_{i}production of the form
A_{i} A_{j}
(for every j such that
1 j < i n)
 remove all left recursive A_{i}productions
 ...
Observations:
Next: Left factoring
Up: Contextfree grammars
Previous: Elimination of ambiguity.
Marc Moreno Maza
20041202