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?

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.