254 ~ Theory of Computer Science
In Examples 7.10 and 7.11 for getting a leftmost derivation, one
production among several choices was obtained by look ahead for k symbols.
This kind of nondeterminism cannot be resolved in some grammars even by
looking ahead.
This is the case when a grammar has two A-productions of the form A ~
a{3 and A ~ ay. By a technique called 'left factoring', we resolve this
nondeterminism. Another troublesome phenomenon in a context-free grammar
which creates a problem is called left recursion. A variable A is called left
recursive if there is an A-production of the form A ~ Aa. Such a production
can cause a top-down parser into an infinite loop. Left factoring and technique
for avoiding left recursion are provided in Theorems 7.6 and 7.7.
Theorem 7.6 Let G be a context-free grammar having two A-productions of
the form A ~ a{3 and A ~ ay. If A ~ a{3 and A ~ ay are replaced by
A ~ aA'. A' ~ {3 and A' ~ Y. where A' is a new variable then the resulting
grammar is equivalent to G.
Proof The equivalence can be proved by showing that the effect of applying
A ~ a{3 and A ~ ay in a derivation can be realised by applying A ~ aA',
A' ~ {3 and A' ~ Y and vice versa.
Note: The technique of avoiding nondeterminism using Theorem 7.6 is
called left factoring.
Theorem 7.7 Let G be a context-free grammar. Let the set of all
A-productions be {A ~ Aa 1 , ... , A ~ Aa,;' A ~ {31' .... A ~ {3m}. Then
the grammar G' obtained by introducing a new vmiable A' and replacing all
A-productions in G by A ~ {31A', ..., A ~ {3I1A', A' ~ a]A', ..., A' ~ a;A'
and A' ~ A is equivalent to G.
Proof Similar to proof of Lemma 6.3.
Theorems 7.6 and 7.7 are useful to construct a top-down parser only for
certain context-free grammars and not for all context-free grammars. We
summarize our discussion as follows:
Construction of Top-Down Parser
Step 1 Eliminate left recursion in G by repeatedly applying Theorem 7.7 to
all left recursive vmiables.
Step 2 Apply Theorem 7.6 to get left factoring wherever necessary.
Step 3 If the resulting grammar is LL(k) for some natural number k, apply
top-down parsing using the techniques explained in Examples 7.10 and 7.11.
EXAMPLE 7.12
Consider the language consisting of all arithmetic expressions involving +, '\
( and) over the variables xl and x2. This language is generated by a grammar
In Examples 7.10 and 7.11 for getting a leftmost derivation, one
production among several choices was obtained by look ahead for k symbols.
This kind of nondeterminism cannot be resolved in some grammars even by
looking ahead.
This is the case when a grammar has two A-productions of the form A ~
a{3 and A ~ ay. By a technique called 'left factoring', we resolve this
nondeterminism. Another troublesome phenomenon in a context-free grammar
which creates a problem is called left recursion. A variable A is called left
recursive if there is an A-production of the form A ~ Aa. Such a production
can cause a top-down parser into an infinite loop. Left factoring and technique
for avoiding left recursion are provided in Theorems 7.6 and 7.7.
Theorem 7.6 Let G be a context-free grammar having two A-productions of
the form A ~ a{3 and A ~ ay. If A ~ a{3 and A ~ ay are replaced by
A ~ aA'. A' ~ {3 and A' ~ Y. where A' is a new variable then the resulting
grammar is equivalent to G.
Proof The equivalence can be proved by showing that the effect of applying
A ~ a{3 and A ~ ay in a derivation can be realised by applying A ~ aA',
A' ~ {3 and A' ~ Y and vice versa.
Note: The technique of avoiding nondeterminism using Theorem 7.6 is
called left factoring.
Theorem 7.7 Let G be a context-free grammar. Let the set of all
A-productions be {A ~ Aa 1 , ... , A ~ Aa,;' A ~ {31' .... A ~ {3m}. Then
the grammar G' obtained by introducing a new vmiable A' and replacing all
A-productions in G by A ~ {31A', ..., A ~ {3I1A', A' ~ a]A', ..., A' ~ a;A'
and A' ~ A is equivalent to G.
Proof Similar to proof of Lemma 6.3.
Theorems 7.6 and 7.7 are useful to construct a top-down parser only for
certain context-free grammars and not for all context-free grammars. We
summarize our discussion as follows:
Construction of Top-Down Parser
Step 1 Eliminate left recursion in G by repeatedly applying Theorem 7.7 to
all left recursive vmiables.
Step 2 Apply Theorem 7.6 to get left factoring wherever necessary.
Step 3 If the resulting grammar is LL(k) for some natural number k, apply
top-down parsing using the techniques explained in Examples 7.10 and 7.11.
EXAMPLE 7.12
Consider the language consisting of all arithmetic expressions involving +, '\
( and) over the variables xl and x2. This language is generated by a grammar