Compiler Construction

A compiler is a sequence of contracts

A compiler translates a program while preserving its defined behaviour. Separate its tasks: scanning groups characters into tokens, parsing builds grammatical structure, semantic analysis resolves names and types, and the back end selects executable operations. Each phase should reject invalid inputs before later phases assume their invariants. Keep source locations attached to tokens and syntax nodes so an error can identify the original expression rather than an internal temporary variable.

References: Winter 2026 outline alignment · LLVM: My First Language Frontend tutorial

Scanning and token boundaries

A scanner recognizes identifiers, keywords, literals and punctuation. Its state must distinguish an operator inside a string from an actual operator. Longest-match rules matter: the input <= should normally become one token, whereas < = becomes two when separated. A keyword table can classify an already scanned identifier. Test the scanner independently with empty input, escaped quotes, comments at end of file and adjacent operators before debugging the parser.

References: Winter 2026 outline alignment · LLVM: My First Language Frontend tutorial

Grammars, precedence and syntax trees

A grammar describes legal sequences of tokens. A recursive-descent parser can represent each nonterminal by a procedure, provided the grammar is suitable. Expression parsing must enforce precedence and associativity: 8 - 3 - 1 means (8 - 3) - 1 for a left-associative subtraction operator. An abstract syntax tree discards grammatical scaffolding while keeping meaningful operations. Parentheses guide construction but need not survive as their own executable nodes.

References: Winter 2026 outline alignment · LLVM: My First Language Frontend tutorial

Name resolution and semantic checking

Maintain an environment mapping identifiers to declarations. Entering a lexical block creates a child environment; lookup walks outward to the nearest matching declaration. Distinguish shadowing, where a nested declaration hides an outer one, from a duplicate declaration within one scope. Type checking then reasons over resolved expressions. In a simple language, an addition node may require two numeric operands and produce a numeric result; a well-formed parse can still violate this rule.

References: Winter 2026 outline alignment · LLVM: My First Language Frontend tutorial

Intermediate representation and control flow

Lower complex expressions into a small instruction vocabulary. For x = (a + 2) * b, a three-address representation first computes t1 = a + 2, then t2 = t1 * b, then assigns x = t2. Basic blocks contain straight-line instructions with one entry. A control-flow graph connects their possible successors. Explicit labels and branches make if statements and loops easier to inspect than emitting machine code directly from every syntax case.

References: Winter 2026 outline alignment · LLVM: My First Language Frontend tutorial

Optimizations require semantic evidence

Constant folding replaces a calculation on known constants, while dead-code elimination removes results that cannot affect observable behaviour. A transformation must respect the source language: replacing x * 0 by zero can discard an exception or side effect in an expression that computes x. Integer overflow and floating-point rounding also constrain algebraic rewrites. State the assumptions behind each optimization and compare execution before and after it on small adversarial programs.

References: Winter 2026 outline alignment · LLVM: My First Language Frontend tutorial

Worked trace and verification strategy

Consider let x = 4; print(x + 3 * 2). Scanning produces names, literals and delimiters; parsing makes multiplication the right child of addition; lookup binds x to the declaration; type checking verifies numeric operands. Lowering yields a multiply, an add and an output operation. Folding can reduce 3 * 2 to 6, and propagation can then produce 10 if x cannot change. Differential tests can compare interpreted syntax trees with compiled execution.

References: Winter 2026 outline alignment · LLVM: My First Language Frontend tutorial

Practice & worked answers

Original exercises for this guide.

Public notes & references

Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.

• Winter 2026 outline alignment ↗Course scope
• LLVM: My First Language Frontend tutorial ↗Supplementary primary reference
• Pat Morin: COMP 3002 Fall 2011 public course page ↗Historical public course materials · Fall 2011