Skip to content

I Wrote a Compiler

February 9, 2014

Yes, I wrote a C compiler.  I did this decades ago, but I’m still amazed when I recall this episode.  It’s the enormity of it.  All that time I devoted.  All that code I wrote out on paper.  It seems impossible now.  I had a Motorola 6809 microcomputer with 64 megs of memory.  It came with an editor and a macro assembler that produced absolute object code.  The intention was that you write assembler code and run it through the assembler to produce an object module.  This always loaded at the address used by the start command of the ROM monitor.  I dreamed of better things than that.

I bought a textbook called “Principles of Systems Programming”.  It described wonderous things like data structures, symbol tables, and compiler design, using the Multics OS in examples.  The first thing I wrote was a macro set for the assembler that identified external symbols and added a symbol table to each object file.  It required relocatable assembler code, but this was easy to do because the 6809 had relative branch instructions.

Next I wrote a linker, based loosely on the IBM MVS linkage editor.  For this, I wrote out pages of pseudo-code on paper.  This I translated into 6809 assembler code, typed it into the editor, and fed it into the macro assember.  When given a list of object files on the command line, the linker would produce a relocatable load module as output, with all symbols resolved.  The load module was also an archive, so that by specifying a new object file and an old load module as input, it could replace one object file within the load module.  I used that feature many times.  I was very pleased with this linker, once it was complete.  It worked exactly as I had intended.

My final project was to be a compiler, but I realized that I had to write it in C, not in assembler.  I needed another C compiler to start with.  I could have used a cross-compiler at work, but I decided to use one that would run on my 6809 machine at home.  The Tiny C compiler was available for many microcomputers, including mine.  It used the model of a one-register stack machine for all CPU types, with a function library for each type.  In fact, every C operation was handled by a call to a library function.  It included source files and could compile itself.  The output from Tiny C was assembler code, to be fed to the native assembler.

My compiler was going to be better than that.  The parser compiled C statements into a tree structure, just like in the book.  I used the grammar from the portable C compiler, with parts omitted.  I did the translation to C at work and then transported the resulting C file to my home.  The code generator converted the tree structure into relocatable assembler code.  It had to be able to compile itself.  It had to be able to compile the entire C grammar, with the exception of the goto statement and floating point variables.  This all seemed possible to me.

The source for my compiler was a whole series of files written in C.  One by one, they were compiled with one of the compilers and assembled into object files.  They were linked into a load module with my new linker.  I couldn’t do all of this at once because of the 64-megabyte memory limit.  Consequently, I started the process with the Tiny C compiler, a parser that handled only the most common C statement, and parts of the Tiny C library.

As I built up the compiler, I replaced the Tiny C function calls with direct assembler statements.  To add two numbers, for example, could be done with a single assembler statement.  This replaced the function call plus about ten statements in the library.  The compiler also kept track of register contents, eliminating many load and store instructions, especially when it used multiple registers.  This optimization meant that my compiler became smaller and faster.  It was able to compile more and more of its own source files.  Eventually, there was no trace of Tiny C left in my compiler.

The result was a working C compiler for the 6809 that produced reasonably compact code.  In the process of building it, I learned a great deal about memory usage and operation handling in C.  I was extremely pleased with my accomplishment.  Of course, once the compiler and linker were completed, I didn’t use them very much.  There are always better and newer things that attract my interest.  I still say that that’s a good thing.

Advertisements

From → Uncategorized

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: