Derivations & parse trees Role of a parser
Ambiguity
A grammar that produces more than one parse tree for some sentence is
said to be ambiguous, Put another way, an ambiguous grammar is one that
produces more than one leftmost or more than one rightmost derivation for the
same sentence. Carefully writing the grammar can eliminate ambiguity.
Elimination of Left
Recursion
A grammar is left recursion if it has a nonterminal A such that there
is a derivation A 
Aafor some string a. Top-Down
parsing method cannot handle left-recursion grammars, so a transformation that eliminates left recursion is needed. A
left-recursive pair of productions A 
A a could be replaced by the non-left-recursive
productions
A
bA'
A'
aA'| 
without changing the set of
strings derivable from A. This rule by itself suffices in many grammars.
No matter how many A-productions there are, we can eliminate immediate
left recursion from them by the follwing technique. First, we group the
A-productions as
A
Aa1| Aa 2|..........A am |b1|b2|........
|bn
where nobi begins with an A. Then, we replace the A-production by
A
b1A'|b2A'|........ |bnA'
A'
a1A'| a 2A'|.......... amA' |e
The nonterminal A generates the same strings as before but is no longer
left recursive.This procedure eliminates all immediate left recursion from the
A and A' productions , but it does not eliminate left recursion involving
derivation of two or more steps. For example, consider the grammar
S==>Aa|b
A==>Ac|Sd|e
The nonterminal S is left-recursive because S gives Aa gives Sda, but
it is not immediately left recursive.
Algorithm below will systematically eliminates left recursion from a grammar.
It is guaranteed to work if the grammar has no cycles or e productions
Cycles can be systematically eliminated from a grammar as can - e productions.
Algorithm Eliminating left recursion.
Input. Grammar with no
cycles or e-productions.
Output. An equivalent
grammar has no left recursion.
Method. Apply the
algorithm to G . Note that the resulting
non-left-recursive grammar may have e -productions.
1. Arrange the nonterminals in some order A1, A2, ,...........,An.
2. for i := 1 to n do
begin
for j: = 1 to i - 1 do begin
replace
each production of the form Ai==> Ajg
by the
productions Ai ==> d1g|d2g...............|dkg
where
Aj==>d1|d2|.........|dk are all current
Aj productions.
end
eliminate the
immediate left recursion among Ai productions
end
Left Factoring
Left factoring is a grammar transformation that is useful producing a
grammar suitable for predictive parsing. The basic idea is that when it
is not clear which of two alternative productions to use to expand a non
terminal A, we may rewrite the A-priductions to defer the decision until we
have seen enough of the input to make the right choice. If A==>ab1|ab2
are two A-productions and the input begins
with a non empty string derived from a , we do not know whether to
expand A toab1 or toab2. Wemay defer decision by
expanding A to
aA' . Then after
seeing the input derived from a we expand A' to b1or to b2
A==>aA'
A'==>b1|b2
Algorithm: left factoring a .grammar
Input. Grammar G
Output. An equivalent
left factored grammar.
method. For each non
terminal A find the longest prefix a common to two or more of
its alternatives. If a!= E, i.e., there is a non trivial common prefix,
replace all the A productins
A==>ab1|ab2|..............|abn|g
, where
g represents all alternatives that do not begin with a by
A==>aA'|g
A'==>b1b|2|.............|bn
Here A' is new nonterminal. Repeatedly apply this transformation until
no two alternatives for a non-terminal have a common prefix.
Derivations & parse trees Role of a parser