BNF & EBNF
Two notations for the same grammars. EBNF adds repetition, option and grouping operators that remove the recursion boilerplate — and in doing so, quietly stops telling you which way a list associates.
What does EBNF actually buy me over plain BNF, and what does the shorter notation stop telling me?
Still a specification of a set of token sequences — the notation change does not change what is being specified. What changes is the *shape of the productions*, and therefore the shape of the parse tree a naive reader would expect. EBNF exists to answer "how do I write a repeated construct without inventing a nonterminal and a recursion for it?"
A BNF-to-EBNF rewrite is legal only if the two grammars generate exactly the same set of sentences. It does *not* have to preserve parse trees, and in the common case of turning left recursion into a star it does not: the star form has no opinion about grouping, so the parser must supply the associativity the recursion used to encode.
Key points
- BNF has sequencing and alternation only; every repetition is a recursion and every precedence level is a nonterminal.
- EBNF adds repetition, option and grouping. It changes the notation, never the class of languages that can be described.
- The star operator is flat: it says how many, never how they group. Associativity has to come from prose, a table or a convention.
- EBNF transliterates directly into recursive-descent loops, which is why hand-written parsers and EBNF specifications go together.
- Rewriting a star to a right recursion preserves the language and silently changes every parse tree — and evaluation with it.
- Bison has no repetition operator, and its manual prefers left recursion because right recursion makes the parser stack grow with list length.
The same language, written twice
BNF — Backus-Naur Form, from the ALGOL 60 report — has exactly one composition operator: sequencing, plus alternation written with |. Everything else is expressed with recursion and with extra nonterminals. A list of one or more terms separated by + or - becomes a left-recursive rule, and a rule per precedence level.
EBNF adds three things: { x } or x* for zero-or-more, [ x ] or x? for optional, and parentheses for grouping. ISO 14977 standardises one spelling; the W3C XML specification uses another; the Go specification uses a third. They are all the same idea and the differences are cosmetic, which is worth saying out loud because reading a grammar from an unfamiliar standard otherwise feels harder than it is.
| <expression> | ::= | <expression> "+" <term> | |
| <expression> | ::= | <expression> "-" <term> | |
| <expression> | ::= | <term> | Three productions for one idea. The recursion on the left is what makes `a - b - c` group as `(a - b) - c`. |
| <term> | ::= | <term> "*" <factor> | |
| <term> | ::= | <term> "/" <factor> | |
| <term> | ::= | <factor> | |
| <factor> | ::= | <number> | "(" <expression> ")" |
What the star removes, and what it removes with it
The EBNF version below generates precisely the same language: same sentences, no more, no fewer. It is half the size, the precedence layering is still visible, and adding % next to * and / is a one-character edit rather than a new production.
The thing to notice is what the notation no longer says. term (("+" | "-") term)* describes a *flat list*: one term, then any number of operator-term pairs. It does not say the list groups to the left. The BNF version said so, structurally, by putting the recursion on the left. So an implementer reading EBNF must get associativity from somewhere else — from prose in the specification, from a precedence table, or from the convention that a star loop is folded left. This is not a flaw so much as a division of labour, but it is the single most common way a hand-written parser ends up computing a - (b - c).
This is also why EBNF and recursive descent fit together so well. expression ::= term (("+" | "-") term)* transliterates directly into a loop, and the loop naturally folds left if you build the node inside it — which is exactly the standard elimination of left recursion, arrived at from the other direction. [[left-recursion]] is the same fact told as a transformation.
| expression | ::= | term (("+" | "-") term)* | Zero or more operator-operand pairs. Flat — the notation is silent on grouping. |
| term | ::= | factor (("*" | "/") factor)* | Precedence is still structural: `term` sits below `expression`, so `*` binds tighter. |
| factor | ::= | number | "(" expression ")" |
- 1.expressionapplying start symbol
- 2.term (("+" | "-") term)*applying expression → term (("+"|"-") term)*
- 3.term "-" term "-" termapplying the star is instantiated twice — note that this step chose a count, not a shape
- 4.factor "-" factor "-" factorapplying term → factor, three times (no "*" or "/" present, so each star is instantiated zero times)
- 5.a - b - capplying factor → number, three times. Nothing in this derivation said whether the result is (a-b)-c or a-(b-c).
The dialects you will actually meet
Nobody writes ISO 14977 EBNF in practice. What you meet is a family of near-identical notations, and the useful skill is recognising which one you are reading in the first ten seconds. The table below covers the ones that appear in real specifications and real tools.
Railroad diagrams — the boxes-and-arrows pictures in the SQLite and JSON documentation — are EBNF rendered visually, and they are worth mentioning because they make one thing obvious that the text hides: a loop in the diagram is a star, and a loop has no direction. The picture cannot express associativity either.
| Notation | Zero or more | Optional | Where you see it |
|---|---|---|---|
| ISO 14977 | { term } | [ term ] | Formal standards documents, rarely elsewhere |
| W3C / XML | term* | term? | XML, XPath, and most W3C specifications |
| Go specification | { term } | [ term ] | The Go spec, and Go-adjacent tooling |
| ANTLR 4 | term* | term? | Generated parsers; also supports term+ |
| Bison / yaccimplementation | not available | not available | Pure BNF — you write the recursion yourself |
| PEG / pegjsimplementation | term* | term? | Ordered choice, so | means "first match wins" |
Rewriting between them, safely
The mechanical rewrite is worth knowing because you will do it in both directions: into EBNF to make a specification readable, and out of EBNF because your parser generator only accepts BNF. Bison in particular has no repetition operator, so every list in a Bison grammar is a hand-written recursion, and which side you recurse on has a real cost — the Bison manual recommends left recursion precisely because right recursion grows the parser stack in proportion to the length of the list.
expression ::= term (("+" | "-") term)*expression ::= expression "+" term
| expression "-" term
| termThe rewrite preserves the generated language whenever the starred group is a complete alternation of operator-operand pairs at one precedence level, because both forms generate exactly the sequences term (op term)^n for every n ≥ 0. It is the *left*-recursive expansion specifically that also matches the left-folding a hand-written star loop performs.
Expanding the same star to the right — expression ::= term "+" expression | term — generates the identical set of sentences and a different set of parse trees. 8 - 4 - 2 then parses as 8 - (4 - 2) and evaluates to 6 instead of 2. The languages are equal; the semantics are not, and no test of the accepted-input set will catch it.
How it works
The steps, in the order the compiler takes them.
- Identify the repeated unit and the separator or operator that joins repetitions of it.
- In EBNF, write
unit (separator unit)*for a non-empty list, or(unit (separator unit)*)?when empty is allowed. - To go the other way, introduce a nonterminal for the list and recurse on the side that matches the intended associativity — left for left-associative operators.
- Check the rewrite by generating three inputs from each form: zero repetitions, one, and three. All three must be accepted by both.
- Check the tree separately, because language equality does not imply tree equality. Evaluate a non-commutative example such as
8 - 4 - 2under both. - Record associativity somewhere the implementer will read it, since the EBNF itself cannot carry it.
How it breaks
What the engineer observes when it goes wrong — not what goes wrong internally.
- A parser is written from an EBNF specification and folds the star loop to the right, so subtraction and division silently produce wrong results while every syntax test passes.
- A grammar is transliterated into Bison with right recursion for a long list, and a file with fifty thousand array elements blows the parser stack — a bug that only appears on generated input.
- Two specifications for the same format use different EBNF dialects and
{ x }is read as literal braces rather than repetition, producing a parser that demands braces nobody writes. - The optional operator is applied to something that can also match empty, producing an ambiguity the generator reports as a conflict on a rule the author considers obviously fine.
When it helps
- Writing a specification humans will read: EBNF is dramatically shorter and the repetition structure of the language is visible at a glance.
- Driving a recursive-descent parser, where each EBNF operator has a direct code shape — star is a while loop, option is an if.
- Comparing two languages' syntax, because the layering and the repetition structure line up when the boilerplate recursion is gone.
When it hurts
- Feeding a BNF-only generator such as Bison, where the star has to be expanded anyway and the EBNF was an intermediate step that could introduce a transcription error.
- When associativity is the point. A left-recursive BNF rule states it; an EBNF star does not, and a specification that only ships EBNF has left a real decision undocumented.
What it costs
Every one of these is paid by something.
- EBNF buys concision and readability, and pays by dropping the structural encoding of associativity — the information has to be restated somewhere the notation cannot check.
- BNF buys an unambiguous statement of grouping directly in the rules, and pays with a rule count that grows with every precedence level and every list in the language.
- Maintaining a specification in EBNF and an implementation grammar in BNF buys readability for both audiences and pays a permanent synchronisation cost, with drift that no test will catch until a program lands in the gap.
What else you could do
What a different compiler or language does instead, and when that is better.
- Railroad diagrams, which are EBNF drawn rather than written. Excellent for documentation and for spotting an unreachable alternative; they cannot express associativity either, and they do not scale past about ten rules.
- A precedence-and-associativity table beside a flat expression rule, which is what Bison's
%left,%rightand%nonassocdeclarations are and what a Pratt parser encodes directly. It puts the missing information in one readable place — see[[operator-precedence]]. - PEG notation, which looks like EBNF but whose
/is ordered choice rather than alternation, so a PEG cannot be ambiguous and also cannot warn you that you meant it to be — see[[parser-generators]].
See it for yourself
The flag, dump or tool that shows you this directly.
- The Go specification at go.dev/ref/spec is EBNF throughout, with associativity stated in prose in the Operators section — a good example of the division of labour this lesson describes.
bison -von a grammar with a list rule shows the expansion you wrote; comparing the state count between a left- and right-recursive version makes the stack-depth argument concrete.- ANTLR's
-Xlogand the generated.interpfile show what the tool did with each*and?— ANTLR expands them internally into loops, which the trace makes visible. - SQLite's syntax diagrams at sqlite.org/syntaxdiagrams.html are railroad rendering of a real, large grammar; find a binary operator and confirm the diagram does not tell you how it associates.
Plausible wrong readings
Stated the way a confident engineer states them.
- "EBNF is more powerful than BNF." It describes exactly the same class of languages. Every EBNF grammar can be mechanically expanded into BNF, which is what tools that only accept BNF do internally.
- "The star tells me the list is left-associative." It tells you nothing about grouping. That is the whole point of this lesson.
- "
{ x }means literally one or more braces." In ISO 14977 and in the Go specification it is the repetition operator. Which dialect you are reading has to be established first. - "Since both forms accept the same inputs, I can pick either." They accept the same inputs and build different trees. For
+nobody notices; for-,/and**everybody does.
Misconceptions
The claim, and what is actually true.
Go deeper
The same idea at increasing depth. Stop wherever it stops being useful.
overview
BNF gives you sequencing and choice; anything repeated has to be written as a recursive rule. EBNF adds star, question mark and parentheses so a list is one line. Both describe exactly the same languages — EBNF is shorter, not stronger.
practical
When you implement from an EBNF specification, the star becomes a while loop and the option becomes an if. Build the AST node *inside* the loop, taking the accumulated node as the left operand, and you get left associativity. Build it after the loop from a collected list and you have to decide the fold direction explicitly — at which point write a comment saying which, because the grammar you copied from did not.
advanced
The deeper reason the two notations diverge is that BNF is a *generative* notation whose derivations are trees, while the EBNF operators are *regular* operators lifted into a context-free setting. A starred group is a regular expression over grammar symbols, and regular expressions have no tree structure — that is precisely why the star cannot carry associativity, and it is the same reason [[regular-languages]] cannot express nesting. Tools that accept EBNF resolve this by expanding stars into fresh nonterminals with a chosen recursion direction, so the tree structure is reintroduced by the tool rather than by the author. Two tools may choose differently, and then the same EBNF produces two different trees.
How much this depends on
Nothing in this domain is true of every compiler. These say how much.
*, + and ? and expands them internally. A grammar copied from a W3C specification into Bison therefore needs manual expansion, and that expansion is where associativity bugs are introduced.If you were asked this in an interview
- Rewrite
expression ::= term (("+" | "-") term)*in pure BNF, and say which associativity your rewrite chose. - Bison has no
*operator. Which side do you recurse on for a long argument list, and why does it matter? - A specification is written in EBNF and two implementations disagree about
8 - 4 - 2. Who is at fault?