skip to content

Why can no tool certify an arbitrary context-free grammar as unambiguous before you ship a rule language?

level: seniorimportance: nice to knowfreq 24%

answer

  1. no complete checker can exist
  2. undecidable for arbitrary rule sets
  3. a search finds, never clears
  4. successful construction proves one direction
  5. some languages have no unambiguous grammar

basics

~20 s

Deciding whether an arbitrary context-free grammar is ambiguous is undecidable, so no checker can be both sound and complete. Tools instead search for a witness string, which can only ever find ambiguity, or restrict the grammar to a class whose successful construction proves uniqueness.

solid answer

~50 s

There is no algorithm that takes any context-free grammar and answers "ambiguous or not" correctly in every case — the problem is undecidable, as is deciding whether a language is inherently ambiguous and whether two such grammars generate the same language. What you get instead are two one-sided tools. A **witness search** enumerates strings looking for one with two derivations: finding one is a proof of ambiguity, but finding none after any amount of search proves nothing, because the witness may be longer than you looked. A **construction** that builds a deterministic parser for the grammar is the other side: if it succeeds, that grammar is unambiguous, because such a parser produces one tree per string. If it fails, you have learned that the grammar is outside the class, not that it is ambiguous. And some languages are **inherently ambiguous** — no unambiguous grammar exists for them at all — so rewriting is not always available.

go deeper

for a junior

Know that checking a grammar for ambiguity is not something a tool can simply do for any grammar, and that finding an example string is how ambiguity is normally shown.

for a middle

State which way each tool is one-sided: a witness proves ambiguity, a successful deterministic construction proves the grammar unambiguous, and neither negative result proves anything.

for a senior

Build the process around the asymmetry — keep the grammar in a constructible class so the build itself is the evidence, and keep every witness ever found as a regression case.

for a principal

Recognise when a language design is asking for trouble — two counting relations over one sequence, or a syntax whose meaning depends on a resolution nobody wrote down — and decide it before any text is stored in it.

## What exactly is undecidable Three related questions about context-free grammars have no general algorithm: 1. **Is this grammar ambiguous?** Given an arbitrary context-free grammar, no procedure answers correctly for every input. 2. **Is this language inherently ambiguous?** That is, does *every* grammar for it derive some string two ways — also undecidable. 3. **Do these two grammars generate the same language?** Undecidable too, which is why "just diff my rewritten grammar against the old one" is not a route around the first question. "Undecidable" is a statement about *all* grammars at once. It does not say your grammar is hard; it says no single procedure handles every grammar, so any checker must either give up on some inputs, get some wrong, or answer a narrower question. ## The two one-sided tools you actually get | Tool | What a positive result proves | What a negative result proves | |---|---|---| | Witness search (enumerate strings, look for two derivations) | A witness found means the grammar **is** ambiguous — a proof | Nothing. The shortest witness may be longer than the bound you searched | | Deterministic construction (build a one-tree-per-string parser) | Success means **this grammar** is unambiguous | Nothing about ambiguity. Only that the grammar falls outside that class | The asymmetry is the whole practical story, and it is easy to state backwards. Take care with the direction: - A grammar for which a deterministic construction succeeds is unambiguous. The implication runs that way and not the other: there are **unambiguous grammars no such construction accepts**, so a failed construction is not evidence of ambiguity. - A search that finds nothing is not a certificate. It bounds where the ambiguity is not, and nothing more. ## Inherently ambiguous languages Usually the fix for an ambiguous grammar is to write a better grammar for the same language. Sometimes that is impossible. A language is **inherently ambiguous** when every grammar generating it is ambiguous. The classic example is the set of strings `a^i b^j c^k` where either `i = j` or `j = k`. Intuitively, a grammar must pair the `a`s with the `b`s for one half of the language and the `b`s with the `c`s for the other, and the strings where `i = j = k` sit in both halves — every grammar ends up deriving those strings both ways. Two consequences for practice: - "Rewrite the grammar" is the right default but not a guarantee, so a language design that needs two different counting relations over one sequence is worth questioning early. - Nearly all practical syntaxes are *not* inherently ambiguous; a dangling else or an unlayered expression rule is a fixable grammar defect, not a fact about the language. ## What to do about a rule language you ship Since you cannot ask for a certificate, engineer for the one-sided tools: - **Keep the grammar inside a class your construction accepts.** A successful build then *is* your unambiguity evidence, checked on every change, and a regression shows up as a build failure rather than as two services disagreeing. - **Treat a search-found witness as a defect with a test.** Any string that parses two ways goes into a corpus that the build re-checks. - **Never rely on "we have not seen it".** Absence of a reported problem is the negative result that proves nothing; user-written rules explore shapes your examples do not. - **Write the tie-break down where it is unavoidable.** If a construction's default resolution is what keeps your parser deterministic, that default is part of your language specification and must be stated for the next implementer, not left in a generator's settings. ## The register of the answer This is a differentiator question, not a screening one. What earns credit is not reciting "undecidable" but drawing the consequence correctly: you cannot buy proof of absence, so you buy proof of presence cheaply (witness search) and restructure the problem so the proof of absence becomes a by-product of something you were doing anyway (constructing a deterministic parser). Getting the implication direction backwards — claiming that a construction failure proves ambiguity — is the single most common error in this material.

  • If a parser construction accepts your grammar, what exactly have you proved?
    That this grammar derives at most one tree per string, so it is unambiguous. You have not proved anything about other grammars for the same language, and if the construction had failed you would have learned only that the grammar is outside that class.
  • Give a language for which no unambiguous grammar exists.
    The strings a^i b^j c^k where i equals j or j equals k. Any grammar must handle the two counting relations separately, and the strings where all three counts agree fall into both cases, so they end up with two derivations under every grammar.

saying these in an interview costs you the question

  • Says an accepted grammar proves the language itself is unambiguous
  • Claims a long fruitless search establishes unambiguity
  • Says every ambiguous grammar can be rewritten into an unambiguous one
  • Reads a failed construction as proof that the grammar is ambiguous
  • Treats undecidable as meaning no useful check is possible