NJU Compilers — a guided C-- compiler (flex/bison → MIPS)

A complete, four-stage compiler for C-- (a small C subset) — lexing, parsing, semantic analysis, three-address intermediate code, and MIPS32 target code — an independent, from-scratch implementation of NJU 编译原理 (Nanjing University Compiler Principles), part of a csdiy.wiki full-catalog build.

Overview

C-- is a simplified C: int/float scalars, 1-D and 2-D arrays, structs, if/else, while, functions, and arithmetic/relational/logical operators. This repo implements the full compiler pipeline for it, following the classic NJU four-lab sequence:

1. Lab 1 — lexical & syntax analysis. A flex scanner and a bison parser build an n-ary parse tree, with precise Type A (lexical) and Type B (syntax) error reporting and error recovery.
2. Lab 2 — semantic analysis. A scoped, chained-hash symbol table and a structural type system implement all 17 C-- semantic checks (undefined/redefined names, type mismatches, bad field/array/function use…).
3. Lab 3 — intermediate code. Syntax-directed translation to linear three-address IR (temporaries, labels, IF…GOTO, CALL/ARG, pointer &/* addressing, DEC for aggregates, READ/WRITE).
4. Lab 4 — target code. The IR is lowered to MIPS32 assembly with a naive stack-slot register allocator and the standard SPIM calling convention + I/O syscalls.

Everything runs and is verified: the IR is executed by a bundled IR virtual machine, and the emitted MIPS is executed by the SPIM simulator — both produce the mathematically correct answers.

Results (measured on Ubuntu/WSL2, gcc 13.3, SPIM 8.0)

Lab	What it does	Verification	Result (measured)
1 Lexer+Parser	parse tree, A/B error reports	3 programs (valid, lexical-err, syntax-err)	correct tree; errors at exact lines — see results/lab1/
2 Semantics	17 error kinds, structural types	valid program → 0 errors; two error suites	all 17 error types fire with correct messages/lines — results/lab2/
3 IR gen	three-address code	executed on tools/ir_vm.py	fib(10)=55, sum(1..100)=5050, Σi² (0..4)=30
4 MIPS gen	MIPS32 for SPIM	executed on spim	fib(10)=55, fib(15)=610, sum(100)=5050, Σi²=30

Real SPIM transcript (results/lab4/spim_runs.txt):

# Lab 4 — generated MIPS32 executed on SPIM 8.0
fib(10)  = 55    (expected 55)
fib(15)  = 610   (expected 610)
sum(100) = 5050  (expected 5050)
array    = 30    (expected 30)

Sample parse tree for int main(){ int i=0; j=i+1; ... } (Lab 1):

Program (1)
  ExtDefList (1)
    ExtDef (1)
      Specifier (1)
        TYPE: int
      FunDec (1)
        ID: main
        LP
        RP
      CompSt (2)
        ...

Sample IR for recursive Fibonacci (Lab 3, results/lab3/fib.ir):

FUNCTION fib :
PARAM v1
IF v1 < #2 GOTO label1
GOTO label2
LABEL label1 :
RETURN v1
...
t2 := CALL fib
...
t5 := t2 + t4
RETURN t5

Implemented assignments

• Lab 1 — Lexical & Syntax Analysis — flex scanner + bison parser, n-ary parse tree, decimal/octal/hex ints, plain/scientific floats, block & line comments, Type-A/Type-B error reporting with error recovery.
• Lab 2 — Semantic Analysis — scoped symbol table (functions/vars/structs), structural type equivalence, and every one of the 17 semantic error kinds.
• Lab 3 — Intermediate Code Generation — translate_Exp/Cond/Stmt schemes, short-circuit booleans, arrays & structs via address arithmetic, function calls, READ/WRITE; verified by an IR interpreter.
• Lab 4 — MIPS32 Code Generation — stack activation records, $a0-$a3 argument passing + stack spill, recursion, syscall I/O; verified in SPIM.

Project structure

nju-compilers/
├── include/        ast.h  type.h  symtab.h  semantic.h  ir.h  codegen.h
├── src/
│   ├── lexical.l   flex scanner            (Lab 1)
│   ├── syntax.y    bison grammar           (Lab 1)
│   ├── ast.c       parse-tree build/print  (Lab 1)
│   ├── symtab.c    types + scoped symtab   (Lab 2)
│   ├── semantic.c  17 semantic checks      (Lab 2)
│   ├── ir.c        three-address IR gen    (Lab 3)
│   ├── codegen.c   MIPS32 code gen         (Lab 4)
│   └── main.c      phase-selected driver
├── tools/ir_vm.py  IR virtual machine (execution evidence for Lab 3)
├── tests/          lab1..lab4/*.cmm  test programs
├── results/        captured real outputs (parse trees, errors, IR, .s, run logs)
├── scripts/        run_tests.sh  gen_results.sh
└── Makefile        make lab1|lab2|lab3|lab4|all|test

How to run

Requires flex, bison, gcc/cc, make, and (for Lab 4 execution) spim. On Ubuntu/WSL2: sudo apt-get install -y flex bison build-essential spim.

make all           # builds bin/parser1 .. bin/parser4 (one per lab)

# Lab 1 — print the parse tree (or the lexical/syntax errors)
./bin/parser1 tests/lab1/test1.cmm

# Lab 2 — semantic error report (empty output == no errors)
./bin/parser2 tests/lab2/test_ok.cmm

# Lab 3 — emit intermediate code, then run it
./bin/parser3 tests/lab3/fib.cmm out.ir
echo 10 | python3 tools/ir_vm.py out.ir        # -> 55

# Lab 4 — emit MIPS, then run it in SPIM
./bin/parser4 tests/lab4/fib.cmm out.s
echo 10 | spim -file out.s                     # -> 55

# regenerate every artifact under results/
bash scripts/gen_results.sh

Verification

• Lab 1/2: outputs in results/lab1 and results/lab2 are the compilers' real stdout; the error suites exercise all Type-A/B and all 17 semantic errors.
• Lab 3: tools/ir_vm.py executes the generated IR; results/lab3/ir_vm_runs.txt records fib(10)=55, sum(100)=5050, array=30.
• Lab 4: the emitted .s files are run under spim; results/lab4/spim_runs.txt records the identical, correct answers on real MIPS simulation (including deep recursion in fib(15)=610).

Re-run all of it with bash scripts/gen_results.sh after make all.

Tech stack

C11, GNU flex 2.6.4, GNU bison 3.8.2, GNU make; Python 3 for the IR VM; SPIM 8.0 for MIPS execution.

Key ideas / what I learned

• Building an n-ary parse tree from bison semantic actions and driving the whole back end off a single shared tree.
• Robust lexical error handling: swallowing a malformed number as one token so a bad constant never cascades into a spurious syntax error.
• Structural (not name) type equivalence for arrays and structs.
• Scoped symbol tables via a chained hash table plus a per-scope teardown list.
• The classic translate_Cond short-circuit scheme and address arithmetic for arrays/structs in three-address code.
• A real MIPS calling convention: activation records, saved $ra/$fp, register-then-stack argument passing, and correct recursion.

Credits & license

Based on the labs of NJU 编译原理 (Compiler Principles), Nanjing University (course materials by the NJU compilers teaching group; grammar after Aho et al., Compilers: Principles, Techniques, and Tools). This repository is an independent educational reimplementation; all course materials and the C-- specification belong to their original authors. Original code here is released under the MIT License.