Questions: Context-Free Grammar Properties and Ambiguity

Question 1

Consider the expression grammar E -> E + E | E * E | id. A compiler developer discovers that the string 'id + id * id' has two valid parse trees under this grammar. What is the fundamental problem this creates for the compiler?

• A. The grammar is incomplete — it fails to generate some arithmetic expressions
• B. The grammar generates too many strings — it accepts some expressions that should be invalid
• C. The grammar cannot be used to guide parsing at all, because ambiguous grammars have no valid derivations
• D. The compiler cannot assign a unique structural interpretation to the expression, leaving evaluation order undefined

Answer: (D)

An ambiguous grammar produces multiple parse trees for the same string. For a compiler, each parse tree implies a different program meaning — here, 'id + id * id' could parse as (id + id) * id or as id + (id * id), which compute different values. A compiler must produce exactly one machine-code translation, requiring exactly one parse tree per valid expression. The grammar is not incomplete (it generates all valid arithmetic expressions) and it has valid derivations. The problem is purely structural: it fails to impose the unique tree that downstream code generation requires.

Question 2

A grammar contains the production A -> Aalpha | beta, where A is the first symbol on the right-hand side. Which type of parser can handle this production directly without transformation?

• A. LL (top-down) parsers, because they process input from left to right
• B. Neither LL nor LR parsers — left recursion is illegal in context-free grammars
• C. LR (bottom-up) parsers, which build parse trees from leaves to root and handle left recursion naturally
• D. Both LL and LR parsers, provided the grammar is otherwise unambiguous

Answer: (C)

Left recursion causes top-down (LL) parsers to loop infinitely: expanding A requires applying A -> Aalpha, which requires expanding A again, with no input consumed. LR (bottom-up) parsers work by reading input and reducing sequences to nonterminals; they can shift terminal symbols before applying reductions, so left recursion poses no problem. The grammar is perfectly valid as a context-free grammar — left recursion is only a parsing strategy problem, not a theoretical one. This is why left-recursive grammars are common in formal language theory but require transformation before use with LL parsers.

Question 3

Two context-free grammars can generate exactly the same set of strings yet differ in whether they are ambiguous.

• T. True
• F. False

Answer: True

Ambiguity is a property of a specific grammar, not of the language it defines. Many context-free languages can be described by both ambiguous and unambiguous grammars. The expression grammar E -> E + E | E * E | id is ambiguous, but the precedence-encoded version (with separate nonterminals for each precedence level) is unambiguous and generates the same language. Compiler developers exploit this: when a natural, intuitive grammar is ambiguous, they rewrite it to an equivalent unambiguous form without restricting the set of valid programs.

Question 4

Fixing an ambiguous grammar generally requires removing some strings from the language — that is, accepting a more restrictive set of programs.

• T. True
• F. False

Answer: False

Disambiguation rewrites the grammar's structure so that every string has exactly one parse tree, but it does not have to change which strings the grammar accepts. The standard fix for expression grammars — introducing separate nonterminals for each precedence level — generates the same language (all valid arithmetic expressions) while eliminating ambiguity. What changes is the grammar's internal structural representation of sentences, not the set of sentences it accepts. The language stays the same; only the grammar changes.

Question 5

What exactly is wrong with using an ambiguous grammar in a compiler, and how does encoding operator precedence directly into the grammar's nonterminal hierarchy solve this problem?

Model answer: An ambiguous grammar gives some strings multiple parse trees, each implying a different syntactic structure and therefore a different computed meaning. A compiler must map each expression to a unique sequence of machine instructions, which requires exactly one structural interpretation. Encoding precedence into the grammar hierarchy — for example, nesting multiplication nonterminals inside addition nonterminals so that * binds more tightly than + — means every expression has exactly one valid parse tree, and that tree's structure directly encodes the correct evaluation order. The disambiguation is built into the grammar itself rather than handled by external rules.

The rewritten unambiguous grammar generates the same language — every arithmetic expression is still valid — but each expression now has exactly one parse tree reflecting the correct precedence. This is the standard approach in production compilers: rather than accepting the natural but ambiguous grammar and applying disambiguation tables as a separate step, grammar engineers build precedence and associativity directly into the production rule hierarchy. The result is a grammar that drives parsing cleanly and whose structural output directly represents the intended meaning of each expression.