TOC Lecture-10
Ambiguity in
Context Free Grammar
Parsing and Ambiguity
• A terminal string may be generated by a number of different
derivations.
• Let G be a CFG. A string w is in L(G), iff there is
*
− a leftmost derivation of w from S. (S w)
• Question
− Is there a unique leftmost derivation of every sentence
(string) in the language of a grammar?
NO
Parsing and Ambiguity: Example
• Consider the expression grammar:
E E + E | E * E | (E) | -E | id
• Two different leftmost derivations of id + id * id
E E+E E E*E
id + E E+E*E
id + E * E id + E * E
id + id * E id + id * E
id + id * id id + id * id
E E
E + E E * E
id E * E E + E id
id id id id
Parsing and Ambiguity
• A CFG is ambiguous if there is a string w L(G) that can be
derived by two distinct leftmost derivations.
• A grammar G is ambiguous if there exists a sentence in G
with more than one derivation (parsing) tree.
• A grammar that is not ambiguous is called unambiguous.
• If G is ambiguous then L(G) is not necessarily ambiguous.
• A language L is inherently ambiguous if there is no
unambiguous grammar that generates it.
Parsing and Ambiguity
• Let G be S aS | Sa | a
• G is ambiguous since the string aa has 2 distinct leftmost
derivation
– S aS aa
– S Sa aa05
• L(G) = a+
• This language is also generated by the unambiguous grammar
S aS | a
Parsing and Ambiguity
• Let G be S bS | Sb | a and L(G) = b*ab*
• G is ambiguous since the string bab has 2 distinct leftmost
derivation
– S bS bSb bab
– S Sb bSb bab
• The ability to generate the b’s in either order must be
eliminated to obtain an unambiguous grammar.
• This language is also generated by the unambiguous
grammars:
G1: S bS | aA G2: S bS | A
A bA | A Ab |
Parsing and Ambiguity
• Consider the following grammar
E E + E | E * E | num
• Consider the sentence 1 + 2 * 3
• Leftmost Derivation-1 E
E E+E
E + E
1+E
1+E*E 1 E * E
1+2*E
1+2*3 2 3
• Leftmost Derivation-2 E
E E*E
E+E*E E * E
1+E*E E + E 3
1+2*E
1+2*3 1 2
Parsing and Ambiguity
• Different parse trees correspond to different evaluations
(meaning).
LMD-1 LMD-2
+ *
+
*
1 2 3 1 2 3
=7 =9
Eliminating Ambiguity
• Ambiguous: E E + E | E * E | num
• Both + and * have the same precedence
• To remove ambiguity, we have to give + and * different
precedence
• Let us say * has higher precedence than +
– E E+T | T
– T T * num | num
Eliminating Ambiguity
• E E+T | T
• T T * num | num
• Consider the sentence 1 + 2 * 3
• Leftmost Derivation (only one LMD)
E
E E+T
T+T E + T
num + T T T * num
1+T
3
1 + T * num num num
1 + num * num 1 2
1 + 2 * num
=7
1+2*3
Eliminating Ambiguity
• Let us say + has higher precedence than *
– E E*T | T
– T T + num | num
• Consider the sentence 1 + 2 * 3
• Leftmost Derivation (only one LMD)
E
E E*T
E * T
T*T
T + num * T T num
num + num * T
1 + num * T T + num 3
1+2*T num 2
1 + 2 * num =9
1+2*3 1
CFGs & Programming Languages
• Programming languages are context-free, but not regular.
• Programming languages have the following features that
require infinite “stack memory”.
− matching parentheses in algebraic expressions
− nested if .. then .. else statements
− nested loops
− block structure
CFGs & Programming Languages
<unsigned constant> <unsigned number>
<constant> <unsigned number> | <sign> <unsigned number>
<unsigned number> <unsigned integer> | <unsigned real>
<unsigned integer> <digit> <unsigned integer> | <digit>
<unsigned real> <unsigned integer> . <unsigned integer> |
<unsigned integer> . <unsigned integer> E <exp> |
<unsigned integer> E <exp>
<exp> <unsigned integer> | <sign> <unsigned integer>
<digit> 0|1|2|3|4|5|6|7|8|9
<letter> a|b|c|…|y|z|A|B|C|…|Y|Z
<sign> +|-
CFGs & Programming Languages
<identifier> <letter> <identifier tail>
<identifier tail> <letter> <identifier tail> | <digit> <identifier tail>
<expression> <simple expression>
<simple expression> <term> | <sign term> |
<simple expression> <adding operator> <term>
<term> <factor> |
<term> <multiplying operator> <factor>
<factor> <variable> | <unsigned constant> |
(<expression>)
<adding operator> +|-
<multiplying operator> * | / | div | mod
Important Points
• If a context free grammar G is ambiguous, language generated by
grammar L(G) may or may not be ambiguous.
• It is not always possible to convert ambiguous CFG to unambiguous
CFG. Only some ambiguous CFG can be converted to unambiguous
CFG.
• There is no algorithm to convert ambiguous CFG to unambiguous
CFG.
• There always exist a unambiguous CFG corresponding to
unambiguous CFL.
• Deterministic CFL are always unambiguous.
Question-1
• Check whether the given grammar G is ambiguous or not.
A AA
A (A)
Aa
• Solution: For the string "a(a)a" the above grammar can generate
two parse trees:
A AA A AA
aA AAA
aAA aAA
a(A)A a(A)A
a(a)A a(a)A
a(a)a a(a)a
Question-2
• Show that the given grammar is ambiguous. Also, find an equivalent
unambiguous grammar.
S S+S | S*S | S^S | a
• Solution: For the string "a + a * a" the above grammar can generate two
parse trees:
Derivation -1 Derivation -2 Unambiguous Grammar
S S+S S S*S S S+T| T
a+S S+S*S T F*T| F
a+S*S a+S*S
a+a*S a+a*S F G^F| G
a+a*a a+a*a Ga
Types of Grammar
Types of Grammar
• On the basis of number of strings, grammars are classified as:
1. Recursive Grammar
2. Non-Recursive Grammar
Recursive Grammar
• A grammar is said to be recursive if it contains at least one
production that has the same variable at both its LHS and
RHS.
OR
• A grammar is said to be recursive if and only if it generates
infinite number of strings.
• Two types:
1. Left recursive grammar
2. Right recursive grammar
Left Recursive Grammar
• A recursive grammar is said to be left recursive if the leftmost
variable of RHS is same as variable of LHS.
OR
• A recursive grammar is said to be left recursive if it has Left
Recursion.
• Example:
A Aα | β
Right Recursive Grammar
• A recursive grammar is said to be right recursive if the
rightmost most variable of RHS is same as variable of LHS.
OR
• A recursive grammar is said to be left recursive if it has Right
Recursion.
• Example:
A αA | β
Problem of Left Recursion
A Aα | β A βα*
A
A α A( )
{
A α
A( );
α;
A α
}
β
The function A( ) recursively calls itself without
checking any condition Infinite loop!
Solution of Left Recursion
Left Recursion Right Recursion
A Aα | β A βα* A αA | β A α*β
A( ) A( )
{ {
A( ); α;
α; A( );
} }
Conversion of Left Recursive to Right Recursive Grammar
A Aα | β A βα*
A β A’ A A
A α A’ | λ β A’ β A’
α A’
λ
α A’
λ
Important Notes
• The grammar which is either left recursive or right recursive is
always unambiguous.
– Examples:
S aS | b (Unambiguous Grammar)
S Sa | b (Unambiguous Grammar)
• The grammar which is both left recursive and right recursive is
always ambiguous.
– Example:
E E + E | E - E | E * E | id (Ambiguous Grammar)
• Left recursive grammar is not suitable for Top down parsers.
– This is because it makes the parser enter into an infinite loop.
Question-1
• Eliminate the left recursion:
P P+Q|Q
• Solution:
P QP’
P’ +QP’ | λ
Question-2
• Eliminate the left recursion:
S S 0 S 1 S | 01
• Solution:
S 01S’
S’ 0 S 1 S S’ | λ
Question-3
• Eliminate the left recursion:
A (B) | b
B B*A|A
• Solution:
A (B) | b
B AB’
B’ * AB’ | λ
Question-4
• Eliminate the left recursion:
A Aα1 | Aα2 | Aα3 | . . . | β1 | β2 | β3 | . . .
• Solution:
A β1 A’ | β2 A’ | β3 A | . . .
A’ α1 A’ | α2 A’ | α3 A’ | . . . | λ
Question-5
• Eliminate the left recursion:
X X1 | Y1 | 0
Y Y0 | X1 | 0
• Solution:
X Y 1 X’ | 0 X’
X’ 1 X’ | λ
Y 0 X’ 1 Y’
Y’ 0 Y’ | 1 X’ 1 Y’ | λ
Non-Recursive Grammar
• A grammar is said to be non-recursive if it contains no production
that has the same variable at both its LHS and RHS.
OR
• A grammar is said to be non-recursive if and only if it generates
finite number of strings.
• A non-recursive grammar has neither left recursion nor right
recursion.
• Example:
S aA | bB
A a|b
B c|d
