7 ms·

How to Write Your Own Compiler (2009)

• peter303 9y ago
  From its earliest year UNIX/Linux had utilities including lex and yacc that automate much of these fuctions. I tended to use awk to create powerful new command scripts.
  • chrisseaton 9y ago
    lex and yacc only automate one tiny part of the front-end of a compiler.
    • Xophmeister 9y ago
      Also, if you're learning to write your own compiler, you should, IMO, implement the lexer/parser (if you haven't done so before) to understand how they work.
• mtkd 9y ago
  One of the best resources I've seen on this is Capon and Jinks 'Compiler Engineering Using Pascal' (1988; ISBN 0-333-47155-5) if you can get hold of it http://www.cs.man.ac.uk/~pjj/book.html http://www.cs.man.ac.uk/~pjj/book.html
  • jonsen 9y ago
    Also Brinch Hansen on Pascal Compilers: https://www.amazon.com/Brinch-Hansen-Pascal-Compilers/dp/0130830984/ https://www.amazon.com/Brinch-Hansen-Pascal-Compilers/dp/013...
    • pjmlp 9y ago
      > 1 New from $3,000.00 Uau! I should take care of my old books.
      • robertbaruch 9y ago
        Haha, don't forget there has to be a seller AND a buyer for a price to hold true.
        • kazinator 9y ago
          There also has to be volume for a price to hold true. Even if someone buys that one for $3000, that doesn't mean it's the price if it only happens once.
    • soegaard 9y ago
      Brinch Hansen's book is a classic. It contains all necessary code for a self-compiling Pascal compiler (If I recall correctly).
  • skate22 9y ago
    I took "compiler techniques" at UMASS Amherst where we built a compiler for a subset of pascal. It was one of the hardest classes i took for my undergrad, but i learnt so much from it. I think building a compiler is somthing every cs major should do once, even if it's just for a subset of a language.
  • js2 9y ago
    Does no one refer to the dragon book anymore? https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...
    • neurotrace 9y ago
      The dragon book is very informative but is harder to parse (ha) than many other compiler books. People should definitely read it, it just might be hard to read as a "My First Compiler" book.
      • jcranberry 9y ago
        I started reading it a while ago when I wanted to properly learn compilers. I actually thought it was very readable.
        • kqr 9y ago
          I must agree. It may be that you and I lean more toward the theoretical side and want more of a "grounds up" material (a chapter about transforming regexes to state machines? seriously?) than a "here's what to do to get it done by next thursday" book.
          • jcranberry 9y ago
            LOL. Anyone attempting to build a compiler by next thursday is in for a rude awakening. In any case you're probably right, given that I like math and (so far) prefer algebra to analysis or applied mathematics.
    • Athas 9y ago
      While there are some good bits in the dragon book, some of its advice on the engineering of a compiler is pretty dated. For example, most of the parsing chapter(s) seem to have the notion that there is a single (global?) symbol table to which tokens and various other things refer, and which is gradually refined and updated throughout compilation. I think that may have been a widespread design once, but it's a bizarre anachronism now. Nowadays, information is often embedded directly into the AST, and compiler passes often create and destroy multiple ad-hoc symbol tables as necessary. I would primarily trust the dragon book for its theoretical content, although even that likely no longer represents the state of the art. I'm not all that knowledgeable about the state of the art in parsers, but I know that compiler optimisations have certainly moved beyond what is in the dragon book. In short, while the dragon book still contains useful information, I don't think its notion of how a compiler is constructed is close to how compilers are actually constructed today.
  • msla 9y ago
    There's also "Let's Build A Compiler" by Jack Crenshaw: https://compilers.iecc.com/crenshaw/ https://compilers.iecc.com/crenshaw/ This page links to that and another, "A Nanopass Framework for Compiler Education" by Sarkar, Waddell, and Dybvig: http://prog21.dadgum.com/30.html http://prog21.dadgum.com/30.html http://www.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf http://www.cs.indiana.edu/~dyb/pubs/nano-jfp.pdf
• caryhartline 9y ago
  If you're wondering why that page looks the way it does, well: > <html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:dt="uuid:C2F41010-65B3-11d1-A29F-00AA00C14882" xmlns="http://www.w3.org/TR/REC-html40"><head> http://www.w3.org/TR/REC-html40"><head> <meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
  • hnlmorg 9y ago
    It's easy to snigger at the code generator used for that site yet the signal to noise ratio for the content itself (which, if we are completely honest, is the metric that really matters) is still better than half the sites that use trendy frontend frameworks and passes JS lint.
  • quickben 9y ago
    It's short, informative, and up to the point.
    • tigroferoce 9y ago
      To give some context, I have studied with that professor and I can say that the guy is not super up to date with presentation technology: at the time (its was 2004) he was still using hand-written transparencies projected with an overhead projector. The readability was close to zero.
  • _ZeD_ 9y ago
    BTW: if OpenBSD choose comic sans for their presentation a reason should be -- cfr: https://news.ycombinator.com/item?id=9240906 https://news.ycombinator.com/item?id=9240906
• andreasgonewild 9y ago
  May I suggest considering Forth as a substrate? Or will that get me voted straight into neckbeard land? I've had a lot of fun hacking Forths, writing my own languages didn't really click until I finally had a serious look. Forth skips on most of the complexity of getting from bytes to semantics; even Lisp is complex in comparison; but is still powerful enough to do interesting things; and the best foundation for DSL's I've come across. My latest rabbit hole is called Snabel: https://github.com/andreas-gone-wild/snackis/blob/master/snabel.md https://github.com/andreas-gone-wild/snackis/blob/master/sna...
  • vidarh 9y ago
    Forth is one of those things that always fascinates me but ultimately always ends up feeling too hard to read. Snabel looks like an interesting experiment in that regard..
    • andreasgonewild 9y ago
      Lisp and Forth, everyone gets that reaction on first contact; the real problem is that most popular languages look the same these days. Popularity has very little to do with earning it. And it's getting worse with more and more crapscript lately. I'm not very much into dogmatics and orthodoxy, Forth wasn't the final answer to anything. Nothing ever is. Implementing the same thing over and over again doesn't make sense to me; I have plenty of experience of my own that thinks differently, things I always wanted to work differently. So that's what I'm doing, my best to improve the status quo.
      • e12e 9y ago
        I like both lisp and forth, but also think more syntax is useful for humans - both lisp and forth essentially demand that you program in ASTs directly, rather than some higher level abstraction/more pleasant.... Typography? Advanced semantic grammar? I'm not sure the ease of macro implementation is worth it. I'd love to see more efforts like Dylan. Or different kind of simplicity, like Smalltalk.
• whitten 9y ago
  I appreciate the effort to have a web page talking about writing your own compiler. Right now, I'm looking for an easy way to add define-use chains to a compiler. I know it involves breaking code into blocks and tracing through the code looking for use of the same variables. This tutorial is good because it adds a symbol table on each block level, which helps in differentiating names that are re-used in a block and don't refer to other variables of the same name. Does anyone know of code that makes clear what is involved in def-use for a variable without saying "this is an exercise for the reader" ?
  • tom_mellior 9y ago
    > a symbol table on each block level, which helps in differentiating names Yes, that's something that every compiler (for languages with scopes that allow hiding) needs. Typically you also never compare variables by name but by pointer to a symbol structure or some numeric ID. > Does anyone know of code that makes clear what is involved in def-use for a variable without saying "this is an exercise for the reader" ? It's not code, but chapter 2 of Nielson/Nielson/Hankin's Principles of Program Analysis discusses how to do this. See accompanying slides on the book's website: http://www.imm.dtu.dk/~hrni/PPA/ppasup2004.html http://www.imm.dtu.dk/~hrni/PPA/ppasup2004.html In a sense, this must be an exercise for the reader, since if you are working on your own compiler, nobody's code will be compatible with yours.
  • bubaflub 9y ago
    Go has several packages supporting program analysis in the standard library. https://golang.org/pkg/go/types/#Info https://golang.org/pkg/go/types/#Info populates separate maps for Defs and Uses. Check out the source for how they walk the SSA and calculate def-use chains. A more convenient interface to go program analysis is https://godoc.org/golang.org/x/tools/go/loader https://godoc.org/golang.org/x/tools/go/loader. See https://blog.cloudflare.com/building-the-simplest-go-static-analysis-tool/ https://blog.cloudflare.com/building-the-simplest-go-static-... for a basic tutorial on using the module.
• bollu 9y ago
  Shameless plug: I've been writing a series that's WIP about writing a tiny optimising compiler - https://github.com/bollu/tiny-optimising-compiler https://github.com/bollu/tiny-optimising-compiler. It tries to model as much as possible, and the aim is to show off the power that modern compiler ideas bring: SSA and polyhedral compilation.
  • chubot 9y ago
    This looks cool, thanks for pointing it out. I'm somewhat familiar witih SSA, but I don't know anything about polyhedral compilation. What does it buy you? Is there a concise intro you could point to? (I thought I had heard someone say it makes your compiler slower for marginal benefit, but they/I could be wrong about that.) FWIW I found this introduction to the new Go SSA back end pretty useful as an overview: https://www.youtube.com/watch?v=uTMvKVma5ms https://www.youtube.com/watch?v=uTMvKVma5ms One thing that was interesting is that they seemed to have an LLVM TableGen-like "rules" DSL for both architecture-independent and -dependent optimizations / code gen. I don't think polyhedral compilation was mentioned and I don't think they use it.
    • bollu 9y ago
      In fact, LLVM does use polyhedral compilation :) it's just disabled by default. There's a module called Polly in LLVM which performs polyhedral optimisations! Yep, tableGen is nice but would be overkill for this tutorial project.
    • gone35 9y ago
      See: https://en.m.wikipedia.org/wiki/Polytope_model https://en.m.wikipedia.org/wiki/Polytope_model https://www.cs.indiana.edu/~achauhan/Teaching/B629/2010-Fall/StudentPresns/PolyhedralModelOverview.pdf https://www.cs.indiana.edu/~achauhan/Teaching/B629/2010-Fall... http://web.cs.ucla.edu/~pouchet/lectures/doc/888.11.5.pdf http://web.cs.ucla.edu/~pouchet/lectures/doc/888.11.5.pdf