A Two-Pass Compiler for a Tiny C-Subset Language with a Stack Virtual Machine (Python)

TinyC is a small, statically typed, C-shaped teaching language — int, float, bool and void types, arithmetic and logical operators, if/else, while, for, single-dimension arrays, and functions with parameters and recursion — and this project builds its complete compiler and virtual machine in Python 3.12. The pipeline is a classic two-pass design: the front end lexes, parses by recursive descent into an AST and runs semantic analysis with a scoped symbol table; the back end generates three-address code, lowers it to stack bytecode and executes it on a custom stack virtual machine with call frames.

The project is deliberately written from scratch — hand-written lexer, hand-written parser, hand-written VM — because the point is to make every phase of the dragon book (Aho, Lam, Sethi, Ullman) concrete and inspectable. Every stage can be run standalone: tinyc lex demo.tiny prints the token stream, tinyc parse dumps the AST, tinyc check lists semantic errors with line and column, tinyc compile emits three-address code and bytecode, and tinyc run executes the program on the VM.

What turns it from a code exercise into an M.Sc project is the measurement: a 70-program test corpus (40 valid, 30 invalid) pins down behaviour, and a benchmark suite (recursive Fibonacci, bubble sort on 1,000 elements, a prime sieve to 10,000) reports instruction counts and VM steps with and without the -O constant-folding pass. The dissertation quantifies what each phase costs and what the optimiser saves — numbers you can defend line by line in the viva.

Compiler-design papers are examined as theory — first/follow sets, parse tables, syntax-directed translation schemas — but students rarely assemble the phases into a working whole, so the connections between a grammar, a symbol table and generated code remain notional. Existing lab exercises use scanner and parser generators (flex, bison, ANTLR), which perform the interesting constructions invisibly: the student writes regular expressions and grammar rules but never implements a token stream, an LL(1) parse, a scope chain or an instruction encoder. There is also rarely any measurement: a compiler is treated as correct or incorrect, not as a pipeline whose phases have countable costs and whose optimisations have countable benefits.

The need is for a complete but small compiler — language design, hand-written front end, semantic analysis, explicit three-address intermediate code, bytecode and a virtual machine — that a single M.Sc student can build and fully understand, coupled with a test corpus that pins down erroneous input handling and a benchmark suite that quantifies the effect of optimisation. That combination makes compiler theory demonstrable, measurable and viva-defensible.

Abstract

Compiler construction integrates much of an M.Sc computer-science education — automata and grammars, data structures, algorithms, architecture — into one coherent artefact. This project designs and implements TinyC, a C-subset teaching language, with a two-pass compiler and a stack virtual machine in Python. The front end (lexer, recursive-descent parser, semantic analyser) and back end (three-address code, stack bytecode, VM) are built from scratch and evaluated on a 70-program corpus and a three-program benchmark suite measuring instruction counts and VM steps with and without constant folding.

Introduction

The University of Madras M.Sc (CS) curriculum treats compiler design as a core theory paper, but the theory stays abstract without an implementation: LL(1) grammars, first/follow sets and intermediate representations become real only when a parser you wrote fails on your own test case. TinyC is sized so one student can build, test and understand every line in one semester, while exercising every classical phase.

Language Design

• Types: int, float, bool, void; implicit int-to-float widening only.
• Statements: declarations, assignment, if/else, while, for, break, continue, block-scoped bodies.
• Expressions: C-style precedence — arithmetic, relational, equality, logical && || ! — with short-circuit evaluation in the VM.
• Data and functions: single-dimension arrays; built-in print(x); typed functions with positional parameters, recursion and a mandatory main.
• The grammar is kept LL(1): left recursion is eliminated and if is disambiguated by mandatory blocks, so the parser needs one token of lookahead.

Existing Work and Positioning

• The dragon book defines the phase model; Crafting Interpreters demonstrates a tree-walking interpreter and a bytecode VM; Python's ast module shows an industrial AST.
• Most student compilers stop at interpretation or skip semantic analysis; TinyC implements both a semantic checker and an explicit three-address IR before bytecode, because TAC is what the syllabus examines and what makes optimisation measurable.
• Generator-based labs (flex/bison) hide scanner and parser construction behind tools; hand-building is the point.

Proposed System

1. Lexer — longest-match tokenizer with line/column tracking and an error token for illegal characters.
2. Parser — recursive descent over the LL(1) grammar; dataclass AST; panic-mode recovery skipping to the next ; or } so one compile surfaces multiple errors.
3. Semantic analyser — scope-chained symbol table checking undeclared/redeclared identifiers, type mismatches, argument counts and return paths.
4. IR and bytecode — linear three-address quadruples lowered to compact stack bytecode with a constant pool; jump targets back-patched by label.
5. Stack VM — operand stack, frame stack, bounds-checked arrays, and a step limit turning runaway recursion into a diagnostic.
6. Optimiser (-O) — constant folding and algebraic identities on the AST; the harness reports instruction-count and VM-step savings.

Feasibility

• Technical: every phase is standard and Python-expressible; the largest component (parser + semantic) is ~1,200 lines.
• Time: 20 weeks at PG project pace covers phases, corpus and measurement; the 60% report weight reflects substantial written analysis.
• Operational: everything runs offline on a plain laptop; the demo needs only Python and pytest.

In scope

• One statically typed language (TinyC) with the feature list above; one grammar; one target (custom stack bytecode).
• Hand-written lexer and parser (no flex/bison/ANTLR/PLY); three-address code and bytecode as text/JSON artefacts.
• Semantic checks limited to scoping, typing, argument counts and return paths.
• One optimisation pass (constant folding + algebraic identities); measurement of its effect on the benchmark suite.
• Deterministic execution on the VM (no concurrency, no externals beyond print).

Out of scope

• Register allocation, liveness, instruction scheduling and native/assembly code generation.
• Pointers, structs, multi-dimensional arrays, heap allocation and a garbage collector.
• Debugger, IDE integration, and any parser-generator toolchain.
• Competitive performance against CPython — Python is the implementation language for clarity; speed of the compiled language itself is a measured quantity, not a goal.

SDLC: iterative model with a fixed phase order. Compiler phases have strict dependencies (you cannot check types before an AST), so increments follow the pipeline rather than feature areas; each phase ends with its own pytest suite before the next begins.

Evaluation approach: correctness is pinned by the corpus (golden output files for valid programs; expected diagnostic catalogue for invalid ones); quality is measured by benchmark tables (static instruction counts, dynamic VM steps, wall time, with and without -O); robustness is measured by the recovery suite (a file with five seeded errors must yield five located diagnostics, not one). Every number in the dissertation is regenerable with one pytest command.

The compiler is a strict seven-stage pipeline; each stage consumes the previous stage's output file or object, so any stage can be inspected in isolation — the property that makes the project examinable.

flowchart TD
  SRC["source .tiny file"] --> LEX["Lexer (tokens + line/col)"]
  LEX --> PAR["Recursive-descent parser (LL(1))"]
  PAR --> AST["AST"]
  AST --> SEM["Semantic analyser + scope-chain symbol table"]
  SEM -->|"typed, annotated AST"| OPT["-O constant folding (optional)"]
  OPT --> TAC["Three-address code generator"]
  TAC --> BC["Bytecode encoder + constant pool"]
  BC --> VM["Stack VM (operand stack + frame stack)"]
  VM --> OUT["program output"]
  SEM -->|"errors"| DIAG["Diagnostic list (line, col, code)"]
  PAR -->|"syntax errors"| DIAG

Data structures at the seams. Tokens are (kind, lexeme, line, col) tuples; the AST is a hierarchy of small dataclasses; the symbol table is a chain of dictionaries with parent pointers (one entry per scope, pushed on block/function entry); TAC is a list of op a b c quadruples; bytecode is an array of opcode operand pairs plus a constant pool of literals.

Runtime model. The VM keeps an operand stack for expression evaluation and a frame stack for calls — each frame holds the return address, the function's locals and its own operand region. CALL pushes a frame, RET pops it and leaves the return value on the caller's stack; recursion (Fibonacci) therefore exercises real stack discipline, and the step limit (default 10 million VM steps) turns infinite recursion into a clean diagnostic instead of a hang.

flowchart LR
  subgraph VM["Stack VM per frame"]
    FS["Frame: locals + return addr"] --> OS["Operand stack"]
    OS --> ALU["Arithmetic / compare / logic"]
    ALU --> OS
    FS --> CT["Control: JMP / JZ / CALL / RET"]
  end
  BC["Bytecode + constant pool"] --> FS

Error flow. Syntax and semantic errors never raise raw exceptions to the user: they accumulate as structured diagnostics (line, column, code, message), and after panic-mode recovery the compiler reports all found errors, sorted by position — the behaviour the invalid-program corpus asserts.

• Register-based bytecode and a comparison study of stack vs register VM step counts on the same corpus.
• More optimisations: dead-code elimination for pure assignments, loop-invariant hoisting and constant propagation across statements, each measured like -O.
• Type checker upgrade: user-defined structs with member access, and a small trait-based print protocol.
• Compiler as a service: a tiny web front end that renders the AST and TAC live in the browser for classroom demos.
• Retargeting: a MIPS-subset assembly generator behind the same TAC IR, turning the project into a full three-target (interpret/TAC/assembly) system.