Grammarspec

Formal Grammars

A grammar is a finite set of rules that decides an infinite set of token sequences. Writing one down separates "what is a legal program" from "how do I recognise one", and that separation is the reason a language can have more than one implementation.

The question

Why write a grammar down at all instead of just writing the parser?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

At this point the program is a flat, finite sequence of tokens — kind, text and span, with whitespace and comments already gone. The grammar is not a representation of the program; it is a specification of the *set* of token sequences that count as programs. The question it exists to answer is membership: is this particular sequence in the language, and if so, with what structure?

What this phase may assume or do

A grammar is written over token kinds, so it is entitled to assume the lexer has already decided which characters group together, classified each group, and discarded trivia. It may not assume anything a later phase establishes: not that names are declared, not that types agree, not that the arity of a call matches. Anything a grammar tries to enforce about *meaning* it will enforce wrongly.

Key points

A grammar is terminals, nonterminals, a start symbol and productions — and nothing else. Lookahead, backtracking and stacks belong to parsers.
The grammar generates a language; a parser recognises one. Separating the two is what lets several implementations agree.
Terminals are token kinds, so a grammar is written against the lexer's output and may assume classification has already happened.
A grammar constrains shape only. Declaration, arity and typing rules live in later phases by necessity, not by convention.
The two-production expression grammar already contains ambiguity, precedence and associativity as unsolved problems.

Four parts, and only four

A formal grammar is a four-tuple: a set of terminals (the token kinds the lexer produces), a set of nonterminals (the names you invent for grammatical categories), a start symbol, and a finite set of productions of the form "this nonterminal may be replaced by this sequence". Nothing else is in the definition. There is no notion of an input pointer, a stack, backtracking or lookahead — those belong to parsing algorithms, and the whole point of writing the grammar separately is that they do not appear here.

That separation buys something concrete. GCC, Clang, MSVC, ICC and a dozen frontends in language servers all accept the same C++ programs, not because they share code but because they share a document. When two implementations disagree, the grammar is the thing you can point at. A parser written without a grammar is its own specification, and the only way to answer "is this legal?" is to run it.

The smallest interesting grammar in this domain is two productions over one nonterminal. It is worth staring at, because everything the rest of the module deals with — ambiguity, precedence, associativity, left recursion — is already latent in it.

The whole module in two productions

expression	→	number	The base case. `number` is a terminal — a token kind the lexer already produced, not a rule about digits.
expression	→	expression "+" expression	The recursive case, and the source of every problem in this module. Nothing here says how a three-operand sum groups.

Deriving 1 + 2 + 3

1.expressionapplying start symbol
2.expression "+" expressionapplying expression → expression "+" expression
3.expression "+" expression "+" expressionapplying expression → expression "+" expression, on the leftmost expression
4.number "+" expression "+" expressionapplying expression → number
5.number "+" number "+" expressionapplying expression → number
6.number "+" number "+" numberapplying expression → number
7.1 + 2 + 3applying the lexer already classified 1, 2 and 3 as number tokens; the derivation only ever manipulated kinds

What "generates" means, and what it does not

specLanguage standards state their syntax as a grammar and then immediately add rules the grammar cannot express. The C standard has constraints and semantics clauses alongside the syntax; the C++ standard resolves several syntactic ambiguities with prose ("if it can be a declaration, it is a declaration"). Reading only the grammar productions of a standard will tell you what parses, never what compiles.

A grammar *generates* a language: start from the start symbol, repeatedly replace a nonterminal using some production, and every sequence of terminals you can reach is a member. The derivation above is one such walk. Recognition is the inverse problem — given a sequence, find a walk that produces it — and that inverse problem is what a parser solves. The grammar is silent on how.

This is why a single grammar can be handed to genuinely different machinery. The same productions can drive a hand-written recursive-descent parser ([[recursive-descent]]), a table-driven LR automaton generated by Bison ([[lr-parsing]]), or a Pratt loop that never mentions the nonterminals at all ([[pratt-parsing]]). They will accept the same strings if the grammar is unambiguous. If it is not, they will disagree, and the disagreement will be invisible until someone writes the program that distinguishes them.

The catch is that a grammar can only talk about *shape*. There is no production that can say "this identifier must already be declared", because a production may only look at the nonterminal on its left-hand side, never at what surrounds it. That restriction is what [[context-free-grammars]] is about, and it is the reason [[semantic-analysis]] exists as a separate phase rather than as more grammar.

Terminals are token *kinds*, not characters. number is one terminal, however many digits it had.
Nonterminals are names you invent. The grammar does not care what you call them; the diagnostics do, which is why expression beats E.
A production is a rewrite rule, not a function call, even though recursive descent implements it as one.
The start symbol picks out what a whole input must be — usually compilation-unit, program or module, not expression.

Where the grammar stops being enough

Every real language has a layer of rules that live outside the grammar, and knowing where that line falls is most of the value of this lesson. "Both operands of + must be numbers" is a typing rule. "A break must be inside a loop" is usually a semantic check, though some grammars fake it with extra nonterminals. "A variable must be declared before use" is name resolution. None of them is syntax, and a compiler that tries to enforce them in the parser produces error messages that name grammar rules instead of naming the mistake.

The practical consequence: when a language change is proposed, the first question is which layer it lands in. A new operator is a grammar change and a precedence-table change. A new inference rule is a type-checker change and no grammar change at all. Confusing the two is how a "small syntax addition" turns into six months of work.

Which layer answers which question, for f(x) + 1

Question	Answered by	Why not the grammar
Are these tokens grouped legally?	The grammar	This is exactly what a grammar is for.
Does `+` bind looser than the call?	The grammar	Encoded as rule layering, or as a separate precedence table beside it.
Does `f` exist?typical	Name resolution	A production cannot consult a table of declarations.
Does `f` take one argument?	Semantic analysis	Arity varies per declaration; a finite production set cannot encode it.
Is `f(x)` a number?	The type checker	Types are computed, not matched.
Will it overflow?typical	Nobody, statically	Not a syntactic or usually even a static property at all.

How it works

The steps, in the order the compiler takes them.

Choose the terminal alphabet by fixing the token kinds the lexer emits — this is the interface between [[lexical-analysis]] and the grammar.
Name a nonterminal for every grammatical category the language distinguishes, and a start symbol for a whole input.
Write productions as rewrite rules; a nonterminal with several alternatives becomes several productions, or one production with |.
Verify by derivation: pick representative inputs and check that a sequence of rewrites reaches each of them.
Verify the negative direction too: pick inputs that must be rejected and confirm no derivation exists — this is the step everyone skips.
Hand the finished grammar to a parser generator or implement it by hand; either way the grammar remains the artefact reviewers read.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

The grammar accepts a program the language designers never intended, and it is only discovered years later when someone writes it and asks what it means — at which point rejecting it is a breaking change.
A rule that should have been a semantic check is encoded as extra nonterminals, and the resulting error message says "expected loop-body-statement" instead of "break outside a loop".
Two implementations disagree on a corner case, and because neither was written from the grammar there is no document to appeal to. Code that compiles on one toolchain fails on another with a syntax error.
The grammar and the implementation drift apart, so the published grammar no longer describes what the compiler accepts, and every tool written from the document — formatters, highlighters, language servers — is subtly wrong.

When it helps

Specifying a language that will have more than one implementation, or one implementation plus a formatter, a highlighter and a language server.
Reviewing a syntax proposal: the productions make the interaction with existing syntax visible before anyone writes a parser.
Debugging a parser: deriving the failing input by hand tells you whether the grammar or the implementation is wrong, which are very different bugs.

When it hurts

For a throwaway configuration format with six keys, a grammar is ceremony. A hand-written scanner and a switch statement will be shorter and just as correct.
When the language is genuinely not context-free, a pure grammar becomes a fiction maintained beside the real parser — see the C typedef problem in [[lexer-hazards]].

What it costs

Every one of these is paid by something.

Maintaining a grammar separately from the parser costs a synchronisation burden forever: every syntax change is two edits, and drift between them is silent. It buys a document that tools and other implementations can be written from.
A grammar precise enough to be machine-checkable is usually less readable than the informal one in a tutorial. You pay in reader effort for the ability to generate a parser from it.
Pushing rules into the grammar to catch them early costs diagnostic quality — the parser can only report grammar-shaped errors — and buys a smaller semantic phase.

What else you could do

What a different compiler or language does instead, and when that is better.

A parser-is-the-spec approach, which is what most scripting languages started with and several still are: fast to change, impossible to reimplement faithfully.
An operator table plus a tiny grammar, as in Pratt parsing: the productions describe statements and the table describes expressions, which is far easier to extend with new operators — see [[pratt-parsing]].
A PEG, which replaces the generative reading with an ordered, recognition-first one: alternatives are tried in order and the first success wins, so a PEG is unambiguous by construction and cannot tell you it was ambiguous — see [[parser-generators]].

See it for yourself

The flag, dump or tool that shows you this directly.

Read a real one: the C++ standard collects its grammar in an annex; the Go specification embeds EBNF beside every construct; CPython's grammar lives in Grammar/python.gram in the source tree.
bison -v grammar.y writes grammar.output containing every production numbered, plus the state machine that was built from it.
python3 -c "import ast; print(ast.dump(ast.parse('1 + 2 + 3')))" shows the structure the grammar dictated for a string you choose.
astexplorer.net renders the tree for the same source under a dozen different parsers, which makes grammar disagreements visible in seconds.

Plausible wrong readings

Stated the way a confident engineer states them.

"The grammar defines the language." It defines the syntax. Every rule about declaration, typing and effect lives outside it, and those are most of the language.
"If the grammar accepts it, it compiles." The grammar accepting it is the first of five or six gates. x = undeclared + "s" parses cleanly in most languages.
"Writing the grammar is the hard part of designing syntax." Deciding what must be rejected is the hard part. Writing productions for what you already know you want takes an afternoon.
"Nonterminal names do not matter." They become the vocabulary of every error message a generated parser emits.

Misconceptions

The claim, and what is actually true.

A grammar tells the parser what to do.

It tells you which sequences are legal. Turning that into an algorithm is a separate, non-trivial step, and several algorithms only work on grammars written a particular way.

Terminals are characters.

Terminals are token kinds. The character-level rules are the lexer's regular grammar, which is deliberately a different and weaker formalism — see [[regular-languages]].

Any language can be given a context-free grammar.

Only the context-free ones. C++ template angle brackets and C typedef names both need information a context-free grammar cannot carry.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

A grammar is a list of rules saying what may be replaced by what. Start from a start symbol, apply rules, and every sequence of tokens you can reach is a legal program. Write it down so that the parser, the formatter, the highlighter and the next implementation all agree on the same answer.

practical

When a parser rejects something you think is legal, derive the input by hand from the published grammar first. If a derivation exists, the parser has a bug. If none exists, the grammar is what you should be arguing about, and the parser is behaving. This two-minute check routinely saves an afternoon, because the two bugs have completely different fixes and completely different owners.

advanced

The interesting question is not "is this grammar correct" but "what does this grammar make expensive later". A grammar with a nonterminal per precedence level encodes precedence structurally and is trivially unambiguous, but adding one operator means editing several rules and it produces deep, mostly-unary parse trees. A flat expression grammar plus a precedence table is ambiguous as written and needs the disambiguation bolted on, but new operators are one table row. Both ship in production compilers; the choice is a maintenance-cost decision, not a correctness one.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

specThe four-part definition and the generative reading are standard formal-language theory and do not vary by implementation. What varies enormously is how much of a real language a published grammar actually covers: C++ leaves several ambiguities to prose disambiguation rules, and no grammar covers the preprocessor.

typicalMainstream compilers keep the grammar as a document and the parser as hand-written code, so the two can drift. Implementations generated directly from the grammar — many Bison and ANTLR frontends — cannot drift, but pay for it in diagnostic quality and in the difficulty of error recovery.

If you were asked this in an interview

What is the difference between a grammar and a parser, and why would you keep them separate?
Give me a rule about a program that a context-free grammar cannot express, and say which phase enforces it instead.
You are adding a new binary operator to a language. Which artefacts change, and in what order?

Connections

API Designschema-first-vs-code-first

Databasesql-parser-internals

Domains that do not exist yet

Testing & Reliability Engineering — Specification-based testing — deriving test inputs from a written specification rather than from the implementation
A grammar is the ideal artefact to generate tests from, and grammar-based fuzzing is how most parser bugs are actually found. The technique is general and is owned there; [[compiler-fuzzing]] is its compiler-specific instance here.