this is a node your homework writeup
Prove that the following
grammar is
ambiguous:
<S> --> <A>
<A> --> <A> + <A>
| <id>
<id> --> a | b | c
A BNF grammar is considered ambiguous if it can generate a sentence using two different parse trees. In the above case, the same sentence a + b + c can be generated using these two parse trees:
<S> -+- <A> -+- <A> --- <id> --- a
| |
| +- +
| |
| +- <A> --- <id> --- b
|
+- <A> --- <id> --- c
<S> -+- <A> --- <id> --- a
|
+- <A> -+- <A> --- <id> --- b
|
+- +
|
+- <A> --- <id> --- c
A grammar that generates the same language, but is not ambiguous would be:
<S> --> <A>
<A> --> <A> + <id>
| <id>
<id> --> a | b | c
This is chapter 3, question 8 of Concepts of Programming Languages Fourth Edition by Robert W. Sebesta