Bootstrapping a simple compiler from nothing
	============================================

This document describes how I implemented a tiny compiler for a toy
programming language somewhat reminiscent of C and Forth. The funny
bit is that I implemented the compiler in the language itself without
directly using any previously existing software. So I started by
writing raw machine code in hexadecimal and then, through a series of
bootstrapping steps, gradually made programming easier for myself
while implementing better and better "languages".

The complete source code for all the stages is in a tar archive:
<http://www.rano.org/bcompiler.tar.gz>. This text is the README file
from that archive. So, if you are reading this on-line, you can fetch
the tar archive and continue off-line, if you prefer.

The code only runs on i386-linux, though it would be easy to port it
to another operating system on i386, and probably not at all hard to
port it to a different architecture.


HEX1: the boot loader
---------------------

You could input a short program into the memory of an early computer
by using switches on its front panel. This short program might then
read in a longer program from punched cards. To write a program on
punched cards you did not need an editor program, as you could write
new cards using an electro-mechanical card punch and manually insert
and remove cards from the deck. So, if we were using an early
computer, we could really implement a compiler without using any
existing software. Unfortunately, a modern PC has neither front panel
switches nor a punched card reader, so you need some software running
on the machine just to read in a new program. In fact, you probably
need some rather complex software running on the machine: just take a
look at /usr/src/linux/drivers/block/floppy.c, for example.

Since we are doing this on a PC running Linux, we have to define some
other starting point. Rather than use the raw hardware, we start with
these facilities:

 - an operating system;

 - a simple text editor (or we could use Emacs and pretend it's a
   simple text editor);

 - a shell that lets us run a program with file descriptors connected
   to particular files (this way the programs we write only need to
   read from and write to file descriptors and do not have to know
   about opening files);

 - an initial program to convert hexadecimal to binary so that we can
   compose our first programs in hexadecimal, using the text editor,
   and then "compile" them to binary in order to run them (this
   corresponds roughly to the program that you might enter into an
   early computer using front panel switches).

Our initial program is hex1.he (the source in hexadecimal) or hex1
(the binary). If you want to check that hex1 really is the binary
corresponding to hex1.he, you can do a hex dump of it:

	od -Ax -tx1 hex1

If you use hex1 to process hex1.he the result it hex1 again:

	./hex1 < hex1.he | diff - hex1

So we can think of hex1 as a trivial bootstrapping compiler for a
language called HEX1.

Apart from comments and white space, the syntax of HEX1 is
/([0-9a-f]{2})*/. Comments start with '#' and continue to the end of
the line. The semantics of HEX1 is the semantics of machine code,
which is rather complex. Fortunately we can restrict ourselves to a
tiny subset of the full instruction set.

In hex1.he I have put the corresponding assembler code in comments
next to the machine code. The file starts with two ELF headers: a
52-byte file header and a 32-byte program header. It is not necessary
to understand all the fields in the ELF header. The most interesting
fields are:

* e_entry, which specifies where execution should begin. Here it is
0x08048054, which is directly after the ELF headers (labelled _start).

* p_vaddr and p_paddr, which specify the target address in memory.
Here it is 0x08048000, which is standard for Linux binaries.

* p_filesz and p_memsz, which should be set to the length of the file.
It seems not to matter if you put a larger number here, and I will
make use of that later, though here I have put the correct value.

(For more information about ELF do a web search. SCO and Intel have
some useful on-line documents.)

The code at _start is a loop that reads pairs of hex digits by calling
gethex and outputs bytes by calling putchar. Next comes putchar, which
uses the "write" system call. Then gethex, which calls getchar and
contains a loop for skipping over comments. The ASCII characters
[0-9a-f] are converted correctly to the values 0 to 15; everything
below '0' (48) is treated as a space and ignored; other characters are
misconverted, as there is no error detection. The function getchar
uses the "read" system call, and calls "exit" at the end of the file.


HEX2: one-character labels
--------------------------

Writing machine code in hex is not much fun. The worst part is
calculating the addresses for branch, jump and call instructions. Here
I am using relative addresses, so I have to recalculate the address
every time I change the length of the code between an instruction and
its target. It would be no better if I were using absolute addresses:
then I would have to change all references to locations after the
change.

So the first feature I add for my convenience is a function for
computing relative addresses. Instead of writing

	# function:
		...
		e8 cc ff ff ff		# call function

I will be able to write:

	.F			# function:
		...
		e8 F			# call function

HEX2 automatically fills in the correct 4-byte relative address.

Unfortunately, I still have to use HEX1 to implement the first version
of HEX2, so, to keep the implementation simple, I only allow
one-character labels and backwards references to them. And there is no
error detection for an undefined label.

The syntax of HEX2 is ([0-9a-f]{2}|\.L|L)*, where L is any character
above 32 apart from [0-9a-f].

The first implementation of HEX2 is hex2a.he. If you compare the ELF
headers in hex1.he and hex2a.he you will notice that I have changed
p_flags. This is to make the program writable as well as executable.
Normal programs consist of several sections, in particular a text
section, which contains the program itself, and a data section. The
text section is executable, but not writable, and the data section is
writable, but not executable. In hex1.he I did not need to write any
data to memory, so I only had a text section. In hex2a.he I need to
write data to memory, but I can not be bothered with separate
sections, so I use a single section which is both executable and
writable.

There are only two pieces of data: "pos" is a 32-bit counter to keep
track of our location as we output the binary, and "label" is a
259-byte table to record the values of the labels. Why 259 bytes? This
is because I forgot to multiply by 4. I should have used a table of
256 4-byte values, one for each possible one-character label, and
calculated the address as (table + char * 4). Since I forgot to
multiply by 4, I only need 259 bytes for my table, and I have to avoid
using labels that are close to one another: if I use 'm', then I
cannot use 'j', 'k', 'l', 'n', 'o' or 'p'. It would be easy to fix
this bug immediately, but it is even easier to work around it for now
and fix it a bit later.

We can "compile" hex2a.he using hex1:

	./hex1 < hex2a.he > hex2a && chmod +x hex2a

Since HEX2 is a superset of HEX1, hex2a.he can also compile itself:

	./hex2a < hex2a.he | diff - hex2a

To test the new facility, I made hex2b.he from hex2a.he by replacing
numerical addresses by symbolic ones wherever possible. Compiling
hex2b.he gives the same binary as hex2a.he:

	./hex2a < hex2b.he | diff - hex2a

In hex2c.he I fix the "multiply by 4" bug. It is easier to fix the bug
now that I can use labels and do not have to manually modify relative
addresses. In hex2c.he I also replace some 1-byte relative addresses
by 4-byte relative addresses, so that I can use labels, and I have
inserted blocks of NOPs at the end of file to make the precise value
of e_entry less critical.

We can compile hex2c.he using hex2a/hex2b or using itself:

	./hex2a < hex2c.he > hex2c && chmod +x hex2c
	./hex2c < hex2c.he | diff - hex2c


HEX3: four-character labels and a lot of calls
----------------------------------------------

One-character labels are a bit restrictive, so let us implement
four-character labels. If labels have exactly four characters we can
store them neatly in 32-bit words!

The syntax of HEX3 is /([0-9a-f]{2}|:....|\.....)*/, and now we will
introduce some very basic error detection. The compiler can report
three different kins of error, which is will do using its exit code:

 exit code 1: syntax error
 exit code 2: redefined label
 exit code 3: undefined label

Since it is a single-pass compiler, only backwards references to
labels are permitted.

The first implementation of HEX3 was hex3a.he, written in HEX2:

	./hex2c < hex3a.he > hex3a && chmod +x hex3a

It is not possible to compile hex3a.he with hex3a itself, as HEX3 is
not compatible with HEX2.

I created hex3a.he by making successive small changes to hex2c.he. The
system call brk() is used to get memory for an arbitrarily large
symbol table. Absolute references to data are avoided by putting a
function (.z / get_p) in front of the static data area that returns
the address of the following data.

Having created hex3a.he, I started work on hex3b.he, an implementation
of HEX3 written in HEX3. Initially hex3b.he was just hex3a.he
translated to the new syntax, but I then gradually rewrote it to make
much greater use of labels and functions. In the final version, after
a certain point in the file, everything is done using only these
instruction groups:

 - push a constant onto the stack:  68 XX XX XX XX
 - call a named function:           e8 .LABEL
 - unconditional jump:              e9 .LABEL
 - conditional branch:              58 85 c0 0f 85 .LABEL
 - push an address onto the stack:  68 .LABEL e8 .reab

The last instruction group consists of a push instruction followed by
a call instruction, but the two may not be separated: the function
"reab" converts the relative address on the stack to an absolute
address by adding its return address and subtracting 5.

We can compile hex3b.he using hex3a or itself:

	./hex3a < hex3b.he > hex3b && chmod +x hex3b
	./hex3b < hex3b.he | diff - hex3b


HEX4: any-length labels and implicit calls
------------------------------------------

When implementing hex3b.he we found that it is possible to define all
complex functions in terms of simpler functions by using a tiny subset
of all the possible machine instructions: branch, call, jump and a few
others.

In HEX4 we use an even smaller set of instructions and generate those
instructions implicitly.

In HEX4 there are four types of token:

 - in-line code or data ('58, '59)
 - define label (:data, :loop, :func)
 - instruction: push constant (10, 42)
 - instruction: push label address (&func, &loop)
 - instruction: call label address (+, -, jump, branch, func)

Tokens must be separated by white space and the type of token is
recognised from the first character. Labels can have any length - but
we implement them with a simple hash function, so there is a risk of
spurious redefined label errors.

The jump and branch instruction groups from HEX3 are implemented by
functions. A "push label address" instruction must always be followed
immediately by a call to one of the functions that can understand a
relative address: address, branch, jump. The "address" function
(formally "reab") converts the relative address to an absolute
address, which can be stored and used later.

The predefined functions are:

Stack manipulation: drop dup rot pick swap
Arithmetic: + - * / % << >> log
Comparisons: < <= == != >= >
Bitwise logic: & | ^ ~
Memory access: @ = c@ c=
Flow of control, using immediate relative address: branch call
Flow of control, using stored absolute address: call
Address conversion: address
Array support: [] []& []= c[] c[]& c[]=
Access of arguments and variables: arg arg& arg= var var& var=
Function support: enter vars xreturnx xreturn0 xreturn1
Dynamic memory: wsize sbrk / malloc free realloc
System calls: exit in out

- All operations take arguments and return results to the stack.

- Comparisons return 0 or 1.

- All data are words, except for c@, c=, c[], c[]&, c[]=, which
operate on bytes.

- Any user-defined function must start with "enter"; "vars" can be
used straight after "enter" to reserve space for N local variables.

- To return from a function, use one of the "return" functions. "X Y
xreturnx" means return Y values from a function that took X arguments.
The most common cases are Y=0 and Y=1, so "X xreturn0" and "X
xreturn1" are provided.

- Like in C, addresses are byte addresses, so we have to multiply by
wsize when allocating memory with sbrk or malloc.

- "x y []" is equivalent to "x y wsize * + @"

- As always, no forward references to labels are allowed.

As with HEX3 there are two implementations of HEX4. The first one,
hex4a.he, is written in HEX3. The second one, hex4b.he, is written in
HEX4.

	./hex3b < hex4a.he > hex4a && chmod +x hex4a
	./hex4a < hex4b.he > hex4b && chmod +x hex4b
	./hex4b < hex4b.he | diff - hex4b


HEX5: structured programming, at last
-------------------------------------

HEX5 is more like a real structured programming language. There are no
longer any labels; instead there are loops and if...(else)...fi
structures. The syntax of HEX5 can no longer be described with a
regular expression; instead we need a context-free grammar:

	program = (hexitem | global | procedure)*
	hexitem = hexbyte |  "_def" symbol
	hexbyte = /'[0-9a-f][0-9a-f]/
	global = "var" symbol | "string" symbol string_literal
	string_literal = /"([^"]|\\.)*"/
	procedure = "def" args name "{" vars body "}"
	args = symbol*
	name = symbol
	vars = "var" symbol
	body = (number | word | loop | jump | if)*
	number = /[0-9]+/
	word = symbol
	loop = "{" body "}"
	jump = "break" | "continue" | "until" | "while"
	if = "if" body "fi" | "if" body "else" body "fi"
	symbol = /.+/ except ...

Lexical rules:

	comment = /#[^\n]*\n?/
	space = /\s/
	string_literal = /"([^"]|\\.)*"/
	token = /\S+/

The first implementation of HEX5, written in HEX4, is hex5a.he. This
is only a very partial implementation, as it would be quite tedious to
implement all of HEX5 in HEX4. In particular, there are not yet any
named variables or arguments; access to a function's arguments and
local variables is done using the functions from HEX4. Global
variables are implemented with a cunning hack:

	./hex4b < hex5a.he > hex5a && chmod +x hex5a

Next came hex5b.he, which can compile itself, as it is written in a
subset of HEX5. In hex5b.he I implemented named arguments and
variables:

	./hex5a < hex5b.he > hex5b && chmod +x hex5b
	./hex5b < hex5b.he | diff - hex5b

Then I wanted to start using those features for implementing further
features, so I switched to developing hex5c.he, in which I implemented
string constants, "while", "until", "return0" and "return1":

	./hex5b < hex5c.he > hex5c && chmod +x hex5c


BCC: a real language
--------------------

All that is needed to turn HEX5 into a tiny structured programming
language is to separate off the first part of the source, where there
is in-line machine code and the "predefined" and library functions are
implemented, into a separate header file. At this point I removed
references to "hex" and called the two files "header.bc" and "bcc.bc".
These two files are concatenated for compilation:

	cat header.bc bcc.bc | ./hex5c > bcc && chmod +x bcc

Now bcc can compile itself, of course:

	cat header.bc bcc.bc | ./bcc > bcc2 && chmod +x bcc2
	mv bcc2 bcc
	cat header.bc bcc.bc | ./bcc | diff - bcc

Note that the bcc produced by hex5 might not be identical to the bcc
produced by bcc itself, as I might make some minor improvements to the
code generated by bcc. But the main improvements to be introduced in
bcc are:

 - proper error messages to stderr instead of just exit codes
 - report undefined symbols
 - a dynamic buffer for tokens so there is no limit to their length


What next?
----------

Here are some things that one might want to do with BCC for one's
education and entertainment:

 - port it to a different operating system or architecture
   (you could compile to Java byte code, for example)

 - think of a neater way of handling return values from functions

 - implement a compile-time check for stack underflow

 - include a non-bogus implementation of malloc, realloc, free

 - use an RB-tree for the symbol table so that the compiler does not
   take time quadratic in the number of symbols

 - think up a way of using BCC to bootstrap GCC ...


Edmund GRIMLEY EVANS <[email protected]>, March 2001
Revised: March 2002