Skip to content
Tape‑n‑Trace
PracticeSearch 26 tools

← Grammars and derivations

Is this grammar ambiguous?

Hopcroft 2e §5.4. A grammar is ambiguous when some string has two distinct leftmost derivations. The detector searches for one; a witness is a complete proof, and its two parse trees are drawn side by side.

Presets:

Symbols split per character (aSb is a, S, b) unless any alternative contains spaces — then tokens are space-separated and id stays one terminal. Variables are whatever appears left of an arrow.

1 variables {E}, 5 terminals {+, *, (, ), id}, start E — 4 productions.

Why the answers are asymmetric

Finding a string with two parse trees settles the question forever. Finding none settles nothing: whether a grammar is ambiguous is undecidable in general, and some languages are inherently ambiguous — every grammar for them is ambiguous (Hopcroft 2e §5.4.4) — so a bounded search is the strongest honest tool. Try the exam expression grammar preset: the ambiguity disappears under the rewrite, and the detector's answer changes shape with it.