Writing a compiler in Ruby, bottom up

Vidar Hokstad __

Writing a compiler in Ruby, bottom up

(To follow my compiler related posts, either subscribe to my main RSS feed, or the compiler specific one )

Back in March 2008 I started publishing a series on how to write a compiler in Ruby, bottom up, that is, starting with the code generator and working my way up instead of the more traditional approach of writing the parser first. Here are the parts I've published on my blog so far.

(The bits labeled "interlude" are sort-of related articles in that the cover issues with writing/developing compilers, or issues related to compilation, but are not directly tied into the actual article series)

Step 1 - Creating a simple prolog / epilog for the main function
Step 2 - Function calls / Hello World
Step 3 - Chaining expressions ; Adding sub-expressions
Step 4 - Defining functions ; Adding support for a runtime
Step 5 - Number literals ; if .. then .. else
Step 6 - Anonymous functions: lamba / call
Step 7 - Making use of lambda / call ; Function arguments
Step 8 - Assignment, arithmetic and comparisons
Step 9 - A builtin "while"
Step 10 - Testing the compiler: A primitive "parser"
Step 11 - A separate emitter class to output assembler
Step 12 - Adding support for arrays
Interlude - A simple operator precedence parser
Step 13 - Local variables
Step 14 - Variable length arguments
Step 15 - Starting on the real parser
Step 16 - Extending the parser
Step 17 - Inferring "let"'s
Step 18 - Plugging in an operator precedence parser
Interlude - The Ruby Object Model - useful overview as the next steps is to start fleshing out an object model
Step 19 - The Object Model
Interlude - The problem with compiling Ruby - Overview of some of the problems with compiling Ruby
Step 20 - Taking stock of where we are; detail walkthrough of the shunting yard parse component
Step 21 - Basic support for the Symbol class; starting to work on attr_reader/attr_writer/attr_accessor
Step 22 - A diversion into method_missing
Step 23 - Real Strings: Turning strings into objects
Interlude - How to implement closures
Step 24 - The Outer Scope: Cleaning up and adding the "main" object
Step 25 - Towards define_method via closures
Step 26 - Taking a stab at STABS support (debugging/gdb)
Step 27 - The Operators - Part 1: Parsing; The start of the removal of 'runtime.c'
Step 28 - The Operators - Part 2: Turning numbers into Numbers (or small enough integers into Fixnum's at least)
Step 29 - The Operators - Part 3: Operating on our newly minted Fixnums
Step 30 - The Operators - Part 4: Comparisons
Step 31 - Stringing things together; basic string output and string interpolation
Step 32 - Testing code generation
Step 33 - Register Allocation
Step 34 - Putting self in a register
Step 35 - Towards Self Hosting
Step 36 - Scanning for problems
Step 37 - Default Arguments
Step 38 - Super
Step 39 - To be or not to be nil
Step 40 - Untangling "expect"
Step 41 - Messy further steps towards self-hosting
Step 42 - Re-opening class definitions
Step 43 - Eigenclasses
Step 44 - Mostly wrapping up self-hosting of the tokenization code
Step 45 - '#send' and method lookup (provisionally April '15)

All the code can now be found in this GitHub repository

A recent (as of 2014) article series on "reconstructing" Ruby (in C)

Someone commenting on this series on Hackernews pointed to Nicklaus Wirth's excellent book on compiler construction (PDF available on his homepage) as a good starting point from a traditional, top down point of view. It's a good and very approachable book, and well worth a read.

Another great series with a more traditional approach is a famous series by Jack Crenshaw: Let's build a compiler

This page at Stackoverflow has a great list of other compiler writing resources.

Please enable JavaScript to view the comments powered by Disqus. blog comments powered by Disqus

I'm a Norwegian technologist who has been living in London since 2000. I have a son, Tristan, born in 2009.

I've got development and management experience from a number of startups as well as more established companies, after co-founding my first company at age 19. I currently split my time between being the Technical Director of Nudge CRM Ltd, and running my consulting business, primarily related to development and devops. (More...)

Contact me

__ [email protected]

__ __ __

12 KiB Raw Permalink Blame History

Writing a compiler in Ruby, bottom up

Writing a compiler in Ruby, bottom up

Related resources

Contact me

Tags

12 KiB

Raw Permalink Blame History