A grammar for a programming language produces two different parse trees for the input 'if (a) if (b) x = 1; else x = 2;' — one where 'else' binds to the outer 'if' and one where it binds to the inner 'if'. What is the fundamental problem and what must be done?
AThe grammar has too many production rules; reducing rule count will eliminate the conflict
BThe grammar is ambiguous — the same token stream has multiple parse trees, so the program's meaning is undefined; the grammar must be rewritten or explicit disambiguating rules added
CThe parser needs more lookahead tokens; switching from LL(1) to LL(3) will resolve the conflict
DThe lexer is incorrectly tokenizing 'else'; fixing the tokenization rules will eliminate the ambiguity
Ambiguity means a single input has multiple valid derivations — multiple parse trees — which means the language assigns two different structures (and potentially two different meanings) to the same program. This is a compiler-breaking problem, not a performance issue. The fix must be at the grammar level: rewrite to make the desired association explicit, or add a disambiguating rule like 'else binds to the nearest unmatched if.' No amount of lookahead (option C) resolves true ambiguity, and the lexer (option D) cannot resolve structural ambiguity in syntax.
Question 2 Multiple Choice
A CFG for an arithmetic language is unambiguous, but a backtracking recursive-descent parser runs in exponential time on some valid inputs. A developer argues this is acceptable since the grammar is correct. Why is this reasoning flawed?
AIt is not flawed — unambiguous grammars always parse efficiently; the exponential behavior must be a bug in the implementation
BEven unambiguous grammars can require exponential time with naive algorithms; practical compilers restrict to grammar subclasses (LL, LR) that guarantee linear-time parsing regardless of input
CThe exponential behavior only occurs on invalid inputs, which can be filtered by the lexer before parsing begins
DAdding more production rules to the grammar will transform it into an LL grammar, fixing the performance problem
Unambiguity and efficient parsability are independent properties. An unambiguous grammar merely guarantees a unique derivation exists; it says nothing about how quickly an algorithm can find it. Without structural restrictions, a backtracking parser may explore exponentially many possible derivations before finding (or ruling out) a match. The LL and LR grammar subclasses are defined precisely by structural properties that guarantee a deterministic, linear-time parsing strategy exists — they are not just 'well-written' grammars, they are grammars with proven algorithmic tractability.
Question 3 True / False
A parse tree makes operator precedence explicit: in the expression '3 + 4 * 5', a correctly written grammar will produce a parse tree where the multiplication node is nested deeper than the addition node, encoding that multiplication binds more tightly.
TTrue
FFalse
Answer: True
This is exactly why grammar design is not arbitrary — the tree structure encodes semantic relationships like precedence and associativity. A grammar that allows '3 + 4 * 5' to produce a tree with addition at the root and multiplication as a leaf correctly captures that * has higher precedence than +. An ambiguous grammar might produce a second tree with the operators at the same level or reversed, yielding a different computed value. The grammar must encode precedence by structuring its production rules so that higher-precedence operators appear deeper in the derivation.
Question 4 True / False
An ambiguous grammar can usually be converted into an equivalent unambiguous grammar — one that accepts exactly the same strings — by rewriting its production rules.
TTrue
FFalse
Answer: False
Some context-free languages are inherently ambiguous: every CFG that generates them is ambiguous. For these languages, there is no unambiguous grammar. The dangling-else case can usually be resolved by rewriting, but not all ambiguities can be. In practice, compiler designers often keep an ambiguous grammar for readability and resolve ambiguities through explicit precedence and associativity declarations (as in yacc/bison), rather than restructuring the grammar. The claim that rewriting always works is a common misconception — it conflates 'disambiguation is always possible' with 'every ambiguous grammar has an equivalent unambiguous one.'
Question 5 Short Answer
Why is grammar ambiguity a serious problem for compilers, not just a theoretical concern?
Think about your answer, then reveal below.
Model answer: An ambiguous grammar means the same program text can be parsed in two different ways, producing two different parse trees with potentially different meanings. A compiler must produce a single unambiguous interpretation; if the grammar allows two, the compiler has no principled basis to choose one and the language's semantics are undefined for those cases.
Consider an ambiguous grammar that allows '1 - 2 - 3' to be parsed as either (1-2)-3 = -4 or 1-(2-3) = 2. A compiler using that grammar might produce different code depending on which derivation it happens to find first — and a different compiler might make the opposite choice. Programs become non-portable and unpredictably wrong. In practice, ambiguities are resolved by grammar restructuring (making precedence levels explicit through nonterminal hierarchy) or by external disambiguation rules built into the parser generator.