Ambiguity in Context-Free Grammars, Disambiguation Techniques, and Analysis of the Grammar $S \rightarrow aS/Sa/a$

A context-free grammar (CFG) is called ambiguous when there exists at least one terminal string that can be produced in two distinct ways resulting in two different parse trees (equivalently, two different leftmost/rightmost derivations).2 Ambiguity is a syntactic property of the grammar, not of the language alone: a language may admit both ambiguous and unambiguous grammars (or be inherently ambiguous).2

Ambiguity becomes a practical problem in parsing/compilers because a parser would not have a unique syntactic structure to attach to the same input string, undermining deterministic meaning assignment from syntax trees.

Key terms:

• Ambiguous grammar
• Parse tree
• Leftmost derivation
• Unambiguous grammar

Ambiguity can often be reduced or eliminated by redesigning the grammar (grammar transformation) so that the intended structure is forced by the rules. Typical approaches include:

1. Refactoring to enforce structure, e.g., left-factoring (common in LL parsers).
2. Eliminating left/right recursion (improves parser construction but does not always solve ambiguity by itself).
3. Encoding precedence and associativity in the grammar (crucial for arithmetic-expression ambiguity).
4. Using parser-generator precedence/associativity declarations (e.g., in YACC) which effectively resolves some shift/reduce conflicts.2

However, there is a strong theoretical limitation: the computational task “given a CFG, decide whether it is ambiguous” is undecidable in general. Likewise, the task of algorithmically finding an equivalent unambiguous CFG (when possible) is not solvable in general.

Key terms:

• Left factoring
• Operator precedence
• Associativity
• Undecidable problem

Now consider the grammar (as written):

Interpreting “$/$” as alternative productions, the CFG is:

We will decide whether it is ambiguous by checking whether some string has more than one parse tree.

Key insight: every production adds exactly one terminal symbol $a$ either on the left ($aS$) or on the right ($Sa$), and the base case produces exactly one $a$ ($S\rightarrow a$).

Key terms:

• Base case
• Sentential form
• Derivation length

Claim: The grammar is unambiguous

Let the target string be $a^n$ (i.e., $n$ copies of $a$). We show that it has a unique parse tree.

Structure forced by the first step

• If the derivation starts with $S \Rightarrow aS$, then one $a$ is fixed as the leftmost symbol of the final yield; the rest must come from deriving the remaining $n-1$ symbols via $S$.
• If instead $S \Rightarrow Sa$, then one $a$ is fixed as the rightmost symbol.
• Only $S \Rightarrow a$ can produce a string of length $1$.

Uniqueness argument (for $a^n$): Consider the derivation tree’s root label $S$. The tree has exactly one internal node labeled $S$ at each derivation depth until reaching the leaf created by $S \rightarrow a$.

For the yield to be exactly $a^n$, at each internal $S$ node, you must choose whether that node contributes the next $a$ on the left or on the right. But because the entire string is homogeneous ($a$ everywhere), different “left vs right” choices could appear to lead to the same terminal string.

We resolve this by observing that different sequences of left/right choices change the branching structure in the parse tree: the grammar’s productions are not symmetric through a single local rewrite—each internal node corresponds to a specific production occurrence ($aS$ or $Sa$). Those occurrences induce different tree shapes.

Concretely:

• For $n=2$, the grammar can only derive $aa$ by either:
  • $S \Rightarrow aS \Rightarrow a a$
  • or $S \Rightarrow Sa \Rightarrow a a$ These terminal strings are identical, so we check whether these produce different parse trees:
• First derivation tree: root uses $S\rightarrow aS$; the $S$ child then uses $S\rightarrow a$.
• Second derivation tree: root uses $S\rightarrow Sa$; the $S$ child then uses $S\rightarrow a$.

These two parse trees are structurally different because the root production differs ($aS$ vs $Sa$), even though the final yield is the same terminal string $aa$.

Therefore, the grammar is ambiguous.

This directly matches the definition: if there exists a string with two different parse trees, the grammar is ambiguous.

Key terms:

• Ambiguity witness
• Production choice

Explicit ambiguity witness for this grammar

We exhibit two different parse trees (equivalently, two distinct derivations) for the same string $aa$.

Derivation 1 (using $S\rightarrow aS$ at the root):

Derivation 2 (using $S\rightarrow Sa$ at the root):

These correspond to different parse-tree structures at the root because the root production differs ($aS$ vs $Sa$). Hence the grammar is ambiguous.