From recognizing to building
By now you have met two machines that read strings. A finite automaton is a turnstile: it remembers only its current state and answers a single yes/no question — is this string in the language? A pushdown automaton adds a stack of plates you can only touch on top, which is exactly the memory you need to match nested structure like balanced brackets or a^n b^n. The previous rungs proved that a context-free grammar and a pushdown automaton describe the same class of languages. But a real compiler does not just want a yes/no. It wants the structure: which token is the operator, which sub-expression is its left argument, where one statement ends and the next begins.
That is the leap this rung makes: from recognizing a string to parsing it. Parsing is the act of taking a flat sequence of symbols and recovering the parse tree a grammar would have used to generate it — running derivation backwards. A recognizer says yes; a parser says yes and here is exactly why, drawn as a tree. Everything downstream in a compiler — type checking, optimization, code generation — operates on that tree, never on the raw characters. So parsing is the bridge between a stream of bytes on disk and a structured object a program can reason about.
First the scanner: regular languages do the lexing
Before a single tree is built, the compiler front end runs a cheaper stage. Feeding individual characters straight into the parser would be wasteful: the parser would burn effort deciding that 'w', 'h', 'i', 'l', 'e' spell the keyword 'while', that '1', '2', '3' form one number, and that the three spaces between them are just noise. So the front end splits into two passes. The first is the scanner (also called the lexer or tokenizer), and here is the elegant part — it lives entirely in the regular world you already mastered.
Each kind of token — an identifier, a number, an operator, a keyword — is described by a regular expression, for instance a number as `[0-9]+` or an identifier as a letter followed by letters and digits. By Kleene's theorem every such regex compiles to a finite automaton, so the scanner is just a fast DFA running over the input, chopping the character stream into a clean sequence of tagged tokens. This is exactly why scanning is cheap: a turnstile-style machine with no stack, linear time, constant memory. The reason a separate scanner is even possible is the boundary you learned earlier — the lexical structure of a language (its words) is regular, even though its grammatical structure (its sentences) is not.
Source text: while (n123 >= 0) Scanner (a DFA) emits a token stream: KEYWORD(while) LPAREN IDENT(n123) GE(>=) NUM(0) RPAREN - whitespace is recognized and discarded - 'n123' is ONE identifier token, not 4 characters - '>=' is ONE operator token, not '>' then '=' The parser never sees raw characters -- only this tidy stream.
Then the parser: a tree the grammar would have grown
Now the parser takes the token stream and the language's context-free grammar and reconstructs a parse tree — a tree whose root is the start symbol, whose internal nodes are the rules that fired, and whose leaves, read left to right, spell out the tokens. Building it is running derivation in reverse: a derivation grows a string from the start symbol by applying production rules; the parser is handed the finished string and must rediscover which rules were applied and in what order. Because the grammar is context-free and not merely regular, this needs the stack a pushdown automaton provides — the recursive, nested matching that a DFA alone cannot do.
There are two great philosophies for doing this, and the next two guides in this rung take one each. Top-down parsing starts at the root — the start symbol — and guesses its way down toward the tokens, asking 'I'm trying to build an expression; given that the next token is a number, which rule should I expand?'. It mirrors a leftmost derivation. Bottom-up parsing starts at the leaves — the actual tokens — and works upward, grouping finished pieces into bigger pieces until the whole thing collapses to the start symbol, mirroring a rightmost derivation run in reverse. Top-down is the more intuitive 'predict and expand'; bottom-up is the more powerful 'wait, accumulate, and reduce'.
Not every grammar is friendly to every method, and not every string has a unique tree. An ambiguous grammar can grow two different parse trees for the same token stream — the classic example is `a - b - c`, which a careless grammar lets you read as `(a - b) - c` or `a - (b - c)`, two different meanings. Real parsers break such ties with precedence and associativity rules, a topic guide 5 returns to. The honest caveat: ambiguity is a property of the grammar, and some context-free languages are inherently ambiguous — no grammar for them avoids it. Worse, asking in general whether a given grammar is ambiguous is itself undecidable, so there is no algorithm that screens every grammar for you.
When the grammar fights you: general parsers
The two mainstream methods come with conditions. Top-down works smoothly only for grammars in restricted classes like LL(1), where the next single token always tells you which rule to expand; bottom-up's LR family is more forgiving but still cannot handle every context-free grammar. So what do you do when a grammar refuses to fit either mould — for instance a natural-language grammar, or one written for clarity rather than for a parser? You reach for a general parser that handles any context-free grammar, ambiguity included, at the cost of more time.
Guide 4 covers two. The CYK algorithm first rewrites the grammar into Chomsky normal form (every rule either A -> B C or A -> a), then fills a triangular table bottom-up: a cell records which nonterminals can derive each contiguous slice of the input, building from single tokens up to the whole string. It is a tidy dynamic program running in O(n^3) time for input length n. The Earley parser takes a different route, juggling sets of partially-finished rules as it sweeps left to right; it also runs in O(n^3) worst case but speeds up to O(n^2) on unambiguous grammars and even linear time on the nice ones. The trade is plain: generality for speed. A specialized LL(1) or LR parser runs in linear time; a general parser pays a polynomial premium for accepting grammars the fast methods reject.
The output: an abstract syntax tree, not the parse tree
There is a last, easy-to-miss step. The literal parse tree is faithful but cluttered: it has a node for every grammar rule that fired, including bookkeeping like the parentheses you wrote, the semicolons that ended statements, and the long chains of single-child rules a grammar needs to encode precedence. None of that matters once the structure is known. So the front end distills the parse tree into an abstract syntax tree (AST), which keeps only the meaningful skeleton.
Take `a + b * c`. The full parse tree threads it through a chain like Expr -> Term -> Factor to enforce that `*` binds tighter than `+`; the AST throws all that scaffolding away and keeps just a `+` node whose right child is a `*` node — the meaning, nothing else. Parentheses vanish too, because once the tree exists they have done their only job of grouping. The AST is what the rest of the compiler walks: a type checker visits each node asking 'do these types fit?', a code generator emits an instruction per node. Reading raw text is over; from here on the program is a tree.
Finally, none of this is a programming-language quirk. The same pipeline — tokenize with a regular scanner, parse with a context-free grammar, distill to a tree — underlies natural-language parsing, where linguists assign grammatical structure to sentences, as well as protocol parsers, query languages, configuration files, and chemical-formula readers. Wherever a stream of symbols carries nested meaning, this front end is the tool. Hand-writing a parser by these principles is the subject of guides 2 and 3; the final guide shows how a parser generator like yacc or bison builds one for you from a grammar, and how it reports the conflicts that warn you the grammar is ambiguous or out of class.