0
$\begingroup$

I'm wondering, is showing two different ways to derive the same word enough proof to show that a context-free grammar is ambiguous?

For example:


O = start symbol
Non-terminal = {O}
Terminal = {r, s}
Productions =
O -> r
O -> Or
O -> sOO
O -> OOs
O -> OsO

There are two different derivations for the word rsrrs:


O -> OOs -> OsOOs -> rsOOs -> rsrOs -> rsrrs
O -> OsO -> rsO -> rsOOs -> rsrOs -> rsrrs

$\endgroup$
  • 1
    $\begingroup$ You have to be a bit more careful, but you're on the right track. A grammar is defined to be ambiguous if there is a word generated by the grammar which has two different parse trees. In your example, that's exactly what happens. $\endgroup$ – Rick Decker Oct 29 '15 at 0:00
  • 1
    $\begingroup$ The principle question directly follows from the definition of ambiguity. (And surely has a duplicate on the site?) The example is for you to work through. $\endgroup$ – Raphael Oct 29 '15 at 6:41
2
$\begingroup$

As Rick says, this is very close. The key is to show that there are two different parse-trees for the same word in the grammar.

What you have is okay, but presenting it as a linear derivation isn't enough. For example, consider something similar to what you did, but slightly different:

$O \rightarrow OOs \rightarrow OsOOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs$

$O \rightarrow OOs \rightarrow rOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs $

At face value, these are two different derivations. However, if you look closely, you see that they only differ in the order that we expand the different terminals of the same intermediate word. So this is NOT a valid proof that the grammar is ambiguous.

However, if we look at your original example using parse-trees, we can see that it still holds:

O
|
O--O--s
|  |  
r  s--O--O
      |  r
      r

And the second tree:

O
|
O--s--O
|     |  
r     O--O--s
      |  |
      r  r

This shows that these are actually different parses: we use a different production from the initial $O$ symbol, so we know that they are different.

An equivalent way to do this is to use the linear derivations like you do, but always put them in "left-derivative" form, where you only ever expand the left-most non-terminal. So your derivations would become:

$O \rightarrow OOs \rightarrow rOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs$

$O \rightarrow OsO \rightarrow rsO \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs $

In this case, there's a 1:1 correspondence between left-derivatives and parse trees, so if there are two distinct ones, you know the grammar is ambiguous.

For the "bad" example I gave, both derivations give the first parse tree, so it's not a valid proof that the grammar is ambiguous.

$\endgroup$
  • 3
    $\begingroup$ "but presenting it as a linear derivation isn't enough" -- if the shown derivations are left-derivations, it is sufficient. (They seem to be here, but I did not check if there is only one way to read the linearization.) $\endgroup$ – Raphael Oct 29 '15 at 6:43
  • $\begingroup$ I'm assuming that means always expand the leftmost non-terminal? $\endgroup$ – jmite Oct 29 '15 at 6:45
  • 1
    $\begingroup$ Yes. I thought you'd know; you can define ambiguity without the concept of syntax trees that way, and I have seen it done in this fashion. $\endgroup$ – Raphael Oct 29 '15 at 6:49
  • 3
    $\begingroup$ There's a bijection between leftmost derivations and parse treees (applying substituions in in-order DFS order always choosing the leftmost child first), and similarly for rightmost derivations. Thus, there is more than one parse tree iff there is more than one leftmost (or more than one rightmost) derivation. $\endgroup$ – G. Bach Oct 29 '15 at 10:14

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.