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

A Natural Language Example

Anyone who has taken a course in programming probably knows that the main difference between programming languages and natural languages is that all natural languages are ambiguous, while an an ambiguous programming language would be useless. Of course, we've all had the experience of misinterpreting something we've heard or read, so most people will take it on faith that natural languages are inherently ambiguous. However, a natural language example can make it easier to appreciate what it means for a context-free grammar to be ambiguous and what implications it has.

Here is a grammar which is a very basic representation of a small part of English:

            <sentence> → <noun-phrase> <verb-phrase>
         <noun-phrase> → <complex-noun> | <complex-noun> <prepositional-phrase>
         <verb-phrase> → <complex-verb> | <complex-verb> <prepositional-phrase>
<prepositional-phrase> → <preposition> <complex-noun>
        <complex-noun> → <article> <noun>
        <complex-verb> → <verb> | <verb> <noun-phrase>
             <article> → a | the
                <noun> → boy | girl | flower
                <verb> → touches
         <preposition> → with

We could derive a number of valid sentences from this grammar, but let's take a look at this one:

the girl touches the boy with the flower

It's probably pretty apparent that this sentence can be interpreted in two ways. Just to be thorough though, let's take a look at the two derivations.

   the     girl      touches   the     boy        with        the    flower
    |       |          |        |       |          |           |       |
<article> <noun>     <verb> <article> <noun> <preposition> <article> <noun>
    \       /          \        \       /          |            \       /
  <complex-noun>         \   <complex-noun>        |         <complex-noun>
        |                  \       \                \              /
   <noun-phrase>             \       \           <prepositional-phrase>
        \                      \       \                   /
          \                      \       \               /
            \                      \       \           /
              \                      \     <noun-phrase>
                \                      \        /
                  \                   <complex-verb>
                    \                       |
                      \               <verb-phrase>
                        \                   /
                          \               /
                            \           /
                              \       /
                              <sentence>

The above derivation implies that the boy who the girl touched was in possession of flora at the time.

   the     girl      touches   the     boy        with        the    flower
    |       |          |        |       |          |           |       |
<article> <noun>     <verb> <article> <noun> <preposition> <article> <noun>
    \       /          \        \       /          |            \       /
  <complex-noun>        \    <complex-noun>        |         <complex-noun>
        |                \         |                \              /
   <noun-phrase>          \   <noun-phrase>      <prepositional-phrase>
        \                  \       /                       /          
          \              <complex-verb>                  /  
            \                   \                      / 
              \                   \                  / 
                \                   \              /
                  \                   \          /
                    \                 <verb-phrase>
                      \                     /     
                        \                 /
                          \             /
                            \         /
                              \     /
                             <sentence>

However, the derivation above this paragraph implies that the girl did not touch the boy directly, but rather utilized said flora to touch him indirectly.

I feel that this sort of example expresses how a derivation captures meaning. It is because of this that computers (or Turing Machines) are able to meaningfully interpret writings in any language which can be defined by an unambiguous grammar. The first task of any compiler (after tokenization) is to parse the source, which is just the reverse of deriving. The above figures are, in fact, parse trees.

One more interesting point

Any language that can be defined with an unambiguous CFG can also be defined with an ambiguous one. However, not all context-free languages can be defined by an unambiguous grammar1. So, if you can come up with an unambiguous grammar for a given language, you're set, but proving that one doesn't exist is significantly harder.


1. {0m1n2s : m = n OR n = s} is an example
Introduction to the Theory of Computation (ISBN 0-534-94728-X) was consulted in the creation of this writeup.

Log in or register to write something here or to contact authors.