0
$\begingroup$

I'm currently studying the book Engineering a Compiler by Keith Cooper, and in chapter 3, there is the following definition:

A grammar G is ambiguous if some sentence in L(G) has more than one rightmost (or leftmost) derivation.

One of the exercises asks the following:

When asked about the definition of an unambiguous context-free grammar on an exam, two students gave different answers. The first defined it as “a grammar where each sentence has a unique syntax tree by leftmost derivation.” The second defined it as “a grammar where each sentence has a unique syntax tree by any derivation.” Which one is correct?

I tried to deduce the definition of unambiguity by negating the definition of ambiguity the chapter has given me:

A grammar G is unambiguous if for every sentence in L(G) there is one and only one rightmost (and leftmost) derivation.

I changed the or to an and because not (a or b) = not a and not b

However most definition of ambiguity I managed to find online states that

A grammar G is unambiguous if for every sentence in L(G) there is one and only one rightmost (or leftmost) derivation.

I've also found that

If a grammar is unambiguous, that means that the rightmost derivation and the leftmost derivation of every sentence represent in the same parse tree.

Reading the last two quotes confuses me in many ways:

  • Does the or in the definition of unambiguity implies that there can exist an unambiguous grammar where for every sentence of it, there is only one leftmost derivation, but more than one rightmost derivation?

  • Does the last quote implies that I only need to find out if for a given grammar, every sentence of it has only one leftmost or rightmost derivation, because if there is, I don't need to find if the other derivation is unique because they're the same?

  • If the statement above is correct, does that mean that only the second student in the excercise are correct? Or that both students are correct?

  • Some other definitions of unambiguity state only about leftmost derivation. Which is correct?

Thanks in advance to everyone who reads this.

$\endgroup$
1
$\begingroup$

In a word, no.

Every tree has exactly one left-to-right depth-first traverse and exactly one right-to-left depth-first traverse, either of which can be used to unambiguously recreate the original tree.

Since the leftmost derivation of a sentence is just another way of writing the left-to-right depth-first traverse of the parse tree for that sentence (and analogously the rightmost derivation), it is only possible for a sentence to have more than one rightmost derivation if there is more than one parse tree, each of which corresponds to a different leftmost derivation.

In other words, for a given sentence generated by a given grammar, the following are exactly the same number:

  • The number of different leftmost derivations of the sentence.
  • The number of different rightmost derivations of the sentence.
  • The number of parse trees whose leaves spell out the sentence.

If that number is one for every sentence generated by the grammar, then the grammar is unambiguous.

So you can use whichever definition for "unambiguous" you find most convenient.

$\endgroup$
3
  • $\begingroup$ I was lacking that first knowledge about right/leftmost derivations representing the same idea of traversing the tree. I guess I was assuming that a given parse tree could have more than one right/leftmost derivation. Thanks for your reply! $\endgroup$ Sep 1 at 4:56
  • $\begingroup$ @angelo: In a parse tree, the leaves are terminals and the nodes are non-terminals. The list of children of each non-terminal is precisely the production which was used to expand that particular non-terminal, so a derivation step corresponds to visiting a node during a traverse. (There are many derivations for a given parse tree because there are many ways of traversing a tree, but there is only one derivation for any deterministic traverse algorithm.) IMHO, it's worth spending some time with a pad of paper and a pencil drawing out parse trees for some simple parses.... $\endgroup$
    – rici
    Sep 1 at 5:34
  • $\begingroup$ There are probably people who can absorb the information and intuitions just be reading the mathematical theorems, but I needed the practical exercise with my hands to really get it. (And that goes double for the rest of parsing theory.) $\endgroup$
    – rici
    Sep 1 at 5:36

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.