- Compilers: Principles, Techniques and Tools — Ch. 2 in full (it is a miniature of this entire project); Ch. 4 §4.1–4.6, §4.8–4.9; Ch. 5 §5.1–5.4; Ch. 6 §6.1–6.2. Browse §8.1–8.3.
- Chapter 2 repays a second reading once you have started coding — it builds the same front end you are building, in about forty pages.
- Levine, flex & bison, ch. 3, for the tool's own view of §4.9.
0Where this topic sits
Topic 1 built one phase. Topic 2 builds all six, for a language small enough that you can hold the whole compiler in your head. Four weeks, and the language has three statement forms and one operator — because the difficulty here is not the language. It is that every structural decision you make this month is one you will live with until December.
1The parser's job
The parser takes the token stream and verifies that it can be generated by the grammar of the source language, producing a tree that exhibits the structure (Dragon §4.1.1). Where the scanner asked are these words in the language, the parser asks do these words form a sentence.
Three families of parser exist (Dragon §4.1.1). Universal methods such as Cocke–Younger–Kasami parse any grammar but are too slow to be practical. Top-down methods build the tree from the root down. Bottom-up methods build it from the leaves up. Both of the practical families work only on sub-classes of grammars — LL for top-down, LR for bottom-up — and those sub-classes are rich enough for every programming language in common use.
Error handling is part of the job, not an add-on
Dragon §4.1.3 sets out what a parser owes the programmer: report errors clearly and accurately; recover quickly enough to find later errors; and add negligible overhead to correct programs. Four recovery strategies are standard (§4.1.4):
| Strategy | How it works | Trade-off |
|---|---|---|
| Panic mode | discard input until a synchronising token — often ; or } — then resume | simple, always terminates, can skip a lot of real program |
| Phrase level | perform a local correction: insert a missing semicolon, delete a stray token | can loop forever if the correction does not consume input |
| Error productions | add rules to the grammar that match common mistakes, with an action that reports them | gives the best messages, because the rule knows what was being parsed |
| Global correction | find the smallest set of edits turning the input into a legal program | theoretically appealing, too expensive to use |
Bison gives you the first and the third. The error token is a pseudo-terminal that matches wherever the parser is lost, so a rule like assign → ID '=' expr error catches a missing semicolon and knows, because of where it sits in the grammar, that the programmer was writing an assignment. That context is why an error production can say missing ';' after assignment to 'total' where a generic handler can only say syntax error.
2Context-free grammars
A context-free grammar is four things (Dragon §4.2.1): a set of terminals — your token names; a set of nonterminals; a set of productions, each with a nonterminal on the left and a string of grammar symbols on the right; and a designated start symbol.
stmt_list -> stmt | stmt_list stmt
stmt -> decl | assign | print_stmt
decl -> 'int' ID ';'
assign -> ID '=' expr ';'
expr -> NUM | ID | expr '+' exprDerivations
A production is a rewriting rule. Starting from the start symbol and repeatedly replacing a nonterminal by the right side of one of its productions gives a derivation (Dragon §4.2.2). If at each step you always expand the leftmost nonterminal, it is a leftmost derivation; always the rightmost, a rightmost derivation.
expr ⇒ expr '+' expr leftmost derivation of a + b
⇒ ID '+' expr replace the leftmost expr
⇒ a '+' expr
⇒ a '+' ID
⇒ a '+' bThese two are not idle terminology. Top-down parsers trace out a leftmost derivation; bottom-up parsers trace out a rightmost derivation in reverse. When you watch a shift-reduce parser run in §5, that is what you are watching.
Parse trees
A parse tree is a derivation with the order of the rewriting steps abstracted away (Dragon §4.2.3). The root is the start symbol, interior nodes are nonterminals, leaves read left to right give the input string. Several derivations may correspond to one parse tree — which is a good thing, since the order of the steps is not supposed to matter.
3Ambiguity, and how grammars are made unambiguous
A grammar is ambiguous if some string has more than one parse tree (Dragon §4.2.4). This is not a subtlety to be tidied away later — it means the grammar has failed to say what the program means.
E → E + E | E * E | id is ambiguous: both trees are legal derivations of a + b * c, and they compute different values. Dragon §4.3.2. A grammar for a programming language must be unambiguous, or made unambiguous by extra rules — which is precisely what precedence declarations are.Two remedies exist, and every compiler uses one of them.
Remedy 1 — rewrite the grammar into layers
Introduce one nonterminal per precedence level, and let the higher-binding level be reachable only through the lower one (Dragon §4.3.2). Associativity then follows from the direction of recursion: left recursion gives left associativity, right recursion gives right associativity.
expr → expr + term | term, term → term * factor | factor, factor → id | ( expr ). Only one tree is now possible: * is forced deeper because term can only be reached through expr. Precedence is encoded in the shape of the grammar, and left recursion gives left associativity. Dragon §4.3.2, Fig. 4.10.Remedy 2 — keep the ambiguous grammar and declare precedence
Dragon §4.8 shows that an ambiguous grammar plus disambiguating rules is often preferable: the grammar stays short and readable, and the parser is usually smaller. This is what bison's %left and %right declarations do — they resolve the conflicts an ambiguous grammar produces, rather than removing the ambiguity from the grammar itself.
| Layered grammar | Precedence declarations | |
|---|---|---|
| Where precedence lives | in the shape of the rules | in a declaration block |
| Grammar size | 3 nonterminals for 2 levels; grows with each level | one expr rule regardless of how many levels |
| Portability | any parser generator, and hand-written parsers | bison/yacc feature |
| Changing precedence | restructure the rules | move one line |
| Readability of the tree | extra single-child nodes to skip past | clean |
This is the first real language-design decision in the course, and Lab Question 3 asks about it. Ours uses precedence declarations. The reasoning is that the grammar you read should look like the language you designed, and a reader who wants to know that * binds tighter than + should not have to infer it from the depth of a nonterminal chain.
Left recursion is a problem only for top-down parsers
A grammar with A → A α sends a recursive-descent parser into infinite recursion: to parse an A it first tries to parse an A. Dragon §4.3.3 gives the standard elimination transformation. Bottom-up parsers have no such problem — indeed they prefer left recursion, because it keeps the stack shallow. This is one of the sharpest practical differences between the two families, and it is why our left-recursive stmt_list rule is natural in bison and would have to be rewritten for a hand-written recursive-descent parser.
4Top-down parsing
A recursive-descent parser is one function per nonterminal, each choosing a production and calling the functions for the symbols on its right side (Dragon §4.4.1). If the choice can always be made by looking at one token of lookahead, no backtracking is needed and the parser is predictive.
Whether that is possible is decided by two functions (Dragon §4.4.2). FIRST(α) is the set of terminals that can begin a string derived from α. FOLLOW(A) is the set of terminals that can appear immediately after A in some derivation. A grammar is LL(1) when, for every pair of productions of the same nonterminal, those sets do not overlap — meaning the lookahead token always identifies the right production.
LL(1) reads: scan Left to right, produce a Leftmost derivation, with 1 token of lookahead. Its virtues are that the parser is readable, hand-writable, and gives excellent error messages, because at the point of failure the parser knows exactly which nonterminal it was in the middle of. Its vice is that the grammar must be massaged first: left recursion eliminated, common prefixes left-factored, and even then many natural grammars are not LL(1).
5Bottom-up parsing, and what bison actually is
A bottom-up parser reduces the input to the start symbol, building the tree from the leaves up (Dragon §4.5). The general form is shift-reduce parsing, with a stack and exactly four possible actions: shift the next token onto the stack, reduce the top of the stack to a nonterminal, accept, or report an error.
id + id * id (Dragon §4.5.3, Fig. 4.28). The parser only ever does two things: shift the next input symbol onto the stack, or reduce the symbols on top of the stack to the left side of a production. The hard question — and the whole content of LR theory — is knowing when the top of the stack is a handle that should be reduced. Notice the parse tree is being built bottom-up, leaves first.Everything hinges on the reduce decision. The substring that should be reduced is called a handle (Dragon §4.5.2), and it is always on top of the stack — which is the reason a stack works at all. Recognizing handles is what LR parsing contributes.
LR parsing
LR(k) reads: scan Left to right, produce a Rightmost derivation in reverse, with k tokens of lookahead. The insight (Dragon §4.6) is that the set of prefixes of right-sentential forms that can appear on the stack — the viable prefixes — is itself a regular language, and so can be recognized by a finite automaton. The parser's states are the states of that automaton, and each state is a set of items: productions with a dot marking how much has been seen.
Three refinements of increasing power are standard (Dragon §4.6–4.7):
| Method | How it decides to reduce | Cost |
|---|---|---|
| SLR | reduce by A → α when the lookahead is in FOLLOW(A) | smallest tables; fails on some real grammars |
| Canonical LR | carries an exact lookahead set in every item | most powerful; state count often in the thousands |
| LALR | merges canonical-LR states with identical cores | SLR-sized tables, nearly canonical-LR power — what yacc and bison build |
So when bison reports a shift/reduce conflict, it is telling you that some state contains both a completed item and an item that could advance, and one token of lookahead does not separate them. Its default is to shift. That default happens to be right for the dangling else — which you meet in Topic 5 — and it is why that particular ambiguity is usually invisible until you read the warnings.
Why does a bottom-up parser handle left recursion comfortably while a top-down parser cannot?
6Syntax-directed translation: how a parse becomes a program
A parser that only answers yes or no is of no use. What turns parsing into translation is attaching attributes to grammar symbols and rules to productions for computing them. A grammar with attributes and rules is a syntax-directed definition (Dragon §5.1).
val, computed from the attributes of its children — so val is a synthesized attribute and values flow upward. A syntax-directed definition using only synthesized attributes is S-attributed and can be evaluated during a bottom-up parse, in exactly the order the reductions happen. That is why bison actions can build a tree with no extra traversal. Dragon §5.1.1, §5.2.3.Synthesized and inherited attributes
An attribute is synthesized if its value at a node is computed from attributes of that node's children. It is inherited if computed from attributes of the node's parent and siblings (Dragon §5.1.1–5.1.2). Synthesized attributes flow up the tree; inherited attributes flow down and across.
| Class | Uses | Can be evaluated | Example |
|---|---|---|---|
| S-attributed | synthesized attributes only | during a bottom-up parse, as reductions happen | the value of an expression; a pointer to a newly built AST node |
| L-attributed | synthesized, plus inherited from the parent or a sibling to the left | in one left-to-right pass | propagating a declared type across a list of declarators |
Every bison action of the form $$ = createBinOp('+', $1, $3); is the rule of an S-attributed definition: it computes this node's attribute — a pointer to a tree node — purely from the attributes of its children. That is the reason the actions can run during the parse with no separate traversal, and the reason the children always exist by the time the parent's action runs. Reductions happen innermost first.
From definition to scheme
A syntax-directed translation scheme embeds program fragments within the right sides of productions, at specified positions (Dragon §5.4). An action at the end of a production is executed on reduction, which is exactly what bison supports natively. Actions in the middle are trickier — bison implements them by inventing an empty nonterminal, which can introduce conflicts, and that is worth knowing before you are tempted to write one.
7The abstract syntax tree
The parse tree is a record of how the parser worked. The syntax tree is a record of what the program means, and it is the representation every later phase actually consumes (Dragon §5.3.1, §6.1.1).
Note in particular that parentheses leave no trace. (a + b) * c and a + b * c produce different tree shapes, and the shape is the grouping — a node recording 'these were parenthesised' would tell no later phase anything it could use.
Designing the node types
Dragon §6.1.1 models a syntax tree as one node kind per construct, with children for the operands. Two practical points follow. First, every node you invent is a case in five switch statements — the printer, the semantic checker, the TAC generator, and so on — so invent as few as you can. Second, the tree is the interface between the front and the rest of the compiler; if it is the wrong shape, you find out in phase 4 or 6, which is why an end-to-end spike in week 2 is worth more than three careful weeks on phases 1–3.
8Semantic analysis and the symbol table
Some rules cannot be expressed by any context-free grammar. The classic example is a variable must be declared before it is used, which requires remembering an unbounded set of names — and Dragon §4.2.7 shows the closely related aⁿbⁿcⁿ is not context-free at all.
So the compiler carries a symbol table: a mapping from names to the information the later phases need (Dragon §2.7). At this milestone that is a type and a storage location. In Topic 3 it becomes a stack of tables, one per scope.
The checks a semantic analyzer performs on this language are short — undeclared use, duplicate declaration — but the shape of the phase is what matters: a traversal of the AST that consults and updates a table, and reports errors with source positions. Every check added in Topics 3–5 is another case in that traversal.
9Intermediate code
Dragon §6.1 presents a spectrum of intermediate representations, from syntax trees (close to the source) down to three-address code (close to the machine). Compilers commonly use more than one.
Three-address code
TAC is a sequence of instructions of the form x = y op z, with at most one operator each (Dragon §6.2). Two features do all the work. Complex expressions are unnested by introducing temporary names. Control flow is unnested by introducing labels and jumps — which is what makes Topic 4 possible.
d = a + a * (b - c) (Dragon §6.2.1–6.2.2). Each instruction has at most one operator and at most three operands. The quadruple form gives every instruction an explicit result field, which is what makes instructions independently movable — and therefore what makes optimization possible. Triples save the result field but hard-wire position, so moving an instruction renumbers everything after it.The representation choice matters (Dragon §6.2.2). Quadruples name the result explicitly, so an instruction can be moved without disturbing anything else. Triples refer to results by instruction position, which saves space but means moving an instruction renumbers every reference to it. Optimizers move instructions constantly, so quadruples win — and that is why our TACInstr has a result field.
A third form worth knowing: static single assignment
SSA (Dragon §6.2.4) requires that every variable be assigned exactly once, introducing new versions x₁, x₂, … and a φ-function where control paths merge. It makes many optimizations dramatically simpler because the definition reaching any use is unique by construction. Every serious modern compiler — GCC, LLVM — uses it. We do not, because the φ-functions need the control-flow analysis of Topic 4 to place, but it is the single best thing to read about if this course interests you.
10Code generation
The last phase maps the IR onto the target machine. Dragon §8.1 names three problems, and they will be recognizable from your own code by week 5:
- Instruction selection. Which target instructions implement this IR instruction? Usually many choices, with different costs.
- Register allocation and assignment. Which values live in registers, and in which ones? Optimal allocation is NP-complete even for restricted cases, so every compiler uses a heuristic.
- Evaluation order. The order instructions are emitted affects how many registers are needed and how well the pipeline is used.
Ours does the simplest defensible thing on all three: one fixed instruction sequence per TAC opcode; registers as a write-back cache over memory homes, with least-recently-used eviction; and the order the TAC already gives. Each of those is a decision, and Topic 6 asks you to name and defend it.
To watch both allocators run on your own expressions, open Temporaries & Registers. It steps through how TAC temporaries are recycled and how the code generator moves them between registers and memory.
Addresses in the target code
Dragon §8.3 makes the connection between the symbol table and the generated code: static data goes in a data area addressed by label, and local data goes in an activation record addressed by an offset from a stack pointer. In this milestone there are no functions, so the whole program shares one frame — a simplification that Topic 3 removes, and the removal is the hardest single step in the course.
11A note on optimization
Phase 5 is nearly idle at this milestone, and you should understand why. Straight-line code with no loops has very little redundancy to remove: constant folding will fire, and constant propagation, and that is about all (Dragon §8.5, §9.1). The payoff arrives in Topic 4 with loops, where a single instruction removed from a loop body is one instruction removed per iteration. Build the framework now, run it to a fixed point now, and it will be ready when it matters.
12The approach for this milestone
Build an end-to-end spike first
Get print(1); from source to running MIPS in week 2, with every phase stubbed to handle only that. Teams that do this finish. Teams that perfect phase 2, then phase 3, then phase 4 discover in week 5 that their AST is the wrong shape for code generation, which is the single most common way this project goes wrong.
Treat the tree printer as an instrument, not a nicety
It is the only window you have into phase 2, and every bug in phases 3–6 is diagnosed by staring at it. Write it early and make its output readable.
Divide the work by phase, not by file
Each phase has a clean interface, so each person owns a boundary and can explain it. Dividing by file gives everyone a piece of everything and nobody a coherent account of anything — which shows up immediately in the individual videos.
Decide your error-message standard now
Four questions per message: does it give the line, name the offending thing, say what was expected, and suggest a fix? Error productions are what let you answer all four, and adding them is much easier while the grammar is small.
13Self-check
A grammar is ambiguous. Which of these is a consequence?
In expr : expr '+' expr { $$ = createBinOp('+', $1, $3); }, why is it safe to assume $1 and $3 already point at built subtrees?
Why do compilers represent three-address code as quadruples rather than triples?
Which of these rules can a context-free grammar NOT express?
Bison reports one shift/reduce conflict and compiles anyway. What has happened?
14References
- Aho, Lam, Sethi & Ullman, 2nd ed. — Ch. 2 (a complete miniature front end); §4.1 (the role of the parser and error handling), §4.2 (context-free grammars, derivations, ambiguity), §4.3 (writing a grammar), §4.4 (top-down, FIRST/FOLLOW, LL(1)), §4.5 (shift-reduce and handles), §4.6 (LR(0) items, SLR), §4.7 (canonical LR and LALR), §4.8 (using ambiguous grammars — the precedence argument), §4.9 (parser generators); §5.1–5.2 (attributes and evaluation orders), §5.3–5.4 (applications and translation schemes); §6.1 (variants of syntax trees), §6.2 (three-address code, quadruples, SSA); §8.1–8.3 (issues in code generation, the target language, addresses).
- Knuth, On the translation of languages from left to right, Information and Control 8(6), 1965 — the paper that introduced LR parsing.
- Levine, flex & bison (O'Reilly, 2009), ch. 3 and appendix on conflicts.