Bottom-Up Parsing: Problems
1) Two or more rules have the same handle
Note: A handle is the right-hand side of a rule.
X1
X2
Xn
A
…
r1: A ® X1X2…Xn
r2: B ® X1X2…Xn
handle
tokens
X1
X2
Xn
B
…
tokens
Use rule r1 or r2 ?
E
E
E
E
Which of these tree to create?
2) Ambiguous grammars
Gexpr2 = (N, T, P, E), where
N = {E}, T = {i, +, *, (, )},
P = { 1: E ® E+E, 2: E ® E*E,
          3: E ® (E),   4: E ® i  }
E
E
E
+
*
i
i
i
E
E
E
+
*
i
i
i
2/42