Problem Solving in Automata, Languages, and Complexity

3.3 Parsing and Ambiguity 115

represent operands of operations + and -, and use symbol F (standing for

factor) to represent operands of * and t.

In addition, we note that the intended interpretation of an arithmetic ex-

pression follows the usual preference rules:

0 i

( > ii

The operators + and - have higher preference over -il: and t.

Within the operators of the same preference (e.g., + and -) in an arith-

metic expression, the one to the left has the preference over the one to

the right.

We can enforce these rules in the following grammar:

E---,E+TfE-TIT,

T---+T*FIT+FfF,

F ---+ (E) 1 a 1 b.

For instance, a - b a + b has a unique parse tree as shown in Figure 3.9(a).
We note that the symbols - and + must be generated first before we use T
to generate b a, because there is no way to generate - or + from T (without
using parentheses). Thus, the preference rule (i) is followed. Second, if we
start the derivation of a - b ;I: a + a by [E + E -T], then the symbol + cannot
be generated without parentheses. Thus, we must generate the rightmost +
or - symbol first, and this forces the parse tree to follow the preference rule
(ii). (If we replace the first grammar rule by [E -+ T + E 1 T - E 1 T],
then we force the parse tree to generate the leftmost + or - symbol first.) If
we want to generate parse trees defying these preference rules, we must use
parentheses. For instance, if we want to perform a + b first in the expression
a - b a + b, then we must generate the expression a - b (a + b), whose unique
parse tree is as shown in Figure 3.9(b). cl

denote the number of occurrences of symbol a in

a string w. Let L =.

(a) Show that both solutions of Exumple 3.6 for L are ambiguous:

G1 : S + aSbS 1 bSaS 1 E.

Gz : S I__) E f aB 1 bA, A ---+ aS 1 bAA, B -+ bS 1 aBB.

(b) Find an unambiguous context-free grammar for the language L.

Solution. (a) In grammar Gl, the ambiguity comes from the two occurrences
of the nonterminal symbol S in the sentential form aSbS in the following two
leftmost derivations for the string abab:

S =+ aSbS --L, abSaSbS * abaSbS =+ ababS 3 abab,

S 3 aSbS + abS 3 abaSbS * abubS 3 abab.