blog.petitviolet.net

Tiny compiler written in Ruby

2020-06-20

Ruby

As a software engineer’s habit, I’ve implemented a toy programming language in Ruby for my learning. GitHub repository is petitviolet/9cc-ruby.

What it looks like

Almost basic syntax is supported, and only int type is available.

  • use number

    • n(number)
  • arithmetic operations

    • +, -, *, /, %
  • unary operations

    • +n, -n(unary)
  • comparison operations

    • >, >=, <, <=, ==, !=
  • condition

    • if (cond) ... else ...
  • multiple statements

    • 1 + 2; 3 + 4;
  • return

    • return 10
  • block

    • { 2 * 3 }
  • local variables

    • a = { 2 * 3 }
  • define function

    • def add(i, j) { i + j }
  • call function

    • add(1, 2)

Running a ruby script generates an assembly program.

$ rbenv exec ruby -W0 lib/9cc.rb '1 + 2'
.intel_syntax noprefix # headers
.global main
main:
  push r14
  push r15
  push rbp
  mov rbp, rsp
  sub rsp, 0
  push 1
  push 2
  pop rdi
  pop rax
  add rax, rdi
  push rax
  pop rax
  mov rsp, rbp
  pop rbp
  pop r15
  pop r14
  ret

Obviously it generated wasteful and redundant one, but it works :)

Since it aims to be runnable on x86-64 Linux, it requires non-macOS environemnt. petitviolet/9cc-ruby a docker image that I use is

$ docker run --rm  petitviolet/9cc-ruby:latest uname -a
Linux fb476515a500 4.19.76-linuxkit #1 SMP Thu Oct 17 19:31:58 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

Then, prepared a script(Makefile) to compile an assembly, run, and check if the result is correct at once.

$ make docker/try ARG="9 'def square(i) { i * i }; def f(n) { if (n % 2 == 0) n else square(n) }; f(3)'"
...
[2020-06-17 13:58:56.458 UTC]OK! def square(i) { i * i }; def f(n) { if (n % 2 == 0) n else square(n) }; f(3) => 9

This output shows the given small program def square(i) { i * i }; def f(n) { if (n % 2 == 0) n else square(n) }; f(3) returned 9 as its result expectedly.

How it’s implemented

As usual of language implementations, the flow of compilation is like:

  • tokenize

    • tokenize given string
  • parse

    • parse tokens and build an abstract syntax tree
  • generate

    • generate an assembly program from the AST

It depends on Rstructural gem so much that I wrote a blog about.

Empower Pattern Matching in Ruby Quick overview of pattern match in Ruby and Gems to empower it Ruby2.7 provides Pattern Matching feature as an experimental one. https://www.ruby-lang.org/en/news/2019/12/25/ruby-2-7-0-released/ I used to do pattern…

All of the tokens and AST nodes are defined as Rstructural::ADT, and parser and generator use pattern matching on them.

Misc

Indeed, it does not work well, for example:

  • return different values every run

    $ make docker/try ARG="9 'def double(i) { i * 2 }; def square(j) { j * j }; def f(n) { if (n % 2 == 0) double(n) else square(n) }; f(3)'"
    [2020-06-17 14:45:30.474 UTC]NG! 9 expected, but got 144
    make: *** [docker/try] Error 1
    
    $ make docker/try ARG="9 'def double(i) { i * 2 }; def square(j) { j * j }; def f(n) { if (n % 2 == 0) double(n) else square(n) }; f(3)'"
    [2020-06-17 14:45:31.841 UTC]NG! 9 expected, but got 80
    make: *** [docker/try] Error 1
    
    $ make docker/try ARG="9 'def double(i) { i * 2 }; def square(j) { j * j }; def f(n) { if (n % 2 == 0) double(n) else square(n) }; f(3)'"
    [2020-06-17 14:45:33.426 UTC]NG! 9 expected, but got 144
    make: *** [docker/try] Error 1
  • segmentation fault :(

    $ make docker/try ARG="55 'def fib(n) { if (n == 0) 0 else if (n == 1) 1 else fib(n-1) + fib(n-2) }; fib(10)'"
    ./test.sh: line 3:    42 Segmentation fault      ./tmp
    [2020-06-17 14:44:54.857 UTC]NG! 55 expected, but got 139
    make: *** [docker/try] Error 1

Anyway, it was fun and good learning for me!