F
F
F
In the grammar
1. E I
2. E E+E
3. E EE
4. E (E)
the sentential form E + E E has two deriva-
tions:
E E+E E+EE
and
E EE E+EE
This gives us two parse trees:
E E
E + E E * E
E * E E + E
(a) (b)
167
The mere existence of several derivations is not
dangerous, it is the existence of several parse
trees that ruins a grammar.
5. I a
6. I b
7. I Ia
8. I Ib
9. I I0
10. I I1
the string a + b has several derivations, e.g.
E E
E + E E * E
I E * E E + E I
a I I I I a
a a a a
(a) (b)
169
Removing Ambiguity From Grammars
170
Solution: We introduce more variables, each
representing expressions of same binding strength.
(a) Identifiers
171
Well let F stand for factors, T for terms, and E
for expressions. Consider the following gram-
mar:
1. I a | b | Ia | Ib | I0 | I1
2. F I | (E)
3. T F |T F
4. E T |E+T
E + T
T T * F
F F I
I I a
a a
172
Why is the new grammar unambiguous?
Intuitive explanation:
f1 f2 fn1 fn
of factors is the one that gives f1 f2 fn1
as a term and fn as a factor, as in the parse
tree on the next slide.
An expression is a sequence
t1 + t2 + + tn1 + tn
of terms ti. It can only be parsed with
t1 + t2 + + tn1 as an expression and tn as
a term.
173
T
T * F
T * F
. .
.
T
T * F
174
Leftmost derivations and Ambiguity
E + E E * E
I E * E E + E I
a I I I I a
a a a a
(a) (b)
give rise to two derivations:
E E+E I +E a+E a+EE
lm lm lm lm
a+I E a+aE a+aI a+aa
lm lm lm lm
and
E E E E +E E I +E E a+E E
lm lm lm lm
a+I E a+aE a+aI a+aa
lm lm lm lm
175
In General:
176
Sketch of Proof: (Only If.) If the two parse
trees differ, they have a node a which dif-
ferent productions, say A X1X2 Xk and
B Y1Y2 Ym. The corresponding leftmost
derivations will use derivations based on these
two different productions and will thus be dis-
tinct.
177
Inherent Ambiguity
Example: Consider L =
A grammar for L is
S AB | C
A aAb | ab
B cBd | cd
C aCd | aDd
D bDc | bc
178
Lets look at parsing the string aabbccdd.
S S
A B C
a A b c B d a C d
a b c d a D d
b D c
b c
(a) (b)
179
From this we see that there are two leftmost
derivations:
and
180