BNF

BNF#

BNF (Backus-Naur Form) and its variants are the standard notations for describing the syntax of formal languages. If you’ve read a programming language specification, you’ve read BNF.

The Original BNF#

A BNF grammar is a set of production rules:

<expr>   ::= <term> | <expr> "+" <term>
<term>   ::= <factor> | <term> "*" <factor>
<factor> ::= "(" <expr> ")" | <number>
<number> ::= <digit> | <number> <digit>
<digit>  ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Conventions.

  • <name>, a non-terminal (a rule).

  • Quoted strings, terminals (literal text).

  • ::=, “is defined as”.

  • |, alternation.

The right-hand side describes what’s allowed; the left-hand side names the construct.

EBNF (Extended BNF)#

ISO 14977 layered shorthand on top of BNF for the patterns that recursion makes verbose, optional groups, zero-or-more repetition, explicit grouping. The result is shorter, easier to read, and the variant most modern language references reach for when describing syntax.

EBNF adds shorthand for things you’d otherwise express with recursion.

expr   = term { "+" term } ;
term   = factor { "*" factor } ;
factor = "(" expr ")" | number ;
number = digit { digit } ;
digit  = "0" | "1" | ... | "9" ;

Operators.

Notation

Meaning

[ x ]

optional (zero or one)

{ x }

zero or more

( a | b )

grouping

"text"

terminal literal

;

end of rule

EBNF is what most modern language references use (JavaScript / Rust / Python all reach for variants of it).

ABNF#

The IETF’s preferred grammar notation, defined in RFC 5234. Differences from EBNF are mostly cosmetic: = for “is”, / for alternation, * for repetition with min/max counts. A small core rule set covers ASCII building blocks that internet protocols repeatedly reference.

ABNF is what IETF specifications use.

email-addr = local-part "@" domain
local-part = 1*ALPHA
domain     = 1*( ALPHA / DIGIT / "-" ) *( "." 1*( ALPHA / DIGIT / "-" ) )

Differences.

  • = instead of ::=.

  • / instead of |.

  • * for repetition: *x (zero or more), 1*x (one or more), 2*4x (between 2 and 4).

  • [ x ] for optional.

  • Built-in core rules: ALPHA, DIGIT, HEXDIG, CR, LF, CRLF, SP, HTAB.

Found in most internet RFCs (HTTP, MIME, SMTP, JSON-RFC-8259, SDP).

PEG (Parsing Expression Grammars)#

PEG looks like EBNF on the surface but works differently underneath. The big shift is ordered choice; the first alternative that matches wins, full stop, which makes the grammar unambiguous by construction. Lookahead operators add expressive power that BNF lacks.

PEG looks like EBNF but with subtly different semantics.

expr     <- term ('+' term)*
term     <- factor ('*' factor)*
factor   <- '(' expr ')' / number
number   <- [0-9]+

Differences from BNF.

  • / is ordered alternation, first match wins.

  • No ambiguity by construction; PEGs are unambiguous.

  • Lookahead operators: &x (positive), !x (negative).

  • Recursion-friendly; widely supported by parser-generator libraries (pest, peg.js, Parsimmon, rust-peg).

Closer to how you’d actually implement a recursive-descent parser.

Reading vs. Writing#

For most operators, BNF / EBNF / ABNF are read-only; you encounter them in language specs, RFCs, and documentation. Knowing how to read them is the practical skill.

  • Identify start symbol (often the first rule).

  • Trace alternations.

  • Recognize repetition.

  • Spot terminals (literals you’d actually type).

Writing grammars is a smaller niche, for DSL designers, language implementers, parser writers.

Where Grammar Notations Show Up#

Grammar notations are how formal-language documentation describes itself. Programming language references, IETF RFCs, SQL standards, network protocols, and DSL specifications all reach for some flavor (BNF, EBNF, ABNF, or PEG) to describe what is and isn’t valid input.

  • Programming language specs, ECMA-262 (JavaScript), Rust Reference, Python language reference, JLS (Java).

  • IETF RFCs, ABNF.

  • Database SQL standards, BNF.

  • Network protocols, ABNF.

  • DSL design, when defining your own little language.

  • Parser generators, ANTLR, Bison, Yacc, Tree-sitter, pest.

Parser Generators#

The tools that turn a grammar file into a working parser. The generators differ in algorithm class (LL, LR, PEG, incremental), output language, and ergonomics. For DSLs and small languages, hand-written parser combinators in code often beat a generator with all its build-time machinery.

Tools that consume a grammar and produce a parser.

  • ANTLR, LL(*) parser generator with multi-language targets.

  • Bison / Yacc, LALR(1); classic.

  • Tree-sitter, modern incremental parser generator; the engine behind syntax highlighting in Neovim, GitHub, Helix, Zed.

  • pest, Rust PEG.

  • nom, Rust parser combinators (not a generator, but the alternative).

  • Parsimmon / Chevrotain, JS.

  • Lark, Python; supports EBNF.

For DSLs and small languages, parser combinators in code (nom, Parsec, parsy) often beat generators; the grammar lives in the implementation language and is testable like any other code.

Common Pitfalls#

The traps that catch grammar authors. Left recursion clashes with LL parsers; ambiguity is allowed in BNF but forbidden in PEG; whitespace and comment handling crosses into the lexer; operator precedence is encoded either via grammar layering or generator-specific declarations.

  • Left recursion, some parser generators (LL-family) reject it; others (PEG, with care) accept it. Refactor with iteration when in doubt.

  • Ambiguity, BNF allows it; PEG forbids it; LR generators detect it; LL might accept it silently.

  • Whitespace and comments, specs usually treat them as separate lexer concerns; grammars often elide them.

  • Operator precedence, expressed via grammar layering (the classic expr → term → factor cascade) or via precedence declarations (Bison’s %left / %right).

EBNF Variants in the Wild#

The dialects an operator may meet across documents. W3C specs, the ISO standard, Bison/Yacc grammars, and ANTLR files all use a flavor of EBNF with cosmetic differences – = versus ::=, | versus /, distinct repetition syntax. The core ideas survive in every variant.

  • W3C EBNF, used in XML, CSS, and other W3C specs.

  • ISO 14977, the official standard, rarely used as-is.

  • Bison/Yacc syntax, the BNF-with-semantic-actions used in the classic toolchain.

  • ANTLR, its own EBNF flavor with semantic predicates and actions.

The differences are mostly cosmetic; the core ideas (rules, alternation, repetition, optional, grouping) are universal.

Contents