Compilers

I thought that this could be a fun topic to discuss. After having written a few naive compiler-ish things to parse DSL's and generate code to solve my problems, I thought It'd be a good idea to just spend a summer learning the whole thing formally. What would your main recommendation be for self-study books? I'm currently looking into the Tiger book and Engineering: a compiler as my two main options. What do you guys think about the best resources to learn to write one? For now, this is more about theory/practice/understanding than learning specific frameworks like LLVM, which I'd also like to learn eventually.

>>7931 You need to learn about formal grammar definitions https://en.wikipedia.org/wiki/Formal_grammar Then use lex and bison or similar tools to parse them and bind symbols to code. https://en.wikipedia.org/wiki/GNU_bison Best way to get into it is probably to start hands on with simple projects like a simple json or xml parsers or whatever.

>>7936 I'm not worried about parsing to be honest and have worked with grammars before. I have written things like JSON parsers before, mostly with parser combinators. AST transformations/optimizing compilers feel like magic to me however.

>>7931 Nice thread. It would be great to share books and resources about compilers here. Also, what is a good way to learn about assembly targets? Is experience with programming directly in X86 assembly the best way to pick up good enough skills to write a backend to it?

Ive heard that ANTLR is supposed to be good for making compilers and there is a book written by the author of ANTLR on how to make compilers. There is a classic free text available called "Lets make a compiler" that uses Pascal and has been translated into other programming languages. These two books are about coding a simple programming language interpreter by hand

>>7931 >the Tiger book ML > Java >>> C Compiling with Continuations by the same author is definitely not a recommendation for a general text but if you like ML and are interested in CPS then it is definitely worth a look. I always recommend Programming Language Pragmatics by Scott, especially for self learning. Basics of Compiler Design by Mogenson (http://www.diku.dk/%7Etorbenm/Basics/), covers a broader range of topics than Engineering A Compiler in 1/3 of the time and at a slightly lower level. >>7939 >a book written by the author of ANTLR on how to make compilers Language Implementation Patterns by Parr. Another book I often recommend, but definitely for beginners wanting a practical introduction. Ruby Under The Microscope is another book thats good for beginners who know Ruby and the basics of C. For the Lisp minded lainon and/or as next steps from SICP/Little & Seasoned Schemer: Lisp In Small Pieces by Queinnec An Introduction to Scheme and its Implementation (ftp://ftp.cs.utexas.edu/pub/garbage/cs345/schintro-v14/schintro_toc.html) Essentials of Programming Languages by Friedman & Wand Programming Languages: Application and Interpretation by Shriram Krishnamurthi (http://cs.brown.edu/~sk/Publications/Books/ProgLangs/) there is a decent amount of overlap in what these four cover so choose one and enjoy.

>>7939 Also, thanks for that Go book.

>>7940 Basics of compiler designs looks like a solid book for the basics if you want to get something as quickly as possible. Engineeirng a compiler goes much more in depth about optimizations and things like SSA forms, but to be honest I think that the tiger book does this better.

>parser generators Come on, this is 80s technology. Why don't we have simple context-free parsers that work just like the regular expressions libraries? The Earley parsing algorithm can receive its grammar as input at runtime with no need to generate any code and it parses arbitrary context-free grammars; seems like an obvious candidate for a parsing API. If you must generate code, why not JIT compile the parser at runtime instead? Why must tools generate fuarrrking C code that must be compiled separately? Regexp engines can compile inputs to ridiculously fast automata.

>>7940 >Basics of Compiler Design by Mogenson (http://www.diku.dk/%7Etorbenm/Basics/), covers a broader range of topics than Engineering A Compiler in 1/3 of the time and at a slightly lower level. I got my start in compilers through this book and can attest that it's really good for getting started. It maybe spends a little too much time on syntax (lexing and parsing) but apart from that it's great.

>>7965 Parser generators are used mostly because of performance. See for example Parsec vs Happy in the Haskell world. Parsec is used for parsing DSL's where performance is not critical, while Happy is used to generate Haskell code from a grammar specification when Parsec's performance is subpar. Compiler writers don't have any issue with building a compiler that compiles compilers and automatically applies microoptimizations, they love that stuff. With that said, code generation at runtime with a JIT should be perfectly doable in a dynamic language that supports generating code and evaling it, like Scheme, Common Lisp, or Julia. Neither of them are perfectly ideal for it though. My ideal language for this kind of stuff would basically be an ML variant which is dynamic at top level with macros and access to the compiler at runtime, but statically typed within any given module so that the generated code that is evaled is typechecked. ML functors do provide a reasonably good amount of power but not as much as macros.

Here's batch 1 of books about compilers

and some llvm specific

last one

>>7940 > Language Implementation Patterns That's a really good one. Especially if you want a high overview of what goes into making one of these. > Programming Language Pragmatics Didn't know about this, it look really good, thanks lain. Is there any chance you could point me to a good resource on bytecode vms?

I have some newbie questions here, if you guys don't mind: can a compiler of language "X" be written in language "X"? whats best for studying compilers creating a new language or making a compiler of an existing language? is there any relationship between compilers and automata that accepts a certain language?

>>8022 >can a compiler of language "X" be written in language "X"? Yup. GCC was originally written in C. GNAT's frontend is all Ada. Rust's frontend is written in Rust. The process of having a compiler compile itself is named bootstrapping https://en.wikipedia.org/wiki/Bootstrapping_(compilers) . >whats best for studying compilers creating a new language or making a compiler of an existing language? I'd recommend implementing a language that was specifically created to teach building compilers/interpeters. >is there any relationship between compilers and automata that accepts a certain language? Yes.

I really want to get deep into writing compilers. I am sort of inspired by what Niklaus Wirth did with Oberon. Basically a language + an OS.

>>8022 I just remembered that this exists: https://github.com/kanaka/mal/blob/master/process/guide.md It's a guide about building a lisp. It could probably help you.

>>8100 While that is a respectable goal, you might find that building on top of Linux is a more achievable goal. You can throw out all of GNU and build the entire user space in your language instead.

>>7931 Bisqwit is making video series on compilers: https://www.youtube.com/watch?v=KwpcOYKfXZc&list=PLzLzYGEbdY5n9ITKUqOuRjXkRU5tMW2Sd

Enjoy.

I know this is compiler thread but if anyone wants to play around with the general concept of interpreters or programming languages, take gander at this article about implementing poor man's scheme interpreter in few lines of python http://norvig.com/lispy.html It is quite easy to follow and I found it interesting that the author took full advantage of Python's list (which handles heterogeneous types without much hussle compared with other langs) and other data structures while dealing with s-expressions and evaluation cycle.

>>8196 I agree, this is a very instructive implementation. The only thing I don't like is how it glosses over the entire garbage collection topic by reusing Python's. Here's an equally instructive post for that: http://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/

Which book should I start with if I want to make my own Scheme compiler and eventually my own C compiler? I have the dragon book already, I'm just not sure how to approach all of this or if it's even the best starting point.

>>11045 Sketchy Scheme and Scheme 9 from Empty Space http://www.t3x.org/

>>11045 the Dragon book is a tough place to start regardless of your level of skill. there are several good textbook recommendations throughout this thread. this paper might help you get started given your choices of languages.

>>11074 I'll give that paper a read through. Is Compiler Design In C a good starting place? I've often heard it recommended alongside the dragon book.

You should try to write one without readings first, reading corrupts your mind. Or at least thing about how to make one.