Questions: Parser Conflict Resolution

Question 1

In the dangling-else problem, a parser generator defaults to preferring shift over reduce when it encounters the conflict on the 'else' token. What parse tree does this default produce for `if a then if b then s1 else s2`?

• A. The else binds to the outer if, because shifting extends the outer construct
• B. The else binds to the nearest (inner) if, because shifting continues building the inner if-then-else
• C. A syntax error is reported, because the grammar is ambiguous
• D. Both parse trees are generated and the programmer must choose

Answer: (B)

When the parser shifts the 'else', it continues building the inner 'if-then-else' construct rather than reducing the inner 'if-then' to a complete statement. This binds the else to the nearest enclosing if — which is the intended semantics of most languages. This is a case where the default shift preference happens to match the desired language semantics, making it safe to leave the conflict resolved by precedence rather than grammar rewriting.

Question 2

A grammar has a reduce-reduce conflict. The developer adds '%left' declarations to suppress it and all parser tests pass. What risk has been introduced?

• A. None — precedence declarations are designed to resolve all types of conflicts safely
• B. The parser may silently produce incorrect parse trees, because precedence rules don't naturally model the semantics of reduce-reduce conflicts
• C. The grammar becomes LALR(2) instead of LALR(1), requiring a more powerful parser
• D. Compilation will be slower because the parser must check precedence at every step

Answer: (B)

Precedence and associativity declarations are designed for operator-precedence ambiguities (arithmetic expressions, dangling-else). A reduce-reduce conflict typically means two competing production rules overlap, which is a structural grammar problem — not an operator-precedence problem. Suppressing it with '%left' makes the conflict disappear from the report but doesn't fix the underlying ambiguity; the parser simply picks one rule silently, which may produce incorrect parse trees for some inputs. Unlike shift-reduce conflicts (which often have natural resolutions), reduce-reduce conflicts almost always indicate genuine grammar design problems.

Question 3

Any conflict in an LALR grammar is evidence of a design error and should be eliminated by rewriting the grammar.

• T. True
• F. False

Answer: False

This is false. Some conflicts — particularly the dangling-else shift-reduce conflict — have natural, semantically correct resolutions using precedence and associativity declarations. Operator precedence conflicts (e.g., 'a + b * c') are also routinely resolved via '%left' and '%right' rather than grammar rewrites. The key is understanding which conflicts have clear intended semantics that precedence declarations can safely encode, versus which conflicts signal genuine ambiguity requiring grammar restructuring.

Question 4

A reduce-reduce conflict is generally more dangerous than a shift-reduce conflict and should rarely be suppressed with precedence declarations.

• T. True
• F. False

Answer: True

True. A shift-reduce conflict often arises from natural language ambiguities (like dangling-else or operator precedence) where the intended resolution is clear and well-modeled by precedence declarations. A reduce-reduce conflict means two different grammar rules match the same input in the same parser state — this almost always indicates a genuine design flaw in the grammar, such as overlapping or redundant productions. Suppressing it with precedence rules hides the problem and may silently accept incorrect parse trees.

Question 5

Why is a reduce-reduce conflict generally more concerning than a shift-reduce conflict, and what should a grammar designer do when they encounter one?

Model answer: A reduce-reduce conflict means two different production rules can both legally apply to the same stack contents in the same parser state, representing a genuine structural ambiguity in the grammar. This almost always indicates a design problem — two rules that shouldn't compete are overlapping. The correct response is to restructure the grammar to eliminate the overlap, not to suppress the conflict with precedence declarations. A shift-reduce conflict, by contrast, often has a natural resolution (prefer shift for dangling-else; use operator precedence for arithmetic), so precedence declarations are appropriate. Suppressing a reduce-reduce conflict with '%left' or '%right' merely hides the ambiguity and can cause the parser to silently accept incorrect parse trees.

The distinction matters because shift-reduce conflicts frequently arise from predictable, well-understood language patterns (operator precedence, optional clauses) where the semantics clearly dictate one resolution. Reduce-reduce conflicts lack this natural mapping — the competing rules typically shouldn't coexist, and choosing between them arbitrarily via precedence is not semantically principled.