Questions: Parse Trees, Derivations, and Ambiguity in CFGs

Question 1

The grammar E → E + E | E × E | a is used to parse 'a + a × a.' A parser produces two different parse trees for this string. What is the correct conclusion?

• A. The grammar has a bug and must be discarded entirely
• B. The string is not in the language generated by this grammar
• C. The grammar is ambiguous — the same string has more than one valid structural interpretation
• D. This is expected and harmless because both parse trees produce the same evaluated result

Answer: (C)

When a single string has two or more distinct parse trees under the same grammar, the grammar is ambiguous. The two trees for 'a + a × a' correspond to (a + a) × a and a + (a × a) — different structures that assign different meanings to the same token sequence. Option D is the critical misconception: the two trees do NOT produce the same result. (1 + 1) × 1 = 2, while 1 + (1 × 1) = 2 here by coincidence, but structurally they represent different computations. In a compiler, ambiguity means the program has multiple possible meanings, which is unacceptable.

Question 2

What is the key difference between 'an ambiguous grammar' and 'an inherently ambiguous language'?

• A. There is no meaningful difference — both describe exactly the same property
• B. An ambiguous grammar can sometimes be replaced by an unambiguous grammar for the same language; an inherently ambiguous language has no unambiguous grammar at all
• C. An inherently ambiguous language can only be described by a single maximally ambiguous grammar
• D. Inherent ambiguity applies only to regular languages, while grammar ambiguity applies to context-free grammars

Answer: (B)

Ambiguity is a property of the grammar, not necessarily the language. The classic arithmetic grammar can be rewritten as an unambiguous grammar by introducing separate nonterminals for terms and factors, enforcing operator precedence structurally. The language of arithmetic expressions is not inherently ambiguous. But some context-free languages are inherently ambiguous: every possible grammar for them produces some ambiguous string. Recognizing this distinction matters because it tells you whether rewriting the grammar is a viable path to disambiguation.

Question 3

A leftmost derivation and a rightmost derivation of the same string can correspond to the same parse tree, because the parse tree captures structural relationships rather than the sequence of rule applications.

• T. True
• F. False

Answer: True

The parse tree records which production rules were applied and how nonterminals relate to each other in the derivation — it does not record the order in which nonterminals were expanded. A leftmost derivation expands the leftmost nonterminal at each step; a rightmost derivation expands the rightmost. Both can produce representations of the same tree, just traversed in different orders. The tree is therefore a more fundamental object than the derivation sequence: it shows how the string is structured, not merely a particular order in which the structure was assembled.

Question 4

If a grammar is ambiguous, it is extremely difficult to generate an unambiguous grammar for the same language.

• T. True
• F. False

Answer: False

Ambiguity is a property of the grammar, not always of the language. Many ambiguous grammars can be rewritten as unambiguous grammars that generate exactly the same set of strings. The standard approach for arithmetic expressions is to introduce separate nonterminals that encode precedence: a grammar with distinct rules for expressions, terms, and factors forces a unique parse tree for every valid string. Only languages that are *inherently ambiguous* — a specific, provable property — have no unambiguous grammar. Most practical programming language grammars fall into the rewritable category.

Question 5

Why does ambiguity in a grammar matter for compilers and programming languages? What goes wrong if an ambiguous grammar is used?

Model answer: A parse tree is not just a record of how a string was generated — it determines the string's meaning. In a compiler, the parse tree is the data structure used to assign semantics to a program. An ambiguous grammar means the same source code could produce multiple distinct parse trees, and therefore multiple distinct meanings. A program must have exactly one meaning; ambiguity is unacceptable. To resolve it, compiler designers either rewrite the grammar to enforce precedence and associativity structurally, or add explicit disambiguation rules (like specifying that × binds more tightly than + outside the grammar formalism).

The arithmetic example makes this concrete: 'a + a × a' could mean 'add first, then multiply' or 'multiply first, then add' — two different computations. Programming languages must specify which one they intend, and an unambiguous grammar enforces that specification at the structural level so no ambiguity can arise during parsing.