9 ms·
Want to Write a Compiler? Read These Two Papers (2008)
- fuzzieozzie 11y agoYou want to be paid to write a compiler? Want to learn some techniques not yet covered in the literature? Take a look at http://www.compilerworks.com/dev.html http://www.compilerworks.com/dev.html
- d0m 11y agoI agree. I remember my compiler class where we went through the whole Dragon book and we had a lot of theoretical knowledge, but we were disappointed because we practically couldn't build a compiler. We went in too much detail too fast without having a good understanding and practical examples with compilers.
- santaclaus 11y ago> the whole Dragon book I learned compilers from Al Aho, and believe me, the class was no better in person. Mostly in-person waxing poetic about his time at Bell Labs...
- dgacmu 11y agoDinner with Al Aho was one of the highlights of when I visited Columbia a while ago. He's simply an awesome person. And he's done some fantastic work - Aho-Corasick is a great algorithm. Alas, the Dragon Book was one of the low points of my undergraduate education, though I had a great teacher who pulled out a terrifically fun class despite the book. (Thanks, +Wilson Hsieh.) In fairness, though -- or more an admission of how wrong we can be about things like this -- I subscribed to the "parsing is boring and solved" belief until Bryan Ford's Packrat Parsing work made me realize that it had just gotten stuck at a traffic light for a few decades.
- mdcox 11y agoVeering a bit offtopic, but does anyone have any pointers to important recent work on parsing? There are alot of papers out there and I guess I don't know how to sift through them. I've heard the "parsing is solved" line before, but so much of my time is spent doing some type of parsing that even incremental improvements are extremely interesting.
- cwzwarich 11y agoI can probably help if you can narrow things down a bit. Are you parsing deterministic languages (e.g. for programming languages), general context-free languages, binary file formats, or something else? 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.
- mdcox 11y agoI'm most interested in deterministic languages. Non-deterministic context-free languages would be extremely interesting as well but more out of curiosity than an applicable need. Thanks!
- vidarh 11y agoFor deterministic languages, hand written recursive descent is usually the choice even today because of simplicity and ease of error reporting. There are exceptions, but relatively few production compilers uses anything else, and most of the innovations in parsing provides relatively little value in this space because they tend to be focused on better expressing complex languages rather than provide improved ways of expressing / capturing errors, and it's the latter that would provide most benefit for deterministic languages.
- sklogic 11y agoPEG (Packrat) is hot now.
- 11y ago
- YZF 11y agoIn my compiler class we also used the Dragon book and we did write a compiler for a C like language... I don't think we covered the book in its entirety though but sounds like that was a better mix. I felt quite capable of writing simple compilers after I finished the course...
- ChuckMcM 11y agoInteresting, I took compilers where the Dragon book was the standard text book, we implemented a PASCAL like language (which compiled for the DEC10 as a target) and it was one of the really transformative classes I had taken. It brought together algorithms and data structures into a curriculum where they joined up to convert text into executable code. Really one of those moments of sudden clarity for me.
- ww520 11y agoI went through a undergrad compiler class with the Dragon book, not the whole thing though, just enough chapters to build a compiler. We did build a full fledged compiler for an OO language, with all the parts of a compiler all the way to code generating assembly. It's kind of fast pace with too many stuff crammed into a class. Some theoretical topics were kind of fuzzy at the time. Still it was one of the best classes I have ever attended. Later on when I re-read the book on my own pace, I thought the book was the best thing since slice bread. Got a much better understanding of the theories behind the compiler topics. A lot of the things I learned I can still apply to this day.
- vidarh 11y agoI loved the Dragon book, but I agree not a practical book. I probably loved it because at the time I'd already been experimenting with compiler writing for 5-6 years, and it gave me a theoretical grounding for a lot of stuff I'd been doing or doing subtly "wrong". I think it - and similar books - should be banished from first compiler classes, and instead be used later. Much more practical books like Wirth's that actually walk you through writing a compiler would be much better for most beginners.
- Animats 11y agoI was amused by "The authors promote using dozens or hundreds of compiler passes, each being as simple as possible." That's kind of a desperation move. There was a COBOL compiler for the IBM 1401 with about 79 passes.[1] They only had 4K or so of memory, but they had fast tape drives, so each pass read the previous intermediate form, did some processing on it, and wrote out the next intermediate form. Except for the passes which did sorts. [1] http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/140x/C24-3146-3_1401_cobolOper.pdf http://bitsavers.informatik.uni-stuttgart.de/pdf/ibm/140x/C2...
- hawkice 11y agoNot a bad way of organizing code, though, at least for relative beginners like me. I'm sure there are more clever things to do, or things that aren't quite possible to do reasonably or efficiently with independent small passes, but I like the way it lets me chunk everything I want to do. So maybe it started because there wasn't any other option -- but pretty good advice in the context of the article.
- sklogic 11y agoThis is the only sane approach. Small passes are easy to write, easy to understand and easy to reason about. And if yoy worry about performance, your compiler can fuse passes together in many cases.
- vidarh 11y agoHave you tried this approach? If so I'm curious to hear about experiences. My own experience with far fewer stages is that while it becomes easy to understand what each stage does and how, it becomes hard to keep track of how each stage interact, as each intermediate output in effect becomes a language dialect of sorts. I'm still not decided on whether it's a net win or loss.
- bonobo3000 11y agoYou might be interested to know Scala's new compiler dotty takes the phase approach - there are 40-50 phases and logic for fusing phases together to work in one traversal. Check it out - a list of all the phases in the source! https://github.com/lampepfl/dotty/blob/master/src/dotty/tools/dotc/Compiler.scala#L38 https://github.com/lampepfl/dotty/blob/master/src/dotty/tool...
- cbsmith 11y agoI haven't read the Nanopass Framework paper, but... The idea of doing tons of compiler passes works well in a functional context, where functional separation i the preferred method of abstraction, and you can use composition to effectively transform all your passes into a single pass. However, actually doing that many passes seems like it is going to end badly. Even if you don't touch disk, you're doing mean things to the memory subsystem...
- pilingual 11y agoIts purpose is for education. It's a great course, and I wish Dybvig would create a Coursera.
- sklogic 11y agoIt is much more memory-efficient than thrashing a single graph over and over again. Rewriting and compacting trees is good for cache locality. Also, for the trivial rewrites (e.g., variable renaming) your compiler can safely choose to replace a cooying rewrite with a destructive update.
- cbsmith 11y ago> It is much more memory-efficient than thrashing a single graph over and over again. Rewriting and compacting trees is good for cache locality. To be clear: if you are thrashing a single graph over-and-over again, you are doing many passes. Rewriting and compacting trees is just a way to make the multiple passes a bit less painful.
- sklogic 11y ago> if you are thrashing a single graph over-and-over again, you are doing many passes. A single "pass" can be thrashing a graph many times too, think of the things like instcombine (in LLVM parlance) or ADCE. Essentially, compilation is rewriting of a source AST into the target machine code. It is up to you how to structure this rewrite, but the amount of work to be done remains the same. For a human it is much easier to structure such a rewrite as a sequence of very trivial changes. And a "sufficiently smart" compiler must realise that it can be done in less steps.
- deleted 11y ago[deleted]
- journeeman 11y ago'Compiler Construction' by Niklaus Wirth[1] is a pretty good book too. It's got the hands-on feel of Crenshaw's book with a quick but, not too superficial, introduction to theory. The book is little more than 100 pages long. The compiler is written in Oberon however, which is also the source language (actually the source language is Oberon-0, a subset) but, Oberon is super simple and can be learned on the go. [1] https://www.inf.ethz.ch/personal/wirth/CompilerConstruction/index.html https://www.inf.ethz.ch/personal/wirth/CompilerConstruction/...
- eterps 11y agoOberon was also a major inspiration for the Go language.
- gnuvince 11y agoI wish someone would take that content and give it proper typesetting; the content is quite good and accessible, but the presentation makes reading quite unpleasant.
- pjmlp 11y agoThen one can jump into "Project Oberon" and see how to build a graphical workstation OS in a GC enabled systems programming language. Also accessible from that site.
- fanf2 11y agoI quite like "understanding and writing compilers" by Richard Bornat - written in the 1970s using BCPL as the implementation language, so rather old-fashioned, but it gives a friendly gentle overview of how to do it, without excessive quantities of parsing theory.
- fanf2 11y agoI quite like "understanding and writing compilers" by Richard Bornat - written in the 1970s using BCPL as the implementation language, so rather old-fashioned, but it gives a friendly gentle overview of how to do it, without excessive quantities of parsing theory.
- toolslive 11y ago"Implementing functional languages: a tutorial" Simon Peyton Jones http://research.microsoft.com/en-us/um/people/simonpj/Papers/pj-lester-book/ http://research.microsoft.com/en-us/um/people/simonpj/Papers... Is very good and shows different strategies for the runtime.
- lmm 11y agoPost-2008 I'd really push http://www.hokstad.com/compiler http://www.hokstad.com/compiler . Writing a compiler in the same way you'd write an ordinary program, this was the first explanation where I actually understood the rationale for the choices being made.
- vidarh 11y agoThanks for the recommendation, though I'd give the caveat that I've been rambling all over the place, especially in the later parts. I also have lots of changes after the latest part that I need to write about... I'd really like to get a chance to take the time to retrospectively go over and tighten it up. The trouble with that is that it's easily 10 times+ as much effort to follow along with a project this way and write about each change as it is to cover the finished code (especially thorny issues such as how to avoid wasting too much time on bug fixes that may or may not have affected understanding of previous parts). Personally, while I'm very happy that people find my series useful, I'd recommend perhaps supplementing or starting with Niklaus Wirth's books or Crenshaws "Let's write a compiler" (one of the ones recommended in the linked artile) for something much more focused. I feel the angles are sufficiently different that it's worth it. And Wirth is my big hero when it comes to language and compiler construction. While the other suggestion in the article is well worth a read, I'd give one caveat: Lots of passes is hard to keep mental track of. My compiler sort-of does something similar in applying multiple transformation stages to the AST, and I'm mulling collapsing it into fewer stages rather than more because I feel it's getting more complex than necessary. You can work around some of the debugging complexity by outputting each stage to a suitable format so you can test each transformation individually, but it's still hard to keep track of exactly what each stage expects and delivers.
- lmm 11y ago> You can work around some of the debugging complexity by outputting each stage to a suitable format so you can test each transformation individually, but it's still hard to keep track of exactly what each stage expects and delivers. Honestly this sounds like a good case for a type system - which of course isn't available in ruby.
- userbinator 11y agoThere's an x86 version of Crenshaw's excellent tutorial here: http://www.pp4s.co.uk/main/tu-trans-comp-jc-intro.html http://www.pp4s.co.uk/main/tu-trans-comp-jc-intro.html I'd definitely recommend it highly; the only way it could be better is if it arrived at a compiler that could compile itself. Another article which I think everyone attempting to write a compiler should read is https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm - how to simply and efficiently parse expressions.
- bonobo3000 11y agoIf you're totally new to this, Peter Norvigs guide to a scheme interpreter in Python[1][2] is the best! Its short and sweet and gave me enough of an idea of the basic parts to start piecing stuff together. [1] http://norvig.com/lispy.html http://norvig.com/lispy.html [2] http://norvig.com/lispy2.html http://norvig.com/lispy2.html
- kybernetyk 11y ago>Now imagine that it's more than just a poor choice, but that all the books on programming are at written at that level. Hmm, I personally found the "Dragon Book" very accessible. And I'm someone without formal CS education.
- PaulHoule 11y agoI like the nanopass concept, particularly I am applying it to domain specific languages. It is not necessarily so inefficient if it is optimized. For instance, data indexing and methods such as RETE networks can make the cost of running an irrelevant pass close to nothing.
- emmanueloga_ 11y agoOn a related subject, two good resources to learn how to write interpreters are [1] and [2]. The nice thing about approaching programming language implementation with Scheme is that the whole parsing subject is unneeded (the interpreters work by manipulating S-expressions directly), or can at least be delayed until later. 1: http://cs.brown.edu/courses/cs173/2012/ http://cs.brown.edu/courses/cs173/2012/ 2: http://www.eopl3.com/ http://www.eopl3.com/