Sunday, August 10, 2014

Building a Compiler, Briefly

During the last meeting of the Toronto Haskell group, we briefly discussed the question of how to build a compiler, and in particular the problem that building a real one is a daunting task.

I've done a bit of digging into various approaches and guides. There are a lot of them, because every respectable CS curriculum needs a compilers course.

The one I find most intriguing is by Niklaus Wirth, the guy behind Pascal and Modula-2. In his "Compiler Construction" PDF, he guides you through building a compiler as a series of exercises in a bit over a hundred pages. Given that other texts run well past 500 pages, a tractable treatment is quite a relief. I get the impression you could work through the guide in 2-3 of weeks full time or perhaps a quarter as a side project.


That said, Wirth does make some simplifications for pedagogical purposes. The source language is Oberon-0, which is a pared-down version of Oberon, so almost but not quite a real language. The target architecture is a simplified RISC instruction set, with an interpreter that fits in a page. You build the compiler from scratch, rather than using tooling like ANTRL, parsec, or LLVM, which you'd presumably leverage in an actual implementation. And the treatment of code optimization is brief. So, choices were definitely made.

But all in all it is possible to make building a simple compiler the work of a couple of weeks rather than a months-long slog.

No comments:

Post a Comment