PROOF: (Only-if) If we examine the construction of a leftmost derivation from a parse tree in the proof of Theorem 5.14, we see that wherever the two parse trees first have a node at which different productions are used, the leftmost deriTOtions constructed will also use different productions and thus be different deri rati cms.

(If) While we have not previously given a direct construction of a parse tree from a leftmost derivation, the idea is not hard. Start constructing a tree with only the root, labeled S. Examine the derivation one step at a time. At each step, a variable will be replaced, and this variable will correspond to the leftmost node in the tree being constructed that has no children but that has a variable as its label. From the production used at this step of the leftmost derivation, determine what the children of this node should be. If there are two distinct derivations, then at the first step where the derivations differ, the nodes being constructed will get different lists of children, and this difference guarantees that the parse trees are distinct. □

5.4.4 Inherent Ambiguity

A context-free language L is said to be inherently ambiguous if all its grammars are ambiguous. If even one grammar for L is unambiguous, then L is an unambiguous language. We saw, for example, that the language of expressions generated by the grammar of Fig. 5.2 is actually unambiguous. Even though that grammar is ambiguous, there is another grammar for the same language that is unambiguous - the grammar of Fig. 5.19.

We shall not prove that there are inherently ambiguous languages. Rather we shall discuss one example of a language that can be proved inherently ambiguous, and we shall explain intuitively why every grammar for the language must bt; ambiguous. The language L in question is:

L = {a4 c d I n > l,m > 1} U {a 6 c d n > l,m > 1}

That is, L consists of strings in а+bc+d such that either:

1. There are as many as as bs and as many es as ds, or

2. There are as many ns as ds and as many bs as es.

L is a context-free language. The obvious grammar for L is shown in Fig. 5.22. It uses separate sets of productions to generate the two kinds of strings in L.

This grammar is ambiguous. For example, the string aabbccdd has the two leftmost derivations:

1. S AB = aAbB => aahbB aabbcBd aabbccdd

hn hn lin im Im

2. 5 => С aCd aaDdd aabDcdd aabbccdd

hn im hn tm im

S A В

AB I С аАЬ I ab cBd I cd aCd\aDd bDc I be

Figure 5.22: A grammar for an inherently ambiguous language 5 S

(a) (b)

Figure 5.23; Two parse trees for aabbccdd

and the two parse trees shown in Fig. 5.23.

The proof that all grammars for L must be ambiguous is complex. However, the essence is as follows. We need to argue that all but a finite number of the strings whose counts of the four symbols a, b, c, and d, are all equal must be generated in two different ways: one in which the as and b are generated to be equal and the cs and ds are generated to be equal, and a second way, where the as and ds are generated to be equal and likewise the bs and cs.

For instance, the only way to generate strings where the as and bs have the same number is with a variable like A in the grammar of Fig. 5.22. There are variations, of course, but these mriations do not change the basic picture. For instance:

Some small strings can be avoided, say by changing the basis production A ab to A aaabbb, for instance.

* We could arrange that A shares its job with some other variables, e.g., by using variables .4, and Л2, with Ai generating the odd numbers of as and Л2 generating the even numbers, as; .4i aA2b \ ab; A2 aAib ab.

We could also arrange that the numbers of os and 6s generated by A are not exactly equal, but off by some finite number. For instance, we could start with a production like S AbB and then use A aAb \ a to generate one more than bs.

However, we cannot avoid some mechanism for generating as in a way that matches the count of fes.

Likewise, we can argue that there must be a variable like В that generates matching es and ds. Also, variables that play the roles of С (generate matching as and ds) and D (generate matching bs and es) must be available in the grammar. The argument, when formalized, proves that no matter what modifications we make to the basic grammar, it wdl generate at least some of the strings of the form a f c d in the two ways that the grammar of Fig. 5.22 does.

5.4.5 Exercises for Section 5.4 Exercise 5.4.1: Consider the grammm

S aS\ aSbS \ с

This grammar is ambiguous. Show in particular that the string aab has two:

a) Parse trees.

b) Leftmost derivations.

c) Rightmost derivations.

! Exercise 5.4.2: Prove that the grammar of Exercise 5.4.1 generates all and only the strings of as and bs such that every prefix has at least as many os as bs

*l Exercise 5.4.3: Find an unambiguous grammar for the language of Exercise 5.4.1.

M Exercise 5.4.4: Some strings of ns and bs have a unique parse tree in the grammar of Exercise 5.4.1. Give an efficient test to tell whether a given string is one of these. The test try all parse trees to see how many yield the given string is not adequately efficient,

! Exercise 5.4.5: This question concerns the grammar from Exercise 5.1.2, which we reproduce here: