a derivation

A derivation is the step-by-step story of how a grammar built a particular string. Picture a sentence growing in front of you: you start with one placeholder, swap it for a rule's right side, then swap one of the new placeholders, and so on, narrating each move, until you arrive at a string of nothing but real symbols. That recorded sequence of rewrites IS the derivation.

Formally, a derivation is a sequence of strings (sentential forms) where each one comes from the previous by applying a single production rule — written w0 => w1 => w2 => ... => wn — beginning with the start symbol and ending with a string of terminals. We write S =>* w (read 'S derives w in zero or more steps') to mean there is some such finite sequence. For example with rules S → S S | ( S ) | ε, one derivation of '()' is S => (S) => () (using S → (S) then S → ε). A string is in the language of the grammar exactly when there exists a derivation of it from the start symbol.

Derivations are how meaning gets attached to syntax: discovering a derivation for a piece of source code is essentially what a parser does, and the order of rewriting can be standardised (leftmost, rightmost) to make derivations unique and comparable. A crucial subtlety: a single STRING may have many different derivations that merely reorder independent choices and yet describe the SAME structure — so derivation order alone is not the right notion of 'structure'. The structure is captured by the parse tree, which collapses all those orderings into one picture; when a string has two genuinely different parse trees, the grammar is ambiguous.