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?

Improve this question

1 Answer 1

Reset to default
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.

Improve this answer
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.