From a pile of rules to a step-by-step story
In the previous guide you met the context-free grammar as a 4-tuple (V, Σ, R, S): a set of variables V, an alphabet of terminals Sigma (Σ, the actual letters), a finite pile of production rules R, and a chosen start symbol S. But a pile of rules just sitting there generates nothing — you have to use them. A grammar does not read a string and answer yes or no the way a DFA does; it BUILDS strings, starting from the seed S and rewriting one placeholder at a time until only real letters remain. This guide is about exactly that building process and how we record it.
The single atomic move is the derivation step, written u => v. It means: take the current string u, find ONE occurrence of some variable A inside it, and replace that one A with the right-hand side of one rule A → α. Everything around the A stays untouched. So if u looks like xAy (where x and y are any strings of symbols) and the grammar has the rule A → α, then in one step xAy => xαy. That is the whole mechanism — one rule, one variable, one swap. A grammar's entire power is just many of these tiny swaps chained together.
Chain those steps from the start symbol all the way down to a string of pure terminals, and you have a derivation: a sequence S => w1 => w2 => ... => wn where wn contains no variables left to expand. We write S =>* w (read 'S derives w in zero or more steps') to say such a chain exists. The starred arrow allows zero steps, so trivially S =>* S. A string w belongs to the language of the grammar precisely when there is SOME derivation S =>* w that ends in terminals only — that is the entire definition of what the grammar generates.
Sentential forms: snapshots along the way
Halfway through a derivation you hold a half-finished thing: part real letters, part placeholders still waiting to be expanded — like a fill-in-the-blank sentence with some blanks filled and some still empty. Each such intermediate string is a sentential form: formally, any string of terminals and variables w with S =>* w. The very first sentential form is the lone start symbol S itself (reached in zero steps). Every line of a derivation is a sentential form; the derivation is just the list of them.
When a sentential form contains ONLY terminals — no variables left — it has a special name: a sentence, and it is exactly a member of the language. So 'sentential form' is the general notion (mid-construction, may still hold variables), and 'sentence' is the finished special case. A common slip is to call a half-built string with leftover variables a sentence; it is not — it is only a sentential form until every last variable has been rewritten away. The language generated by the grammar is precisely the set of its sentences: all the terminal-only strings reachable from S.
Take the grammar S → A B, A → a A | a, B → b and watch the snapshots fly by: S => A B => a A B => a a B => a a b. The first four strings (S, then A B, a A B, a a B) are sentential forms that still hold at least one variable; only the last, a a b, is all terminals — that one is the sentence, and it proves S =>* aab puts 'aab' in the language. Reading down that column of snapshots is reading the derivation; the moment the variables run out, you have landed in the language.
Which variable next? Leftmost and rightmost
There is a freedom hiding in the derivation step: when a sentential form holds SEVERAL variables, which one do you rewrite next? Nothing in the definition forces a choice, so the same string can be built by many different sequences that merely differ in which order you attacked the variables. To tame this, we adopt a discipline. A leftmost derivation always rewrites the LEFTMOST variable at every step — like reading and writing strictly left to right, never jumping ahead to a later blank before finishing an earlier one. We sometimes mark these steps =>lm.
Its mirror image is the rightmost derivation (marked =>rm), which always reaches for the RIGHTMOST variable first. Both disciplines describe the very same notion of derivation — they only fix which variable to attack, removing that one freedom and leaving only the genuine choice of which rule to apply. Take the grammar S → A B, A → a, B → b B | b. A rightmost derivation of 'abb' fully expands B before touching A: S =>rm A B =>rm A b B =>rm A b b =>rm a b b. A leftmost derivation of the same string does A first: S =>lm A B =>lm a B =>lm a b B =>lm a b b. Same string, same structure — different step order.
The parse tree: one picture for many derivations
Here is the crux of the whole guide. A derivation is a long verbal play-by-play; a parse tree is the same information drawn as one picture, and it quietly throws away the part that never mattered — the order in which independent choices happened to be made. The tree's shape shows how the pieces nest inside one another. It is the structural skeleton of the string, and it is the honest answer to 'how was this put together?'
How is the tree built? The root is labelled with the start symbol S. Every internal node is labelled with a variable, and the children of a node labelled A — read left to right — spell out exactly the right-hand side of some rule A → α that was used to expand that A. The leaves are labelled with terminals (or with ε when a rule of the form A → ε was applied, contributing nothing). So each internal node is one rule application, and the whole tree records the entire derivation at once, independent of the order the rules fired.
Run your finger along the leaves from left to right and write down what you see: that string of terminals is the yield of the tree (also called its frontier). The yield is read off the LEAVES only — the variables labelling internal nodes are part of the structure but never part of the yield. This gives a second, fully equivalent definition of the language: a string w is in the language of the grammar exactly when there exists a parse tree rooted at S whose yield is w. Derivations and trees describe the very same set of strings; the tree just keeps the structure and discards the ordering noise.
Grammar: S -> A B, A -> a A | a, B -> b
Parse tree for 'aab':
S
/ \
A B
/ \ |
a A b
|
a
Reading the leaves left to right: a a b -> yield = "aab"Trees versus derivations, and the seed of ambiguity
Now the deep relationship, and it is worth memorising. ONE parse tree corresponds to MANY derivations (all the ways of ordering the independent rewrites) but to EXACTLY ONE leftmost derivation and exactly one rightmost derivation. The correspondence is one-to-one: every parse tree gives a unique leftmost derivation, and every leftmost derivation gives back a unique parse tree. That is precisely why the tree, not the raw derivation sequence, is the right notion of structure — two derivations that differ only in bookkeeping order collapse to the same tree.
- Two derivations describe the SAME structure if they yield the same parse tree — even when their step sequences differ (as the leftmost and rightmost ones usually do). Different step order alone means nothing.
- So the honest test of 'two structures' is two distinct parse trees — equivalently, two distinct LEFTMOST derivations (or two distinct rightmost derivations), since each tree has exactly one of each.
- A grammar is AMBIGUOUS exactly when some single string in its language has two genuinely different parse trees. The flat grammar E → E + E | E * E | a is the classic offender: a + a * a parses both as (a + a) * a and as a + (a * a) — same yield, two trees, two different groupings.
Where this is heading
You now own the machinery that turns a static pile of rules into a living generator: the derivation step u => v, the chained derivation S =>* w, the sentential forms along the way, the two disciplined orderings (leftmost and rightmost), and above all the parse tree whose yield is the generated string. Two equivalent definitions of the language now sit in front of you: 'w such that S =>* w in terminals' and 'w that is the yield of some tree rooted at S'. Both describe exactly the context-free language of the grammar.
The next guide turns this from analysis into craft: how to DESIGN a context-free grammar so it generates exactly the language you want — the recursive templates for a^n b^n, balanced brackets, and arithmetic expressions, built by thinking recursively (a base case, plus a rule that wraps a smaller instance in something bigger). And once you can generate the right set of strings, guide 4 raises the bar to the harder, more honest goal: giving each string the right tree, by removing ambiguity. Hold tight to one idea as you go — the parse tree, never the derivation order, is what carries meaning.