CD · Short notes
20 short notes in syllabus order, about 179 minutes to read end to end.
A compiler reads a program in a source language and translates it into an equivalent program in a target language, reporting the errors it finds in the source. An interpreter instead executes the source operations directly on the inputs, without producing a separate target program.
The lexical analyser (scanner, lexer) is the first phase of a compiler. It reads the source text character by character, groups the characters into meaningful units called lexemes, and passes one token per lexeme to the parser.
A context-free grammar written to describe a language is often unsuitable for a parser. An ambiguous grammar gives a parser two trees to choose from. A left-recursive grammar sends a top-down parser into an infinite loop.
A predictive parser must decide which production to apply by looking only at the next input token. A bottom-up SLR parser must decide whether to reduce by looking at the same token.
A top-down parser builds the parse tree from the root down, in preorder, and in doing so produces a leftmost derivation of the input. At each step it holds a leftmost nonterminal and must choose one of its productions.
A bottom-up parser builds the parse tree from the leaves up to the root. It starts from the input string and repeatedly replaces a substring that matches the body of a production by the production's head, a step called a reduction, until only the start symbol remains.
An LR parser is a shift-reduce parser that decides each action from a table indexed by a state on top of its stack and the next input token. The states are the states of a DFA that recognises viable prefixes, so the parser always knows which productions it might be in the middle of.
SLR places a reduction A → α on every token in FOLLOW(A). FOLLOW is a global set: it collects every token that can follow A anywhere in the grammar, even when, in the particular state the parser is in, only a few of those tokens can actually come next.
Parsing tells the compiler how a program is structured; it does not compute anything about the program. Syntax-directed translation attaches information to grammar symbols, called attributes, and attaches rules to productions that compute those attributes.
A syntax-directed definition says what each attribute equals but leaves the order of evaluation to the dependency graph.
The code a compiler generates runs inside a runtime environment: an agreed layout of memory and an agreed protocol for calls and returns.
Two questions decide what a procedure call does with names. Parameter passing answers how an actual parameter in the call is connected to the formal parameter in the procedure: by copying its value, by sharing its location, by copying in and out, or by re-evaluating the argument text.
Between the parser and the code generator, a compiler represents the program in one or more intermediate representations (IRs). A high-level IR such as a syntax tree keeps the source structure and suits type checking.
Intermediate-code generation turns the syntax tree into three-address code with syntax-directed rules.
Optimisation and code generation work on three-address code organised into basic blocks: maximal straight-line sequences that control enters only at the top and leaves only at the bottom.
Local optimisation improves one basic block at a time, using only what is known inside the block.
Global optimisations need facts that hold at a program point on every execution, or on some execution: "this definition of x may reach here", "y may be used later", "a + b has already been computed on every path to here", "z is always 3 here".
If a variable holds the same known constant on every path to a use, the compiler can replace the use by the constant. That enables constant folding (computing 4 * 2 at compile time), which can make more variables constant, and can make branch conditions known so that whole paths become dead.
A variable is live at a program point if its current value may still be read later. A register holding a dead variable can be reused; an assignment to a variable that is dead immediately afterwards is useless and can be deleted.
An expression is a common subexpression if it was computed earlier and its operands have not changed since. Reusing the earlier value is common subexpression elimination; across blocks it relies on the available expressions analysis.
