Can a grammar that has only one leftmost derivation tree for every sentence, have more than one rightmost derivation tree for some sentence?

Question

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.

Answer 1

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.