Grammarspec

Productions & Derivations

A derivation is the proof that a token sequence is in the language. Leftmost and rightmost derivations are the two canonical orders, and they are exactly the orders that top-down and bottom-up parsers reconstruct.

The question

What does it actually mean to say a parser "derives" a program, and why does the order of the rewrites matter?

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

What the program is here

A *sentential form*: a mixed sequence of terminals and nonterminals that sits between the start symbol and the finished token sequence. It is the intermediate state of the membership proof, and it exists to answer "how far along is this derivation, and what must still be expanded?" A parser never materialises it as a data structure, but every parsing algorithm is reconstructing one.

What this phase may assume or do

A rewrite step is legal only if the symbol being replaced is a nonterminal that appears in the current sentential form, and the production used has exactly that nonterminal on its left-hand side. Nothing about the surrounding symbols may influence the choice — that restriction is what makes the grammar context-free, and it is what lets a parser expand a nonterminal without knowing where it sits.

Key points

A derivation step replaces one nonterminal using one of its productions; a derivation is a sequence of such steps from the start symbol.
A sentential form is the intermediate mixed sequence; a sentence is a sentential form with no nonterminals left.
Leftmost and rightmost derivations are canonical because they correspond to top-down and bottom-up parsing respectively.
Many derivations share one parse tree; the tree forgets the order of expansion, which is the information a derivation adds.
Two different parse trees for one input, not two different derivations, is what ambiguity means.
LR reductions are rightmost derivation steps run backwards — that single fact makes shift-reduce traces readable.

One step at a time

A derivation step picks a nonterminal in the current sentential form and replaces it with the right-hand side of one of its productions. A derivation is a sequence of such steps starting at the start symbol. If the sequence ends with a form containing no nonterminals, that form is a *sentence* of the language, and the derivation is the proof.

Two orders are singled out because they correspond to real algorithms. A leftmost derivation always expands the leftmost nonterminal; a rightmost derivation always expands the rightmost one. Neither is more correct; both reach the same sentence when the grammar is unambiguous, and they build the same tree. The reason to care is that a top-down parser such as [[recursive-descent]] or an LL table produces a leftmost derivation as it goes, while an LR parser produces a rightmost derivation *in reverse* — every reduction it performs is a rightmost derivation step run backwards, which is why [[shift-reduce]] looks nothing like the grammar until you know this.

The grammar below is the layered expression grammar that the rest of this module keeps returning to. Its layering — expression, term, factor — is precedence encoded structurally, which is the subject of [[operator-precedence]]. Here it is just a grammar with enough rules that the derivation is interesting.

A leftmost derivation of 1 + 2 * 3

expression	::=	expression "+" term \| term	Left-recursive on purpose: it makes `+` group to the left. See `[[left-recursion]]` for what that costs a top-down parser.
term	::=	term "*" factor \| factor	A separate level for ``, and it sits below `+`, so `` binds tighter.
factor	::=	number \| "(" expression ")"	The parenthesised alternative is what lets an author override the layering.

Deriving 1 + 2 * 3

1.expressionapplying start symbol
2.expression "+" termapplying expression → expression "+" term
3.term "+" termapplying expression → term
4.factor "+" termapplying term → factor
5.number "+" termapplying factor → number
6.number "+" term "*" factorapplying term → term "*" factor
7.number "+" factor "*" factorapplying term → factor
8.number "+" number "*" factorapplying factor → number
9.number "+" number "*" numberapplying factor → number — no nonterminals remain, so this is a sentence

The derivation is not the tree

A derivation is a sequence; a parse tree is a structure. The tree records *which* production expanded *which* nonterminal, and deliberately forgets the order in which the expansions happened. That is exactly why several derivations can share one tree: expanding the left branch fully before touching the right branch, or alternating between them, produces the same parent-child relationships.

This is a useful diagnostic. If two derivations of the same input yield the same tree, the grammar is fine and you were merely walking it differently. If two derivations of the same input yield *different* trees, the grammar is ambiguous and the language has not been specified — see [[ambiguous-grammars]]. The formal statement is that an unambiguous grammar has exactly one leftmost derivation per sentence, which is why leftmost is the canonical one to compare.

The tree below is the one the derivation above produced. Notice that number appears three times as a leaf: in the tree these are distinct nodes with distinct spans, even though the derivation wrote the same symbol. Spans are how the parser keeps them apart, and where they came from is [[source-locations]].

The parse tree the derivation built — every nonterminal it expanded is a node

Parse tree — every grammar rule and every token

expression“1 + 2 * 3”

├── expression“1”

│ └── term“1”

│ └── factor“1”

│ └── number (1)“1”

├── "+"“+”— A punctuation node. An AST would not keep it — the node kind carries the information instead.

└── term“2 * 3”

├── term“2”

│ └── factor“2”

│ └── number (2)“2”

├── "*"“*”

└── factor“3”

└── number (3)“3”

Read it asCount the chain expression → term → factor → number on the left: four nodes for one digit. That is what precedence-by-layering costs in tree size, and it is the single strongest argument for [[parse-tree-vs-ast]]. The AST for this input is three nodes.

Why the direction shows up in real parsers

typicalThe error-message row describes the default output of hand-written descent parsers versus stock Bison. It is a property of effort, not of the algorithm: Bison 3.8 with %define parse.error detailed reports expected token sets, and rustc's hand-written parser earns its diagnostics with a great deal of construct-specific code rather than by being top-down.

A recursive-descent parser calls parseExpression, which calls parseTerm, which calls parseFactor, which consumes 1. Read the call stack at that moment: it is the left spine of the tree, which is the prefix of the leftmost derivation. The parser is *choosing* which production to apply before it has seen the input the production covers, which is why top-down parsing needs lookahead and why it cannot cope with left recursion.

An LR parser does the opposite. It shifts 1 onto a stack, then reduces it to factor, then to term, then to expression — committing to a production only after the entire right-hand side is on the stack. Read those reductions bottom to top and you have the rightmost derivation backwards. Because it decides late, it can handle left recursion and a strictly larger class of grammars, and it pays for that with a construction step that produces tables no human reads — see [[ll-vs-lr]].

Same grammar, same input, two reconstruction orders

	Top-down (LL, recursive descent)	Bottom-up (LR)
Derivation produced	Leftmost, forwards	Rightmost, in reverse
When it commits to a production	Before consuming the right-hand side	After the whole right-hand side is on the stack
Left recursion	Non-terminating; must be eliminated first	Handled natively, and preferred
What the code looks liketypical	One function per nonterminal — readable	A state table — not readable
Error message qualitytypical	Names the construct being parsed	Names a state number unless effort is spent

How it works

The steps, in the order the compiler takes them.

Begin with the sentential form consisting of just the start symbol.
Select a nonterminal in the current form — the leftmost one for a leftmost derivation, the rightmost for a rightmost one.
Select a production whose left-hand side is that nonterminal, and textually substitute its right-hand side.
Repeat until no nonterminal remains; the result is a sentence, and the sequence of productions used is the proof of membership.
To build the parse tree instead of the sequence, record each substitution as a parent node with the right-hand side symbols as its children, in order.
To recover the derivation from a finished parse, do a preorder walk for the leftmost derivation and a reverse postorder walk for the rightmost.

How it breaks

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

A recursive-descent parser written directly from a left-recursive production recurses forever and the compiler dies with a stack overflow on the first expression it sees — no error message, just a crash.
A hand-traced derivation is done rightmost while the parser under test is top-down, so the trace and the parser disagree at every step and hours go into a discrepancy that was never real.
A parser generator reports a conflict on a grammar the author derived by hand successfully. The derivation existed; the *deterministic* one-token-lookahead choice did not, and those are different claims.
The parse tree is built with the children in reverse because a bottom-up parser pops the stack without re-reversing, so a - b evaluates as b - a and nothing errors.

When it helps

Debugging a parser generator conflict: deriving the ambiguous input both ways shows precisely which two productions are competing.
Reviewing a grammar change: deriving three or four representative inputs by hand catches structural mistakes before any code is generated.
Reading an LR trace: knowing that reductions are reversed rightmost steps turns an opaque log into a legible derivation.

When it hurts

Hand-derivation does not scale. Nobody derives a realistic statement in a real language by hand, and trying to is a sign the grammar needs shrinking rather than tracing.
For an ambiguous grammar, finding one derivation proves nothing useful — the interesting question is how many trees exist, and derivation-by-hand is a bad way to answer it.

What it costs

Every one of these is paid by something.

Encoding precedence as derivation layers makes the grammar unambiguous by construction and costs one nonterminal per precedence level, deeper parse trees, and an edit to several rules every time an operator is added.
A leftmost, top-down reconstruction buys readable code and construct-aware diagnostics, and pays with an inability to handle left recursion and a smaller class of accepted grammars.
A rightmost, bottom-up reconstruction buys grammar generality and native left recursion, and pays in generated tables nobody can inspect and error messages that must be reconstructed from state numbers.

What else you could do

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

Earley parsing derives all parses of any context-free grammar at once, in cubic time worst case, which is what you want for natural language or for a grammar you are not allowed to rewrite.
GLR forks the parse at every conflict and prunes the branches that die, which is how tools that must accept real C++ without a preprocessing pass survive — see [[parser-generators]].
Pratt parsing abandons the nonterminal-per-level structure entirely, deriving expressions with a binding-power loop; the derivation still exists, but no production ever names term or factor — see [[pratt-parsing]].

See it for yourself

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

bison -v grammar.y writes grammar.output: every production numbered, every state, and every reduction — read it alongside a trace to see the reversed rightmost derivation directly.
bison -Dparse.trace plus yydebug = 1 prints each shift and reduce at run time, which is the derivation happening in front of you.
ANTLR's grun MyGrammar expr -gui renders the parse tree for an input you type, including the one-child chains that layering produces.
Our own grammar deriver at /compilers/grammar steps a derivation forwards and backwards over a grammar you can edit.

Plausible wrong readings

Stated the way a confident engineer states them.

"Leftmost and rightmost derivations give different trees." They give the same tree for an unambiguous grammar. Different trees mean the grammar is ambiguous, which is a different problem entirely.
"The parser builds the derivation." The parser builds the tree; the derivation is a way of talking about the order it did so. Nothing stores a list of sentential forms.
"If I can derive it, the parser will accept it." Only if the parser's algorithm can *find* that derivation deterministically with the lookahead it has. Derivability and parseability by a given algorithm are separate properties.
"Bottom-up parsing means reading the input right to left." It reads left to right like everything else. The *derivation* it reconstructs is the rightmost one, reversed.

Misconceptions

The claim, and what is actually true.

A derivation and a parse tree are the same information.

The tree is a quotient of the derivation: it keeps which productions were used and where, and discards the order. That is why many derivations map to one tree.

A rightmost derivation means the parser processes the last token first.

It means the parser commits to productions in an order that, reversed, is rightmost. Input consumption is left to right throughout.

Go deeper

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

overview

Deriving means starting from the start symbol and replacing nonterminals with the right-hand sides of rules until only tokens remain. Do it always-leftmost and you are imitating a top-down parser; do it always-rightmost and reverse it and you are imitating a bottom-up one.

practical

The practical payoff is reading a Bison trace. Each Reducing stack by rule 7 line is one rightmost derivation step, backwards. Write the rules down in the order they were reduced, reverse the list, and you have the derivation — which tells you exactly where the parser thought it was when it went wrong, rather than which state number it was in.

advanced

The derivation order also decides what an action can see. In a bottom-up parser, a semantic action attached to a production runs when the production is reduced, so every child is already built and every attribute of every child is available — this is what makes synthesised attributes natural in LR and inherited attributes awkward. In a top-down parser the reverse holds: the parent is entered before its children exist, so inherited context flows down easily and synthesised results must be threaded back by return value. Attribute grammars formalise this, and it is the reason two parser families produce such different-looking semantic code for the same language.

How much this depends on

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

specThe leftmost/rightmost correspondence with top-down and bottom-up parsing is a theorem about context-free grammars, not an implementation detail, and holds for every conforming LL and LR parser. What is implementation-specific is whether a given tool exposes the derivation at all.

typicalMost production compilers today use hand-written recursive-descent or Pratt parsers rather than generated LR tables, chiefly for error recovery and diagnostics. GCC moved from Bison to a hand-written C++ parser in 4.1; Clang and rustc were hand-written from the start. Generated parsers remain common in database engines and in DSLs, where diagnostics matter less.

If you were asked this in an interview

Give a leftmost derivation of 1 + 2 * 3 for a grammar with expression, term and factor levels.
Why do LR parsers produce a reversed rightmost derivation, and what does that let them do that LL parsers cannot?
Two derivations of one input reach the same sentence. Is the grammar ambiguous? What would prove that it is?

Connections

DSArecursion stack binary-tree