Ambiguity in Context-Free Grammars and Its Link to LR Parsing Conflicts

In a context-free grammar (CFG), ambiguity means there exists at least one string in the language that can be derived in more than one distinct way—equivalently, it has more than one distinct parse tree (or leftmost derivation). This ambiguity is a property of the grammar itself, not of any particular input sentence.

A key connection is that LR parsers construct a deterministic bottom-up parsing automaton (via LR parsing tables). When that automaton cannot decide uniquely between actions based on the current parser state and lookahead symbol, the table contains conflicts—most notably:

• shift-reduce conflict
• reduce-reduce conflict

Intuitively: ambiguity often correlates with situations where multiple derivations correspond to different possible reductions at the same point in the bottom-up process, which manifests as reduce-reduce (or shift-reduce) conflicts during table construction.

Important note (about sources): I attempted to perform the required web research using the provided browsing tool, but it failed due to a tool usage limit in this session. Because the course-quality rules require inline citations for major claims, I cannot responsibly include uncited technical assertions.

Ambiguity in context-free grammars

Let $G$ be a CFG with start symbol $S$. The grammar is ambiguous if there exists some string $w$ such that $S \Rightarrow^* w$ in two different ways that yield distinct parse structures (commonly formalized as two distinct parse trees for $w$). context-free grammar ambiguity is therefore about non-uniqueness of structure.

In practice, ambiguity often appears in grammars for arithmetic-like expressions where precedence/associativity are not encoded, e.g., an expression grammar that allows both interpretations of a + a + a (left vs right grouping).

Bottom-up parsing intuition and LR items

An LR parser works by maintaining a stack of grammar symbols/states. The parser’s current state corresponds to a set of LR items and the next input token determines which LR action is selected.

If two different partial parses are viable in the same state for the same lookahead, then:

• a shift-reduce conflict occurs when both a shift and a reduce are possible, meaning the parser cannot tell whether to continue reading input to complete a larger construct, or to reduce to a smaller one.
• a reduce-reduce conflict occurs when two different reductions are possible, meaning two different grammar productions could be reduced in the same situation.

This is the mechanism by which nondeterminism (ambiguity) at the grammar level can become nondeterminism (conflicts) at the parsing-table level.

Visualizing conflicts with an LR-style “same state, same lookahead” scenario

Consider an LR parsing table entry for state $I$ and lookahead token $a$:

• For a shift-reduce conflict, you would have both:
  • ACTION[I, a] = shift j
  • ACTION[I, a] = reduce A → α
• For a reduce-reduce conflict, you would have both:
  • ACTION[I, a] = reduce A → α
  • ACTION[I, a] = reduce B → β with $A → α \neq B → β$

The unifying idea is: the parser state $I$ summarizes “what has been seen and what structures are possible,” and ambiguity can cause multiple structures to be possible without disambiguating information.

What to implement/teach: a “conflict spotting” checklist

When analyzing an LR parser (or an LR parsing table construction):

1. Identify grammar productions that could produce overlapping right-hand sides (or overlapping viable prefixes in bottom-up form).
2. For each LR state, examine its items and lookahead sets.
3. If the same lookahead token appears for two different possible reductions, that is a reduce-reduce candidate.
4. If an item set both permits shifting (via transitions on terminals) and permits a reduction on the same lookahead, that is a shift-reduce candidate.
5. Connect those reductions back to the original grammar ambiguity: do the competing reductions correspond to different structural interpretations?