3

I have the following question taken from a compilers course exam:

Show that the following grammar is ambiguous.

S = XcY
X = a
Y = b | Z
Z = bW
W = d | ϵ

I drew the following tree:

grammar diagram

Am I correct in thinking it is ambiguous because acY can end up at acb (one of which is followed by an epslion) following different paths?

TomSelleck
  • 379
  • 3
  • 11

1 Answers1

6

Yes. Since epsilon means you can rewrite W as the empty string, acbW -> acb. As you have shown, there are two leftmost derivations for the string acb, which by definition means the grammar is ambiguous.

ndm
  • 556
  • 3
  • 5