Want to Write a Compiler? Read These Two Papers (2008)

Because parsing is a field of little active research interest where most of the work happened more than 20 years ago, there are a lot of techniques from the 70s, 80s, and 90s that are relatively unknown.

Full context-free grammar are supported by "generalised parsing". The older stuff is GLR by Tomita, Early parsing, the CYK algorithm. The newer stuff based on Tomita is the particular rabbit hole I stuck with for a while. I read about SGLR which eliminates lexers, GLL which is GLR but based on the LL algorithm. The people who do GLL research also did improvements on SGLR with improved speed on right-nulled grammars. Then there is the SGLR improvements with disambiguation filters, automatic derivation of error recovery with island grammars, etc. The disambiguation filters include a kind of negation, making the current implementation of SGLR for SDF capable to parsing Boolean Grammars, which are a superset of context-free grammars.

Anyway, there's more than context-free grammars. Definitely look into data-dependant grammars! It's able to define a lot of interesting things, like network protocol formats where you parse the length of the payload, then based on that length you know how much to interpret as the payload before you read the footer of the message. And you write all of that in a more declarative way and get a nice parser generated from it.

There is so much more, but I think I should to stop now :)

Parser combinators are a relatively modern topic in parsing. First research into the topic was made in the late 1980s, but parser combinators became popular after Parsec [0], a practical implementation of parser combinators in Haskell. These ideas have been borrowed to many different implementations in different languages since then.

[0] Daan Leijen: "Parsec, a fast combinator parser", 2001 http://research.microsoft.com/en-us/um/people/daan/download/...

Earlier you wrote that "And if you worry about performance, your compiler can fuse passes together in many cases."

What kind of fusion do you use in your approach?

In the last paragraph of Keep's thesis, he mentions pass fusion, citing Wadler's 1988 work on deforestation. Keep does not, however, give a working implementation.

I know of no-one doing nanopass fusion, but I'd love to be corrected.

Yes, but as Wirth showed already in the 70's, you don't even need an IR in order to do this, much less separate passes.

For a highly optimizing compiler like yours the complexity might have been unavoidable anyway, though (a lot of the simplicity of Wirth's compilers comes from a long held insistence that no optimization could be added to the compiler unless it sped up the compilation of the compiler itself - in other words, it needed to be simple enough and cheap enough to apply to the compiler source code to pay for itself... needless to say this implicitly means that most Wirth-compilers omit a lot of optimizations that are usually included elsewhere, though some of his students did implement some impressive "unofficial" optimizing variations of his compilers that were also blazing fast)

As compilers go, I don't think gcc has been a good example of maintainable software for a very long time, if ever.

While that is true of most modern compilers, do consider that there's the whole Wirth school of compilers that don't use an AST at all but generate machine code directly during parsing.

> For a human it is much easier to structure such a rewrite as a sequence of very trivial changes.

I'm not convinced, as I've written elsewhere, because while the changes may be trivial, you need to keep track of what a program is expected to look like in between each stage, and that becomes harder the more stages you introduce. E.g. my forever-in-progress Ruby compiler has a stage where it makes closures explicit: It allocates an environment to store variables in and rewrites variable accesses accordingly. For following stages the language I'm working on is different: I can no longer use closures.

The more stages you have, the more language dialects you need to manage to mentally separate when working on the stages. And if you decide you need to reorder stages, you often have painful work to adapt the rewrites to their new dialects.

The end result looks very simple. But try to make changes and it's not necessarily nearly as simple.

See, the problem is, for the "sufficiently smart" compiler to easily realize this is possible, the passes need to be purely functional. It turns out, most programmers struggle with understanding functional programming...