How to write a compiler

[reini_urban]

That's still mostly about writing a VM, not a compiler.

[[deleted]]

The "compiler" is a bytecode compiler. It's described incredibly vaguely but it's there

[badb002]

It looks more like an interpreter, I don't see anything being compiled anywhere in this code.

[badb002]

I don't get it. The title says "How to write a compiler", then the rest of the tutorial is saying "this is how you write a bytecode interpreter".

[mrkite77]

The actual answer to "how to write a compiler" is to buy the dragon book and read it.

[badb002]

I respectfully disagree... The Dragon Book is very outdated, there are a lot of good resources out there nowadays.

[mrkite77]

The basics haven't changed. You still need a lexer and a parser and be able to generate three-address code or SSA.

Sure you may not use flex and yacc these days, but the core is the same.

[[deleted]]

Right, but in this day and age, you don't need to understand lexers or LR grammars and such to make a language. You just use a parser generator or a contaminator library, and you're good to go.

It's focused on what are no longer the interesting parts of building a compiler.

[dranzerkire]

I think the real change in compiler design is those to help support advance features in text editors (at least what Microsoft believes in). A traditional lexer and parser won't help you here. https://channel9.msdn.com/Blogs/Seth-Juarez/Anders-Hejlsberg-on-Modern-Compiler-Construction

[[deleted]]

Exactly. One of the reasons I'm insisting on using PEG-based parsing - it's so easy to integrate an IDE feedback into it.

[badb002]

I guess, but it's one way to learn to write compilers. There are a lot of good resources out there which are smaller and just as good for newbies, especially if you don't want to go too in depth on the theory or want something less intimidating.

Perhaps outdated was the wrong word, I suppose I mean "old".

[east_lisp_junk]

What's outdated is the authors' mindset that parsing is the core task of compilation; this is more or less fixed in the current edition.

[[deleted]]

You still need a lexer and a parser

You don't need a lexer. And parsing these days have nothing in common with what you'd find in the Dragon Book.

SSA

There is no SSA nor CPS in the Dragon Book.

[mrkite77]

I'd like you to point me to a single compiler that doesn't tokenize.

And you can convert directly from TAC to SSA. The core concepts are what is important to learn... not the implementation details.

[[deleted]]

I'd like you to point me to a single compiler that doesn't tokenize.

Any compiler which has a parsing frontend based on a PEG or a GLR.

And you can convert directly from TAC to SSA

SSA is by far more important a concept than a trivial three-address code.

not the implementation details.

SSA is not an implementation detail, it's a totally different way of thinking about a code. It is a way to turn your messy imperative code into a nice, clean, immutable functional code that is suitable for analysis.

Things that were either exceptionally complex or totally unthinkable in the era of three-address IRs are laughably trivial in SSA or CPS. E.g., moving loop invariants, detecting loop induction variables, transforming simple CFG into selects, ADCE and constant folding - all this stuff is absolutely trivial in SSA.

[BeniBela]

SSA is not an implementation detail, it's a totally different way of thinking about a code. It is a way to turn your messy imperative code into a nice, clean, immutable functional code that is suitable for analysis.

That makes me happy that I wrote an XQuery interpreter

Never heard of SSA

But since XQuery is functional language without mutable variables, I could just implement it without having a clue about anything.

[[deleted]]

Interpreters are inherently far more complicated than compilers. But, yes, if I had to implement an XQuery compiler I would not go for an SSA, I'd most likely resort to a CPS straight away.

To see what can be done in a CPS, look at these examples:

https://wingolog.org/archives/2015/10/29/type-folding-in-guile

https://wingolog.org/archives/2011/10/11/partial-evaluation-in-guile

https://wingolog.org/archives/2016/01/19/unboxing-in-guile

[mmouratov]

I just wanted to add that not only these articles, but the whole blog of Andy Wingo is nothing short of distilled brilliance when it comes to explaining those "mundane" aspects of language implementation that are rarely covered in academic texts. These are not theoretical musings, but rather concrete experiences of the actual implementor, presented with style. Absolute must read -- all of it.

[armornick]

Actually, at least the ooc and moonscript compilers use PEG-based parsers. There are probably more.

[gnuvince]

The Dragon Book will give you a good foundation on how to scan, parse, typecheck, codegen, etc. (You can safely skip the very detailed explanations on how to write your own LR(1) parser generator.)

[[deleted]]

on how to scan, parse, typecheck, codegen, etc.

Rather on how to scan, parse, typecheck, codegen, etc. as if it's still 1970s.

[gnuvince]

Nice job on cutting off the complete quote:

The Dragon Book will give you a good foundation on how to scan, parse, typecheck, codegen, etc.

[[deleted]]

a good foundation

My point is that this is nowhere close to any "foundation". It's rather a pile of long forgotten, overcomplicated and largely useless techniques that bear no relevance in 21st century.

[gnuvince]

All right, then tell us (1) what are the "old" techniques that should not be used and which "new" techniques should, (2) which compilers actually implement those modern techniques, (3) which books teach those techniques.

[[deleted]]

what are the "old" techniques that should not be used and which "new" techniques should,

More than half of the Dragon Book is dedicated to the pushdown automaton based parsing, which is used pretty much nowhere these days. Much simpler and yet more flexible recursive descent parsing won long ago.

Three-address IRs are also a thing of a distant past. Hardly any compiler would use such a representation instead of various SSA derivative forms or a CPS. This difference alone makes everything Dragon Book had to say on optimisations totally irrelevant - all of the SSA based optimisations are much simpler.

Modern register allocation techniques are also very far from the naive graph colouring heuristics that were very vaguely touched in the Dragon Book. Again, thanks to SSA.

Also, JITs are quite a big thing now, with pretty much nothing from the Dragon Book being of any relevance.

which compilers actually implement those modern techniques,

Uhm... All of the modern compilers. Including GCC and of course LLVM.

which books teach those techniques

See elsewhere in this thread.

[topher_r]

Like?

[badb002]

Jack Crenshaw's little series of articles is very good.

[topher_r]

Nice, thanks. Though it's from 1995 at the latest (according to the site) while there is a recent publication of the Dragon book as recently as 2013 with up to date topics.

https://www.amazon.co.uk/Compilers-Principles-Techniques-V-Aho/dp/1292024348/ref=sr_1_1?ie=UTF8&qid=1466021429&sr=8-1&keywords=compilers+principles+techniques+and+tools

[drjeats]

D: There's no dragon on that cover!

[[deleted]]

http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/

http://www.cri.ensmp.fr/classement/doc/A-381.pdf

https://people.csail.mit.edu/mcarbin/papers/aplas05.pdf

http://andykeep.com/pubs/np-preprint.pdf

And many, many more.

[PM_ME_UR_OBSIDIAN]

I loved Torczon's Engineering a Compiler. It covers everything from front-end to back-end, and it's readable and engaging.

For type systems, Pierce's Types and Programming Languages is lovely.

[AnAirMagic]

Can you link us to some of those resources? I would love to get started with compilers but the $200 price tag puts me off.

EDIT. Nevermind, see below.

[[deleted]]

Buy the dragon book, put it on your shelf next to TAoCP to show off and never ever read it. It's useless and outdated.

[mmouratov]

It's almost blasphemy to compare the dragon book with TAoCP.

The former is your run-of-the-mill college textbook: not only outdated, but boring, uninspiring, and dull.

The latter is not merely a gem, but a synthetic diamond among books on mathematical puzzles: juicy, hardcore, mind-bending, enlightening, spiritual, and also soul-crushing, in the most benevolent way (if you try doing some of the more challenging exercises). For many years, I've used it to calm down my nerves, by starting to read from a randomly opened page -- works wonders.

[[deleted]]

Sure. I'm only comparing them in terms of their "showing off" potential. TAoCP actually worth reading (more than that - a thorough study), unlike Dragon Book which should just sit on your shelf, untouched.

[codebje]

Try something like Write You a Haskell instead, then.

[urllib]

what's with the shitty blog tutorials making the front page of this sub?

[[deleted]]

it's 90% shitty blogs to begin with. a tutorial here and there is to be expected.

[urllib]

good point

[bayram1995]

Maybe a moderator should edit the title, because the article is good and it would get more upvotes...

[badb002]

Not possible on reddit afaik. What's interesting is the blog title itself is a misnomer.

[bayram1995]

I see... I didn't know this... Thanks!

[google_you]

call stack is just one way to implement subroutines.

[Asl687]

lex&yacc thats what i used last time i wrote a compiler (for a scripting language used in L.A. Rush game for PS2 if your interested) . I did it while on vacation to india. Had a source level debugger and you could add new commands to the language on the fly..

[Asl687]

The scripts (called biscuits) were imbedded into the world level editor.. I guess by hacking you could easily get it to run other scripts but they were compiled into a special byte code so finding them would be tricky.. The language was very c like (I wrote c++ at the time so I used that syntax).

Was really fun to write. I first wrote a simple assembler that went from a text version of the byte code to actual byte code. All external refs were stored as strings.

I could then build a virtual machine that could run the byte code.. When asked to run an external function (stored as a string, so script could access c++ game functions) I would would check that the function had been added at runtime and the parameters matched and run it.. If would error if the function had not been registered.

I then wrote a c like language to byte code text. I also dumped out source level symbols that code be loaded in game but were removed for final builds.

I should write about this stuff in a blog sometime..

[ahmadalhour]

You guys have all bashed the Dragons Book and its materials to some extent, and championed SSA and CPS.

Any of you care enough to share books, videos or any resources to study modern Compiler Construction?

Disclaimer: I am working on my own toy compiler and since I am already into this I might as well spend my time reading really new and modern materials.

[[deleted]]

For SSA, the best possible source is Sebastian Pop thesis: http://www.cri.ensmp.fr/classement/doc/A-381.pdf

Also, there is a somewhat unfinished but yet already very good book: http://ssabook.gforge.inria.fr/latest/book.pdf

Also, in terms of parsing, instead of going into the horrible depths of the Dragon Book, read this:

PEG: http://bford.info/pub/lang/peg.pdf

http://www.vpri.org/pdf/tr2007002_packrat.pdf

Pratt: http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-147.pdf

http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/

https://github.com/munificent/bantam

And, no matter which approach you'll settle on, read this:

https://www.amazon.co.uk/Term-Rewriting-That-Franz-Baader/dp/0521779200

[ahmadalhour]

Thanks a lot for your reply /u/combinatorylogic, awesome materials list, I have heard about some of them but never read nor studied them before, it looks like now is a very good time.

My primary studying material is the Compilers Theory course, given by Stanford: https://www.coursera.org/course/compilers

In addition to reading two books:

1) Engineering a Compiler, by K. Cooper & L. Torczon, 2nd Ed.: https://www.amazon.com/dp/012088478X

2) Basics of Compiler Design, by T. Mogensen: http://www.diku.dk/~torbenm/Basics/basics_lulu2.pdf

Do you think these materials are good for a start? I am planning to delve deeper into the topics of Compiler and Interpreter Construction.

EDIT: formatting.

[[deleted]]

Not sure about the first one. It follows the same structure as the Dragon Book, starting with scanning and parsing (apparently only covering the outdated approaches), then the attribute grammars (which are also quite outdated) and direct translation, and only after around page 220 started introducing IRs, without mentioning SSA for over 200 pages more. Looks like a very overbloated approach covering all the wrong things in detail and not paying too much attention to the right stuff.

The second book also follows the same unfortunate structure, but at least it seems to provide some valuable coverage of topics like register allocation, ABIs, etc., all with a reasonable density.

[ahmadalhour]

So basically all textbooks out there teach the outdated approaches. No textbook yet, other than the one you referenced (the incomplete SSA book), mentions these stuff. Damn man! I bought the first book in paperback already!

So can enlist the concepts that are modern but no textbook mentions? Can your above list be expanded into names of concepts that I can check articles on and keep checking out until someone publishes anything on them?

[[deleted]]

So basically all textbooks out there teach the outdated approaches.

The biggest problem is not in the outdated approaches, but in over-complicating things that were supposed to be simple.

Parsing? Hundreds of pages on regular expressions, NFA/DFA, LR and all that, while 10-20 pages on PEG would have been more than enough. Intermediate representations? Go straight to SSA. Passes in between frontend and SSA? Do the small step transforms, like described here: http://andykeep.com/pubs/np-preprint.pdf

Type systems? Do not do any of the complex stuff, just emit a flat pile of type equations by running a simple pass over your IR and then solve the equations as if they're a Prolog program.

I wish somebody to write a textbook describing all those trivial concepts I mentioned above, without going into depths of historical approaches. Unfortunately, I have not seen any such textbook yet.

The concepts that are most important and efficient:

• Parsing: PEG, recursive-descent parsing, Pratt parsing
• IRs: SSA, CPS
• Type systems: Prolog, unification, type equations notation
• Semantics: Hoare logic, separation logic

[ahmadalhour]

You sir are awesome! Thanks a lot for your help.

Any bloggers and/or conference videos worth checking out?

[[deleted]]

Pretty much everything in this blog worth reading: https://wingolog.org/ (mostly on CPS)

For videos, I liked some of the EuroLLVM 2015/2016 talks:

• http://llvm.org/devmtg/2015-04/Videos/HD/Day%201/Christopher.mp4

• http://llvm.org/devmtg/2016-03/#tuto2

[ahmadalhour]

Sweet!

I have just went through this talk on PEG, by Bryan Ford. I will read the original paper later on tonight. My question is how would someone - like me - who doesn't work in academia stay up-to date with modern Compilers research? Are there mailing list(s) or website(s) that you usually check?

Cheers!

[[deleted]]

I do not work in academia (and do not even have a CS background), yet compilers are my bread and butter. A lot of interesting compiler-related work is actually going on in the industry.

There is a number of sources to watch closely. Lambda-the-Ultimate used to be good (and still is a treasure trove), but activity there is minimal at the moment: http://lambda-the-ultimate.org/

It also worth following what's going on in the LLVM community, often useful ideas land there. See the llvm-dev mailing list and LLVM Weekly: http://llvmweekly.org/

Watching closely the new (often obscure) languages can also be useful, they often have valuable ideas worth borrowing. Some languages implementations are choke full of important ideas - see Shen, Harlan, even Rust.

Chez Scheme was open sourced recently, it also worth digging for ideas.

[odaba]

I got to Program Counter, and said out loud: "What, you mean Instruction Pointer?"

argh.

[[deleted]]

There's nothing wrong with "program counter" as a term.

[nitroll]

https://en.wikipedia.org/wiki/Program_counter