Compiler Design experimental

Compiler Design How source becomes machine code: lexing, parsing, ASTs, type checking, intermediate representations and code generation. Lexing and parsing. Lexing and parsing. Turn text into an AST.. Explain the grammar rules and construct an abstract syntax tree from a token stream.. Tokens, Grammars, Recursive descent, Error recovery Tokens A compiler's front door is the lexer (scanner), which turns a raw character stream into a sequence of tokens: pairs of a category (IDENT, NUMBER, PLUS, LPAREN, ...) and a lexeme, usually annotated with source position for diagnostics. Lexers are typically implemented as deterministic finite automata (DFAs), either hand-written as switch-driven state machines or generated from regular expressions by tools in the Lex/Flex family. Maximal munch (longest-match) resolves ambiguity: <= scans as one token, not < followed by =. Keywords are usually recognized by scanning an identifier and then checking it against a reserved-word table, rather than encoding each keyword as its own automaton path. Whitespace and comments are consumed and discarded (or attached as trivia for tooling). A well-built lexer also handles lookahead-sensitive cases, such as distinguishing a language's string interpolation delimiters or multi-character operators, and must produce a well-defined error token or diagnostic on invalid input rather than silently misclassifying it. Grammars Parsing recovers hierarchical structure from a flat token stream, and that structure is specified by a context-free grammar (CFG): a set of production rules over terminals (tokens) and nonterminals (syntactic categories). Grammars for expressions must encode precedence and associativity, typically through a cascade of nonterminals (expr -> expr + term | term, term -> term * factor | factor) so that 2 + 3 * 4 parses with multiplication binding tighter. Left recursion, natural for left-associative operators, is poison for naive top-down parsers and must be eliminated or handled via precedence climbing. A grammar is ambiguous if some string has two distinct parse trees (the classic dangling-else problem); compiler writers resolve ambiguity either by grammar rewriting or by explicit disambiguation rules in the parser. Recursive descent Recursive-descent parsing implements each nonterminal as a function that consults one or more tokens of lookahead to decide which production to take, then recursively calls the functions for the symbols on the right-hand side. It requires the grammar to be free of left recursion and, for a predictive Left-to-right, Leftmost-derivation (LL) parser using one token of lookahead (an LL(1) parser), requires the FIRST set (FIRST) and FOLLOW set (FOLLOW), the sets of tokens that can begin or immediately follow a given nonterminal respectively, to be disjoint across alternatives. Precedence climbing (or Pratt parsing) extends recursive descent to expressions efficiently by parameterizing the expression-parsing function with a minimum binding power, avoiding one nonterminal per precedence level. Recursive descent is popular in production compilers (Clang, V8, rustc's earlier stages) because it is easy to hand-tune for good error messages, unlike opaque table-driven Left-to-right, Rightmost-derivation (LR) parsers. Error recovery Real input is rarely well-formed, so a parser must recover from errors well enough to keep reporting further genuine issues without cascading false positives. Panic-mode recovery discards tokens until a synchronizing token (;, }) is found and resumes parsing from there. Phrase-level recovery attempts local fixes (inserting a missing token) to keep the parse going. Good diagnostics report the expected token set, the actual token, and precise line/column spans, and ideally suggest a fix. The Abstract Syntax Tree (AST) produced should mark error nodes explicitly so that later phases (semantic analysis) can suppress redundant cascading diagnostics rather than compounding the original error. Ambiguity and precedence Not every context-free grammar is unambiguous, and the dangling-else problem is the textbook case: in if (a) if (b) s1; else s2; it is not obvious from the grammar alone whether the else attaches to the first or second if. Parser generators resolve this either by rewriting the grammar to add an explicit matched and unmatched statement distinction, which removes the ambiguity at the cost of a larger grammar, or by declaring an explicit precedence and associativity for the construct and letting the tool apply a fixed rule, typically attaching the else to the nearest unmatched if. Choosing the wrong resolution does not produce a parse error; it silently changes what the program means, which is why a language's disambiguation rule belongs in its specification rather than being left as an unstated side effect of whichever parser generator happens to implement the front end. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Semantic analysis. Semantic analysis. Type-check a program.. Explain the type system and implement a type checker over a small language.. Scopes and symbols, Type systems, Checking, Diagnostics Scopes and symbols Semantic analysis walks the Abstract Syntax Tree (AST) to resolve names and check meaning that a context-free grammar cannot express. A symbol table maps identifiers to declarations (kind, type, storage location) and is organized around scopes: typically a stack of hash maps, pushed on block/function entry and popped on exit, so that lookup walks outward from the innermost scope until it finds a binding or exhausts the chain (implementing lexical/static scoping). Each declaration site inserts a symbol; each use site performs a lookup and, if resolution fails, produces an "undefined identifier" diagnostic bound to that specific reference. Shadowing is legal in most languages (an inner let x hides an outer one) but redeclaration within the same scope is typically an error. Forward references complicate this: some constructs (mutually recursive functions, class members) require a first pass that only declares names before a second pass that resolves bodies, since a single top-to-bottom pass would reject legitimate forward calls. Type systems A type system assigns types to expressions and enforces rules about which operations are legal on which types, catching an entire class of errors before code ever executes. Types range from primitives (int, float, bool) through composites (arrays, structs, pointers) to more advanced constructs (generics, sum types, function types). Type systems are characterized along two axes: static vs dynamic checking (compile time vs run time) and strong vs weak enforcement (whether implicit unsafe conversions are permitted). Type inference (as in Hindley-Milner) lets a compiler deduce types without full annotation, using unification over type variables constrained by how each expression is used. Subtyping and coercion rules (e.g., int widening to float) must be specified precisely, since ad hoc implicit conversions are a classic source of subtle bugs. Checking Type checking is a recursive traversal that computes (or checks) the type of every AST node against the rules of the type system, given the environment built from scope resolution. For an expression node, checking typically synthesizes a type bottom-up (e.g., a + b requires both operands' types to be checked and combined per the operator's typing rule); for statement/declaration nodes, checking often propagates an expected type top-down (e.g., checking a return against the enclosing function's declared return type). A binary operator's typing rule is a small function from a pair of operand types to a result type or an error; assignment checks that the right-hand type is compatible with the left-hand variable's declared type. Function calls check arity and that each argument's type is compatible with the corresponding parameter, and array/index expressions check that the indexed value is actually an array/pointer type and the index is integral. Diagnostics A production-quality checker does not stop at the first type error; it should recover locally (often by assigning the special "error type", which is compatible with everything, to suppress cascades) and continue collecting diagnostics for the rest of the program. Good diagnostics state what was expected, what was found, and where (with the precise span of the offending sub-expression, not just the enclosing statement), and should avoid duplicate reports of a single root cause. Because semantic errors follow syntax errors in the pipeline, a checker should also suppress semantic diagnostics for AST subtrees already marked as parse-error nodes, so a single malformed line does not generate a flood of unrelated messages. Type inference Not every type system requires a programmer to annotate every variable explicitly. Type inference lets the checker reconstruct a variable's type from how it is used, typically by generating a system of type equations from the syntax tree and then solving them through unification, the process of finding a substitution that makes two type expressions equal. A fully inferred system can still reject a genuinely ill-typed program; inference removes the annotation burden, it does not weaken the checker's guarantees. Most production languages choose local inference instead of whole-program inference, reconstructing types within a single function body while still requiring explicit annotations at module boundaries, because whole-program inference produces error messages that are technically accurate but often reported far from the line the programmer actually got wrong. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Intermediate representation. Intermediate representation. Lower an AST to an IR.. Describe the target intermediate representation and implement a lowering pass from the abstract syntax tree to it.. Why an IR, SSA, Lowering, Optimisation basics Why an IR Compilers insert an intermediate representation (IR) between the Abstract Syntax Tree (AST) and target code so that the N source languages and M target architectures reduce to N front ends plus M back ends, rather than N-by-M direct translators, and so that optimisation logic is written once against a uniform, analysis-friendly representation. A good IR is lower-level than an AST (control flow made explicit as basic blocks and branches, expressions flattened into simple three-address instructions) but still architecture-independent (unlimited virtual registers, no concrete calling convention yet). Three-address code, where each instruction has the shape dst = src1 op src2, is the classic textbook IR because it is simple to generate, simple to analyze, and close enough to real instruction sets to lower cheaply. SSA Static single assignment (SSA) form requires that every virtual variable be assigned exactly once in the program text, which turns def-use chains into direct pointers and makes many optimisations (constant propagation, dead-code elimination, common-subexpression elimination) simpler and more precise. Where control flow merges (after an if/else, at a loop header) and a variable may hold different values depending on the incoming path, SSA introduces a phi function, x3 = phi(x1 from block A, x2 from block B), that selects the value corresponding to the predecessor block actually taken at runtime. Constructing SSA requires computing the dominance frontier of each definition to know exactly where phi nodes are needed (the standard Cytron et al. algorithm), and destructing SSA before final code generation, since real hardware has no phi instruction, by inserting copies along predecessor edges. Lowering Lowering an AST to IR is a recursive translation, typically implemented with the same treewalk shape as type checking but emitting instructions instead of types. Expressions lower to sequences of three-address instructions that leave their result in a fresh virtual register; short-circuit boolean operators (&&, ||) lower to explicit branches rather than eager evaluation of both operands; if/else lowers to a comparison-and-branch followed by then/else basic blocks that both jump to a shared merge block; while/for loops lower to a header block (condition test), a body block, and a back-edge, with break/continue lowering to direct jumps to the loop's exit/header blocks respectively. Function calls lower to an explicit calling sequence: evaluate arguments into registers/stack slots per the IR's calling convention, emit a call instruction, and bind the result register. Optimisation basics Once code is in IR, a compiler applies target-independent optimisations before ever thinking about registers or instructions. Constant folding evaluates operations on compile-time-known constants ahead of time; constant propagation replaces uses of a variable known to hold a constant with that constant; dead-code elimination removes instructions whose results are never used (easy to detect precisely in SSA, where "never used" means the SSA name has no uses); common-subexpression elimination reuses a previously computed value instead of recomputing an identical expression. These passes are typically run to a fixed point, or in a standard pipeline order, because each pass can expose new opportunities for the others (folding a constant can make a branch's condition statically known, which then enables removing the dead branch entirely). Representations Intermediate representation is not a single fixed format; compilers choose among several depending on which later passes matter most. Three-address code, where each instruction has at most one operator and up to two source operands plus a destination, maps naturally onto register machines and is what this module's SSA form builds on. Stack-based intermediate representation instead has no named operands at all: every instruction pushes or pops values from an implicit stack, which is simpler to generate directly from an AST and is the choice made by bytecode formats such as the Java Virtual Machine's class-file format. A compiler targeting a register machine typically still lowers through a three-address form even when its front end first emits a stack-based bytecode, because register allocation, covered in the next module, has no natural analogue over an implicit stack. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Code generation. Code generation. Generate target code.. Explain instruction selection and implement a code generator that emits target instructions.. Instruction selection, Register allocation, Calling conventions, Emitting code Instruction selection Instruction selection maps intermediate representation (IR) operations onto the target's actual instruction set: here, the Compact 16-bit encoding of the Microprocessor without Interlocked Pipeline Stages (MIPS) instruction set, specifically its 16-bit compact encoding (MIPS16), as implemented by the DATUM emulator (DATUM), this course's own fixed name for its teaching target machine and not an acronym. The simplest strategy is a one-to-one macro expansion, where each three-address IR instruction becomes a small fixed sequence of target instructions; a more sophisticated approach is tree-pattern matching (as in tools built on the maximal-munch tiling idea), where the code generator matches the largest available instruction pattern against a subtree of the IR/expression tree to cover more work per instruction (e.g., fusing a multiply into a load if the target supports scaled addressing). Because MIPS16 is a load-store architecture, every memory operand must first be materialized into a register with an explicit load, and every computed value must be explicitly stored back if it needs to survive past the current instruction sequence, since there is no direct memory-to-memory arithmetic. Register allocation The IR uses an unbounded set of virtual registers, but DATUM has a small, fixed physical register file, so register allocation must map virtual registers to physical ones (or to spill slots in memory when demand exceeds supply). The standard approach builds an interference graph, where two virtual registers are connected by an edge if their live ranges overlap (computed by a liveness/def-use analysis over the Control-Flow Graph (CFG)), and then attempts to colour that graph with k colours, one per physical register, via Chaitin-Briggs graph-colouring: repeatedly remove low-degree (< k) nodes onto a stack, and if stuck with only high-degree nodes remaining, pick a spill candidate (favoring one with low use-density and high degree) and mark it to spill rather than colour. Spilled values are written to and read from stack slots around each use, which reintroduces exactly the memory traffic register allocation was trying to eliminate, so minimizing spills (not just achieving correctness) is the practical measure of a good allocator. Calling conventions A calling convention is the contract between caller and callee about where arguments and return values live, which registers the callee must preserve (callee-saved) versus may freely clobber (caller-saved), and how the stack frame is laid out. On the MIPS16/DATUM target this typically means: a fixed subset of registers dedicated to the first N integer arguments, remaining arguments passed on the stack, a designated return-value register, a frame pointer or stack-pointer-relative addressing scheme for locals and spills, and an explicit prologue (allocate frame, save callee-saved registers and return address) and epilogue (restore, deallocate, return) emitted around every function body. Getting this contract precisely right matters more than almost anything else in code generation, because a violation (clobbering a register the caller assumed was preserved) produces bugs that only manifest nondeterministically depending on what the register happened to hold. Emitting code The final phase walks the register-allocated IR/CFG and emits concrete assembly (or machine code) for the DATUM emulator: basic blocks become labelled instruction sequences, IR branches become the target's conditional/unconditional jump instructions with resolved label targets, and function bodies are wrapped in the prologue/epilogue from the calling convention. Basic-block layout should place the fall-through (most common) successor immediately after its predecessor where possible, to avoid an unconditional jump on the hot path. The emitted code must be validated not just by inspection but by actually running it on the DATUM emulator against known inputs and expected outputs, since register-allocation or instruction-selection bugs typically manifest as wrong runtime results rather than as errors visible in the generated text itself. Verification Generated code must be validated by actually executing it, not merely by inspecting the emitted instructions for plausibility. A minimal verification harness runs the DATUM emulator against a fixed suite of known inputs and compares the resulting register and memory state to precomputed expected outputs, catching register-allocation and instruction-selection bugs that would otherwise surface only as silently wrong results deep inside a larger program. Differential testing extends this further by comparing the code generator's output against a trusted reference interpreter that executes the IR directly, on the same inputs, so any divergence between the two implementations flags a code-generation bug immediately rather than after it corrupts an unrelated computation downstream. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/)