From hand-written parser to grammar compiler
In this rung you wrote a recursive-descent parser by hand, then traced a shift-reduce machine bottom-up, then met the worst-case-safe CYK and Earley algorithms. Each was real work per grammar. The obvious next wish: write down the grammar once, and let a program generate the parser for you. That program is a parser generator — think of it as a compiler whose source language is grammar rules and whose output is parser code. The classic pair is yacc (Yet Another Compiler-Compiler, 1975) and its free reimplementation bison; in other ecosystems you will meet ANTLR, menhir, or tree-sitter, but the idea is the same.
Crucially, yacc and bison do not run CYK or Earley at parse time. They build the LR parsing table you studied in guide 3 — specifically a variant called LALR(1) — and emit a fast, table-driven shift-reduce parser that runs in linear O(n) time on the input. CYK and Earley are general (they handle any context-free grammar, even ambiguous ones) but cost O(n^3); the bison-style tool trades that generality for speed, and in return it insists your grammar fall inside the deterministic LR family. When your grammar does not, it tells you — loudly — and that conversation is most of the real work.
What a grammar file looks like
A bison input file pairs each grammar rule with a chunk of code — the semantic action — that runs when the parser reduces by that rule. Recall from guide 1 that the parser does not consume raw characters; a scanner / lexer has already chopped the text into tokens like NUM, PLUS, LPAREN. The grammar is written over those token names, and a reduce step is exactly the moment you have recognized a complete phrase and can do something with it — typically, build one node of the result tree.
A concrete example: the rule 'expr : expr PLUS term' might carry the action '$ = makeNode(+, 1, $3)'. Here $1 and $3 stand for the values of the first and third symbols on the right-hand side (the two sub-expressions), and $$ is the value this rule hands back for its left-hand side. So the action wires the children's values into a new plus-node and passes it up. Splitting the grammar into layered expr / term / factor rules — where 'factor' covers a NUM or a parenthesized expr — also encodes 'times binds tighter than plus' directly in the grammar's shape, before we even discuss precedence.
The values flowing through $1, $3, $$ are pointers to tree nodes, and the thing they assemble is an abstract syntax tree (AST). This is the deep payoff of the whole front end. A parse tree (also called a concrete syntax tree) records every grammar rule fired, including bookkeeping nonterminals like 'term' and 'factor' and noise like the parentheses; the AST throws all of that away and keeps only the meaning — for '1 + 2 * 3' it is a plus-node whose right child is a times-node, faithfully recording that the multiply happens first. Everything downstream (type checking, optimization, code generation) walks the AST, not the text.
Conflicts: when the parser cannot decide
Hand the generator an ambiguous or merely awkward grammar and it cannot build a deterministic table — there is a table entry where it does not know what to do. That is a conflict, and it comes in two flavours. A shift-reduce conflict means: with the same lookahead token, the parser could either shift (read more input, betting the phrase continues) or reduce (declare the phrase complete and apply a rule). A reduce-reduce conflict means two different rules both claim the same finished phrase. Conflicts are not random failures; they are the generator telling you the grammar is genuinely ambiguous or outside LR's one-token-lookahead reach.
The textbook shift-reduce conflict is the dangling else: in 'if C1 then if C2 then S1 else S2', does the 'else' attach to the inner 'if' or the outer one? Both parse trees are legal under the naive grammar, so on seeing 'else' the parser cannot tell whether to reduce the inner if-statement (closing it without an else) or shift the 'else' (giving it to the inner if). Real languages settle this by a rule — 'else binds to the nearest unmatched if' — and the parser generator lets you encode that choice rather than rewrite the grammar into something unreadable.
Precedence: keeping ambiguity but resolving it
There are two ways to handle an arithmetic grammar. One is to bake in the structure with the layered expr / term / factor rules above — clear, but the grammar swells as you add operators. The other is to write the gloriously short and ambiguous rule 'expr : expr OP expr' and then declare precedence and associativity as separate directives. The generator keeps the tiny grammar but uses your declarations to resolve every shift-reduce conflict the ambiguity creates. This is the everyday use of conflict resolution, and it is why real grammar files stay small.
%left PLUS MINUS /* lowest precedence, left-associative */
%left TIMES DIVIDE /* higher precedence, left-associative */
%right POWER /* highest, right-associative: 2^3^2 = 2^(3^2) */
%%
expr : expr PLUS expr
| expr TIMES expr
| expr POWER expr
| NUM
;
/* The grammar is ambiguous, but %left/%right lines below resolve
every shift-reduce conflict:
- later %left/%right line = higher precedence
- %left prefers REDUCE (a-b-c parses as (a-b)-c)
- %right prefers SHIFT (a^b^c parses as a^(b^c)) */Notice the precise mechanism: a conflict over 'expr . OP expr' (the dot is where the parser sits) is settled by comparing the precedence of the operator on the stack against the precedence of the incoming lookahead operator. Higher-on-stack means reduce now; higher-incoming means shift. Equal precedence falls back to associativity — %left reduces, %right shifts. So 'precedence and associativity' is not vague hand-waving; it is a deterministic rule for filling exactly the conflicted entries of the LR table. The grammar stays ambiguous on paper, but the parser is fully deterministic.
Beyond programming languages
Grammars and parsers are not just for source code. Natural-language parsing uses context-free (and richer) grammars to assign syntactic structure to English or Chinese sentences, and here the comfortable assumptions break in instructive ways. Human languages are pervasively ambiguous — 'I saw the man with the telescope' has two perfectly good parse trees, and no precedence directive can pick the right one, because the right one depends on meaning, not syntax. So natural-language parsers typically keep the general O(n^3) Earley or CYK machinery and rank the many possible trees with probabilities rather than forcing a single deterministic answer.
The same grammar-and-parse idea shows up far beyond language too: parsing structured data formats (JSON, the headers of a network packet, a date string), validating configuration files, parsing the notation in a chess game or a chemical formula, and reading the nested structure of markup. Anywhere you have a stream of tokens with nested, recursive structure, the machinery of this rung applies. The cleaner the structure, the more likely a deterministic LR or LL parser suffices; the messier and more human, the more you reach for the general algorithms.
Step back and see the whole rung as one arc. A regular-language scanner turned characters into tokens; a top-down LL parser or a bottom-up LR parser turned tokens into a tree, with FIRST and FOLLOW sets and the handle as the local decision tools; CYK and Earley stood ready for grammars too gnarly for either; and a parser generator packaged the winning strategy so you never write the table by hand. The grammar you write is the specification; the parser you get is the proof that a string belongs — the parsing question answered, automatically, in linear time when the grammar is kind enough to allow it.