The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

How is a new compiler compiled?

Sorry for the newbie question from someone who doesn't have a CS degree, but could someone tell me how people manage to compile a compiler for a new language?

For that matter, how did things start for the very first compiler way back when? Thx.
Thursday, December 23, 2004
There's nothing to say that your compiler has to be written in the laguage it compiles. I think the language of choice for writing such things tends to be C. I imagine the first one was written using assembly langauge.

Thursday, December 23, 2004
It's called compiler bootstrapping - here's an example of how to do it without using another language:

This process can also be used to insert backdoors into any software then compiled with the compiler, even without the backdoor being left in the source code - see here for an example:
r1ch Send private email
Thursday, December 23, 2004
Of course, if you really really want to understand this stuff, and you can't be bothered with all that programming nonsense, then you'll want to get a copy of Kripke's Naming and Necessity...just remember to keep your connotations and denotations in order folks!
Richard Rodger Send private email
Thursday, December 23, 2004
BCPL was a predecessor to C that was essentially designed to aid in this process.

BCPL was written in BCPL, and the compiler made several passes over the code. Pass 1 produced a parse tree. Pass 2 produced a "psuedo-assembler" output. Pass 3 converted this to local assembler. Pass 4 is then the assembly of this code.

The way you'd get to a new machine would be to write a converter from the psuedo assembler to assembly language for the new machine, then write an assembler for the target machine (a much easier task than a compiler) on the machine you already have (because you have development tools for that machine) and then you could produce binaries for the machine.

If your machine already had an assembler, you could move the assembly source onto the target machine and build it, which was probably simpler than trying to move binaries about in those days. And then you have a working BCPL compiler, which can compile the psuedo->real assembly converter and the rest of your development environment.

In cases where you're not moving machine, you tend to write the first compiler in C, and then get that into shape. It'll get to a point where you can write a compiler for the language in the language itself, which you compile through the C version of the compiler. And then you've got the language's compiler written in itself.

Some languages never get to this point, because they're not powerful enough to write their own compiler. The hacker terminology for these is "My Favourite Toy Language" on the presumption that anything that you can't write a compiler with is a toy.
Katie Lucas
Thursday, December 23, 2004
The first compiler for pascal was written on paper by Wirth, who then ran it by hand on itself, and then manually entered the resulting machine code.  By dint of attention to detail, he then had a working pascal compiler.

I don't have that kind of patience, myself.
Aaron F Stanton Send private email
Thursday, December 23, 2004
Thx everyone :-)
Thursday, December 23, 2004
Aaron, amazing story. Do you have a link for that?
Alexandru Pojoga Send private email
Thursday, December 23, 2004

In 1968, after the working group for Algol, Wirth decided to design a new
language in the tradition of Algol 60 and Algol W that met his goals for
including advanced data types, structuring of data types, and I/O for the
language. It was called Pascal (after Blaise Pascal, 15th century scientist
and inventor of early mathematical calculating machine).

In 1969, a bootstrap compiler using Fortran as the implementation language
was completed. Although the compiler was written in Fortran, the idea was
to rewrite the compiler in Pascal itself, and so bootstrap the compiler.
Wirth called that project unsucessful, and instead, a Pascal compiler
was written in a subset of the full Pascal language and translated by hand
to a language called SCALLOP on the CDC 6000 computer, and thus bootstrapped.
Tom H
Thursday, December 23, 2004
There's a unix program called YACC which takes language grammars and outputs compilers. You have to know C, but it might help?
Steve Cooper Send private email
Friday, December 24, 2004
*The* book to buy is

Compilers - Principles, Techniques and Tools


Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman

This is not a book to get if you are just curious - it is quite heavy going.

I think there's a chapter with a worked example of the process Katie described.
Justin Send private email
Friday, December 24, 2004
I've found that the Gentle Compiler Construction System is quite enjoyable to use, and not too hard.

No, I'm not affiliated ;)

Only drawback is it's older-style C code output. I wish they'd update it so that more modern C++ compilers don't issue so many warnings.
Jonathan Send private email
Friday, December 24, 2004
Don't forget cross-compilers - the compiler runs under one type of CPU and emits code for another.

We don't see that much today except for the embedded systems world, where the low horsepower of the CPUs doesn't support a native compiler.

Monday, December 27, 2004
"after Blaise Pascal, 15th century scientist
and inventor of early mathematical calculating machine"

Seventeenth-century. His dates are 1623-62. But did he win his wager?
Graham Asher Send private email
Wednesday, January 19, 2005

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz