A compiler for a small language
The problem
Build a compiler for a small language with variables, arithmetic, comparisons, if/else, while and print, that compiles to stack-machine code and runs it on your own virtual machine.
Requirements
- A lexer that reports invalid characters with their line and column
- A recursive-descent parser that builds an abstract syntax tree and reports the first syntax error clearly
- A symbol table with block scopes that reports undeclared and duplicate names
- A type checker for int and bool that reports every type error with its line
- A code generator that emits stack-machine code with backpatched jumps
- A virtual machine that runs the code and can print a trace of each step
Technologies
- Python
- Regular expressions
- Recursive descent
- Dataclasses
- Stacks
Step by step
- Write the grammar of the language on paper, with precedence levels.
- Write the lexer and test it on correct and incorrect programs.
- Write the parser and a function that prints the syntax tree.
- Add name resolution and type checking as separate tree walks.
- Write the code generator and print the code with addresses.
- Write the virtual machine, then test whole programs such as factorial, GCD and primes.
Expected result
A working compiler and virtual machine that turn a small language into running code, with clear error messages at every phase.
How it is evaluated
- Correct programs give the right output, checked on at least ten test programs
- Every kind of error is reported with its line, and the compiler never crashes
- Each phase is a separate function or class with its own tests
- The generated code for a loop matches the layout from the lessons
Ways to improve it
- Add functions with parameters and a call stack
- Add constant folding and dead code elimination before code generation
- Compile to Python source or WebAssembly text instead of your own bytecode