https://ssloy.github.io/tinycompiler/

[ ] [ ]
Skip to content
logo
Playing with code
Home
logo Playing with code

  * [*] tinycompiler tinycompiler
      + [ ] Home Home Table of contents
          o Introduction
          o Graphics!
              # Mandelbrot set
              # Zero-player breakout game
              # Fire
              # Sunset race
      + Abstract syntax trees
      + SLY: lexer and parser
      + Symbol tables
      + Displays
      + Assembly generation
      + DIY lexer
      + DIY parser
      + Afterword
  * [ ] tinyoptimizer tinyoptimizer
      + Home
      + mem2reg
  * [ ] strange things strange things
      + Cursed fire or #define black magic

Table of contents

  * Introduction
  * Graphics!
      + Mandelbrot set
      + Zero-player breakout game
      + Fire
      + Sunset race

TinyCompiler: a compiler in a week-end

Introduction

[compiler]

Have you ever wondered how a compiler works, but you never found
courage to find out? Then this series of articles is for you. I have
never had the chance to look under the hood either, but one week-end
I have decided to to write a translator from the esoteric programming
language wend (short for week-end), which I just invented myself,
into regular GNU assembly. The goal is to keep the code as tiny as
possible, 500-ish lines of python sounds great. The main repository
lives on github (don't forget to check out other tiny* repositories
in my profile).

Spoiler alert: I am currently working on a tinyoptimizer, a
minimalist optimizing compiler.

So behold, here is a program that uses virtually all concepts in wend
:

Fixed-point square root

 1 main() {
 2     // square root of a fixed-point number
 3     // stored in a 32 bit integer variable, shift is the precision
 4 
 5     int sqrt(int n, int shift) {
 6         int x;
 7         int x_old;
 8         int n_one;
 9 
10         if n > 2147483647/shift { // pay attention to potential overflows
11             return 2 * sqrt(n / 4, shift);
12         }
13         x = shift; // initial guess 1.0, can do better, but oh well
14         n_one = n * shift; // need to compensate for fixp division
15         while true {
16             x_old = x;
17             x = (x + n_one / x) / 2;
18             if abs(x - x_old) <= 1 {
19                 return x;
20             }
21         }
22     }
23 
24     int abs(int x) {
25         if x < 0 {
26             return -x;
27         } else {
28             return x;
29         }
30     }
31 
32     // 25735 is approximately equal to pi * 8192;
33     // expected value of the output is sqrt(pi) * 8192 approx 14519
34 
35     println sqrt(25735, 8192);
36 }

Since I am interested in a compiler, the language being implemented
is of no importance. I am not trying to invent yet another C++
killer, that is not the point. Wend is a simple language similar to C
or Java, but with far less features. Wend is strongly typed, with no
pointers, arrays, closures, dynamic memory allocation, garbage
collector or parallel computations. It supports nested functions and
function overloading, a bare minimum for the first dive into compiler
theory.

By the way, I have spent a lot more time on writing test programs
than on the compiler itself :)

Graphics!

It is so dull to compute Fibonacci numbers, so here are more eyecandy
examples for the compiler, check test-programs/gfx/*.wend files.

Mandelbrot set

[mandelbrot]

Zero-player breakout game

[breakout]

Fire

[fire]

Sunset race

[sunset-rac]

Made with Material for MkDocs