10 ms·

An Intro to Compilers

687 points by luu 9y ago

bitL 9y ago
BTW, can anyone please suggest a good online compiler course for creating your own programming language with labs/exams/certs? I can find pretty good courses for almost anything but not for compilers... Something that would focus on handling grammar (LALR, LL, CYK etc), ASTs, semantics, types, code-completion, imperative/OOP/functional/logical/self-modifying constructs etc. or even NLP-to-AST conversion...
- piemonkey 9y ago
  Alex Aiken has a very nice course: http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=Compilers http://openclassroom.stanford.edu/MainFolder/CoursePage.php?...
  - sn9 9y ago
    You can find this on Stanford Lagunita in a MOOC format.
- kerkeslager 9y ago
  Matt Might doesn't have an organized course for free online, but I found that his blog filled in a lot of the gaps for me between compiling a language like C, and a more modern language like Scheme or Python, which are missing from other resources I've found online. You'll have to click around to different posts, but here's a good starting point: http://matt.might.net/articles/compiling-scheme-to-c/ http://matt.might.net/articles/compiling-scheme-to-c/
  - DonaldPShimoda 9y ago
    Well... he kind of does, actually! http://matt.might.net/teaching/compilers/spring-2015/ http://matt.might.net/teaching/compilers/spring-2015/
    - kerkeslager 9y ago
      Awesome! Thanks for that.
- jpolitz 9y ago
  My compilers course has all the lectures recorded, and has starter code for all the assignments provided. It provides all the parsers, and focuses on the backend, including memory management and various details of value representations. This is just my materials, I don't have an associated platform with verification/certification. However, some folks from HN have previously done the course and emailed me after, and seem to have gotten some value out of it. https://cseweb.ucsd.edu/classes/sp17/cse131-a/ https://cseweb.ucsd.edu/classes/sp17/cse131-a/ https://podcast.ucsd.edu/podcasts/default.aspx?PodcastId=4014 https://podcast.ucsd.edu/podcasts/default.aspx?PodcastId=401... https://github.com/ucsd-cse131-sp17 https://github.com/ucsd-cse131-sp17 Earlier offering: https://www.cs.swarthmore.edu/~jpolitz/cs75/s16/ https://www.cs.swarthmore.edu/~jpolitz/cs75/s16/
  - rmusial 9y ago
    Thanks for this, this looks amazing
  - gilmi 9y ago
    I'm using the earlier offering of your course and another[0] to learn about compilers for a while now and it's the only method that really clicked for me. Thank you very much for making this open! [0]: http://www.ccs.neu.edu/course/cs4410 http://www.ccs.neu.edu/course/cs4410
    - jpolitz 9y ago
      Ben Lerner did a great job writing notes [0] for his version, which are super helpful if you prefer reading to videos. [0] https://course.ccs.neu.edu/cs4410/#%28part._lectures%29 https://course.ccs.neu.edu/cs4410/#%28part._lectures%29
      - gilmi 9y ago
        Definitely! They are really well done and actually worked better for me than videos. Unfortunately they only cover the first half of the course.
  - 9y ago
- dochtman 9y ago
  I liked the Stanford course given by Aiken, on Coursera: https://dirkjan.ochtman.nl/writing/2012/07/21/compilers-on-coursera.html https://dirkjan.ochtman.nl/writing/2012/07/21/compilers-on-c... Also, if you like this sort of thing, my compiler in Python that compiles to LLVM IR might be interesting: https://github.com/djc/runa https://github.com/djc/runa
- dipper 9y ago
  Most of this stuff flew over my head. While I understand C, this stiff feels out of grasp. Can anybody also please suggest recommended reading for beginners?
  - phenylene 9y ago
    Crafting Interpreters is a great read: http://www.craftinginterpreters.com/contents.html http://www.craftinginterpreters.com/contents.html
    - dipper 9y ago
      This looks great, thanks!
CalChris 9y ago
This was really good. I could imagine it being required background reading for a lab of the compilation pipeline in 61C at Berkeley. Add in a section on linking.
- stephengillie 9y ago
  Great read! I learned a lot about LLVM and Clang. Would like a section on JITs.
- sitkack 9y ago
  Levine's "Linkers and Loaders" is available online https://www.iecc.com/linker/ https://www.iecc.com/linker/
jacquesm 9y ago
If this stuff interests you, even though it is quite old you really should read the 'dragon book': https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...
- tmccrmck 9y ago
  We've rehashed the debate over the utility of the dragon book in the 21st century so many times on HN that I'm not going to comment on it's usefulness. (Search if interested) But, for those interested, I highly recommend Engineering a Compiler by Cooper and Torczon OR Modern Compiler Implementation in ML by Appel. I've read all three and would only recommend the dragon book to someone very interested in the subject.
  - timthorn 9y ago
    Appel's book is also available in many other languages, if the thought of ML is offputting.
    - sigjuice 9y ago
      Why would the thought of ML be off-putting?
      - timthorn 9y ago
        If you're unfamiliar with it but want to learn about compilers, a text in a language you know will decrease the cognitive load.
  - pbiggar 9y ago
    +1 for Cooper/Torczon (as someone who has a PhD in compilers, and still hates the Dragon book).
  - CalChris 9y ago
    The Monica Lam sections in the second edition of the Dragon Book are out of this world good. Also, she's an excellent lecturer. Muchnick's book is still quite good. A second semester compiler class is rarely taught and so everyone tries to squeeze too much into one semester. I almost wish they broke it in two and allowed students to take either half. LL(1) parsing isn't a prerequisite to static single assignment.
pbiggar 9y ago
Pet peeve about compiler education that is not repeated by this article (yay, well done!): the way you have to wade through months of parsing bullshit to get to the really interesting stuff (optimization and static analysis).
- gizmo686 9y ago
  As much as I enjoyed optimization and static analysis, parsing is probably the single most useful knowledge I got from my formal CS education; and probably the only part of a compiler that most CS students will ever need to know.
  - olewhalehunter 9y ago
    The symbiotic relationship between compiler development and hardware architecture design has a defining role in CS problems, and while you don't need to understand that relationship to write CRUD apps for a living, I think ignorance of it robs those who really want to understand this stuff of truths both technical and profound.
    - yeowMeng 9y ago
      Totally! Compiler development = Finite State Automaton + Push Down Automaton + Context Free Grammar + Intermediate representation + Static Analysis/Optimiation + Stack Machine + ... Hardware Architecture = Stack Machine/Turing Machine + electricity + creativity Stack Machine == Turing Machine Compiler development starts and ends with Turing Machines. Hardware architecture ends with Turing Machines operating at the speed of electricity through metal.
      - olewhalehunter 9y ago
        There are alternatives to this mainstream style of computer architecture, such as dataflow or hybrid quantum-classical systems, which both require a very different kind of compiler. https://en.wikipedia.org/wiki/Dataflow_architecture https://en.wikipedia.org/wiki/Dataflow_architecture
userbinator 9y ago
I know it might be a contrived case, but it's rather disappointing to see that even with the -O2 optimisation level, the final generated code contains 43% (3/7) useless instructions to mess around with RBP. I mean, it should be bleeding obvious to the compiler that this function doesn't require any stack allocation, much less an RBP-based one (the tradeoff between using RBP/RSP-based allocation is far more subtle, and I can forgive a compiler for choosing nonoptimally in that case), so why did it emit those useless instructions? There's plenty of articles about how intelligent compiler optimisers can be, and I don't doubt that they can do some pretty advanced transformations, having read a lot of compiler output; and then, I see things like this, which just make you go why!?!? It's puzzling how compilers behave, applying very sophisticated optimisation techniques but then missing the easy cases. The effect might not be as great as more advanced optimisations, but so is the effort required to do this type of optimisation. This is not even low-hanging fruit, it's sitting on the ground. However, the compiler will use as few registers as possible. Compilers usually try to use all the registers they can (although sometimes they do exhibit odd non-optimal behaviour, as described above); eschewing register use and using memory instead will increase code size and time.
- brigade 9y ago
  The "useless" instructions aren't for potential stack allocation, they're there so backtraces work. If you don't care about that then you can add -fomit-frame-pointer and they disappear. Compilers don't default to this because having backtraces on crashes and profiling are more useful than the like 1% speed gain from another available register on x86-64.
  - userbinator 9y ago
    Backtraces work without that. http://yosefk.com/blog/getting-the-call-stack-without-a-frame-pointer.html http://yosefk.com/blog/getting-the-call-stack-without-a-fram...
    - brigade 9y ago
      Are you arguing that they do work on ELF+DWARF with sufficient extra debug info, when running under a debugger, despite documentation that explicitly says it doesn't work? Because I certainly don't expect my users to have a debugger installed (let alone regularly run programs under one) but I'd still like to get useful crashlogs automatically. Or are you saying that you could potentially reconstruct a backtrace, if someone wrote code to do so that is smart enough to locate and account for all the stack adjustments in reconstructing where each function stored its return address, including runtime alloca() / VLA adjustments and multiple adjustments in the same function (potentially needing to reconstruct the code flow), just from the disassembly? Because the linked MIPS code is nowhere near that smart, and to my and that author's knowledge, such code has not been written for x86. Either way, nice in theory but not good enough in practice.
fleshweasel 9y ago
I'm a little confused as it looks like an image in the article labels a string literal as being a comment. Am I misunderstanding something?
- 6nf 9y ago
  Yea it's just a mistake, it should be string literal.
- b4ux1t3 9y ago
  Note that it is underlined in yellow. The color of the underline is what denotes it as a literal, not the color of the text itself.
simonebrunozzi 9y ago
Ha, sweet memories. I am 40 now; back in 2004-2006, for two years I was one of the youngest professors in Italy, teaching "compilers and programming languages". I still feel so fortunate to have had that experience. To help my students save the relatively huge amount of money to buy the dragon book(s), I created a condensed version of the parts that were required for the course - and I didn't charge anything for it, unlike what usually happens pretty much everywhere in Italy. They were available in PDF and OpenOffice formats, on the website that I created for the course (yes, the CS department didn't really have a proper website to use as CMS - I kid you not). You can find the material here, it's in Italian but it might be fun to take a quick look: http://www.lulu.com/shop/simone-brunozzi/dispense-lab-linguaggi-di-programmazione-e-compilatori-informatica-unipgit/ebook/product-17491425.html http://www.lulu.com/shop/simone-brunozzi/dispense-lab-lingua... Such good memories.
- negativ0 9y ago
  Do you have a link to download it without registering to lulu.com ?
  - simonebrunozzi 9y ago
    Oh, sure, I just put the most relevant stuff (in PDF and SXW) in a single zip file here: https://www.dropbox.com/s/medbtnjbd4lgoeb/lab-compilatori_brunozzi.zip?dl=0 https://www.dropbox.com/s/medbtnjbd4lgoeb/lab-compilatori_br...
- Rodd45 9y ago
  This is great Simone, thanks!
- agumonkey 9y ago
  There are two Aho Ullman books at my library, dense but amazing books. ps: how did students do on this class ? too hard but loved ?
  - simonebrunozzi 9y ago
WalterBright 9y ago
One nice thing today is the source code to professional compilers is readily available. Pick one for a simpler language, and just read the code.
- sigjuice 9y ago
  Is there a particular language that you could recommend? Thanks!
  - blacksmythe 9y ago
    Perhaps the one he wrote? Walter Bright is the creator and first implementer of the D programming language... http://www.walterbright.com/
    - WalterBright 9y ago
      D is a fairly complex language. I'd start with a simpler one, like a Pascal or Javascript compiler. For the latter, you can look at: https://github.com/DigitalMars/DMDScript/tree/master/engine/source/dmdscript https://github.com/DigitalMars/DMDScript/tree/master/engine/...
      - b4ux1t3 9y ago
        Cheers to you for not just trying to force your own creation down people's throats. D is a cool language, but you're right, it's a bit complex for a beginner.
      - jnordwick 9y ago
        I'd also say the Java compiler is fairly simple too, but it lack any real optimization passes.
        WalterBright 9y ago
        A Java compiler lacks optimization and code generation (generating IR is not code generation). So does Javascript. But they are both great languages for learning how lexing, parsing, and semantic analysis works because those operations are relatively simple. C is a harder one because the multiple "phases of translation" add quite a bit of complexity. It's easy to get lost in the frustrating and pointless complexity of the preprocesser. C++ layers onto that mixing semantic analysis up with parsing, and an unusually complex semantic analysis. Not for beginners. I suggest reading the source code to a professional compiler because there are books about how compilers work, and then there's how compilers really work. Pro compilers tend to be built differently from academic or side project compilers.
Tehnix 9y ago
> Some compilers translate source code into another programming language. These compilers are called source-to-source translators or transpilers I was wondering how compile-to-JS languages would be classified. Technically they are all transpilers, but seeing as there is no lower-level for the browser than JS (barring WebASM), one could also argue that they are in fact also compilers. Anyone have any thoughts on this?
- pbiggar 9y ago
  Transpiler is a recently made up word, and describes something that's just as well described as a compiler. I wouldn't spend too much time hoping for a distinction here.
  - nostrademons 9y ago
    I'd thought a transpiler is a compiler where the source and target language are the same and the semantics of the program are preserved across transpilation (eg. Closure Compiler, Babel, LLVM optimization passes). That's a useful distinction: it implies that you can feed the output of a transpiler back into the input and at worse the result will be idempotent, and that you can mix transpiled output with raw input and the result will still be interpretable. Evidently Wikipedia has a more broad definition of source-to-source compilation, which I'd agree is pretty meaningless. The distinction between high- and low-level languages is pretty arbitrary; you can write machine-language "source code", so in some ways all compilers are source-to-source.
    - jlouis 9y ago
      We could newspeak it to be an endo-compiler (endo- is greek for internal/within). It runs well with endo-functor.
  - chrisseaton 9y ago
    > Transpiler is a recently made up word People keep saying this, but it's not true. You can find the word being used, in its modern meaning, as far back as 1964. https://academic.oup.com/comjnl/article/7/1/28/558689/The-communication-of-algorithms https://academic.oup.com/comjnl/article/7/1/28/558689/The-co...
bogomipz 9y ago
Wow I enjoyed both the content and the design aesthetic of this post. I guess that's what happens what a designer turns software engineer? Please post more like this!
bollu 9y ago
I've been writing an llvm-lite in haskell to show of the main optimisation ideas of LLVM [here](https://github.com/bollu/tiny-optimising-compiler https://github.com/bollu/tiny-optimising-compiler). Thought someone maybe interested :)
yazilimci_adam 9y ago
Thanks. I liked this blog post. I've questions. Why should I prefer LLVM? What is LLVM and how it is different from GCC. I understand, every compiler has three parts. Front end, Optimizer and Back End. Looks simple.
- legulere 9y ago
  I haven't looked at the GCC code myself, but what I heard is that you can see that it's a codebase that grew massively over a large timespan and things that should be separated are not. At least a few years ago there were actually two different IR formats (the newer one being based on SSA) which are converted between each other several times. I think GCC's IR does not have a canonical text representation, this is really helpful for understanding and debugging in LLVM. Still also LLVM has its weird parts, like their variable naming scheme
kp25 9y ago
I'm usually scared to look at these compilers titled articles, feeling I do not understand or learn anything from it. This article is a very good intro to compilers and now I understood how these things work. Thanks for the article.
lmirosevic 9y ago
Can anyone point out to me where the linker fits into the equation?
deleted 9y ago
[deleted]
andreasgonewild 9y ago
Compiler design depends a lot on the language being compiled though, this would be a typical design for a C-style language. When doing Forth-style languages for example; I've found that it's not very helpful to parse to trees, since I can't tell the structure of function calls before seeing the actual running stack anyway. Which in turn affects the compiler, since all it has to work with is a sequential stream of tokens. And not all languages are stand-alone, or compile all the way down to machine code. Compiling to byte-code for running immediately, with the backup of a runtime library; is an attractive option for more specialized languages; and this means that it's possible to carry more information straight over from compilation to runtime. I've been working on a scripting language that raised some of these questions lately: https://github.com/andreas-gone-wild/snackis/blob/master/snabel.md https://github.com/andreas-gone-wild/snackis/blob/master/sna...
xoroshiro 9y ago
I don't understand why this still looks scary to me. A while back after learning regex (though only at a basic level) I thought, maybe I can make my own custom C preprocessor as an exercise. Perfect right? I get to choose the syntax AND the rules. But somehow I just can't write it. Nested ifdefs, defines, undefs mixing together too OP. Reading through this, it seems like there's a huge amount of work into real compilers. Front end, optimizer, backend, etc. I do appreciate it more, but as useful as compilers are, maybe I'll just leave it to the pros (:
- le-mark 9y ago
  > maybe I'll just leave it to the pros (: Don't ever do that! It really isn't that complicated at a basic level. Regex aren't the solution for parsing. What you're missing is the recursive nature of "context free languages"[1]. Formal language theory [2] was one of the big, early wins of Computer Science. There's a lot to it, but writing a simple recursive descent parser doesn't require any of it. The big caveat is that parsing is only about 1/3 of the problem, the others as described in this article are optimization and code generation. And of these, optimization can be skipped entirely leaving only code generation, which can be naively done by walking the AST. If this all seems foriegn to you, there's a lot of really good info online nowadays ie people love writing about this subject. Understanding this subject is very important in my opinion, this is one of the foundational things we do. Attaining a comfort level with compiler engineering is one the two or three things anyone can do to really "level up" as a software developer. Some other things are writing multi threaded servers in C, and 3d software rasterization. Again, my opinion here. [1] https://stackoverflow.com/questions/559763/regular-vs-context-free-grammars https://stackoverflow.com/questions/559763/regular-vs-contex... [2] https://en.wikipedia.org/wiki/Formal_language https://en.wikipedia.org/wiki/Formal_language
  - xoroshiro 9y ago
    >Understanding this subject is very important in my opinion, this is one of the foundational things we do. Attaining a comfort level with compiler engineering is one the two or three things anyone can do to really "level up" as a software developer. I think it depends on the level of abstraction. Then again, I'm not really a software developer, most of the work I do is scripting stuff for data analysis, which is where I learned regex from. I did learn C in college which I somehow got fascinated with, but I never really do any serious work with it. Still, over time, reading about quite lower level stuff (compared to what I do) does seem like it helps take the mystery out of things like unintuitive behaviors with multiple references to a Python list (I suspect it was pointers all along). Taking it to the next lower level with studying compilers and how assembly gets generated doesn't seem like it will benefit me much more. Still, I do like C enough to possibly consider doing something in it for fun if I get an idea, so maybe one day I'll come back to this.
codingbear 9y ago
Can anyone help me understand what kind of employment are available in the market which requires deep knowledge of compilers? I love this subject, but I don't know to which domains it is applied on outside of compiling languages like Javascript/JAVA/D/C/Rust and so on on into Machine code.
- 147 9y ago
  Steve Yegge's rant opened my eyes to how useful knowledge of compilers can be: http://steve-yegge.blogspot.com/2007/06/rich-programmer-food.html http://steve-yegge.blogspot.com/2007/06/rich-programmer-food...
JustSomeNobody 9y ago
I love reading about compilers. It's fascinating. I have implemented my own PL/0 compiler in various languages as a way to learn those languages. It's fun without having to think about designing a new language. Question: Does anyone know of some resources for adding concurrency to a simple stack based VM? I've been wanting to look into that for a while just for kicks. So, basically, take something like the machine here: https://en.wikipedia.org/wiki/P-code_machine https://en.wikipedia.org/wiki/P-code_machine and add concurrency to it.

687 points by luu 9y ago

bitL 9y ago

BTW, can anyone please suggest a good online compiler course for creating your own programming language with labs/exams/certs? I can find pretty good courses for almost anything but not for compilers... Something that would focus on handling grammar (LALR, LL, CYK etc), ASTs, semantics, types, code-completion, imperative/OOP/functional/logical/self-modifying constructs etc. or even NLP-to-AST conversion...

piemonkey 9y ago
Alex Aiken has a very nice course: http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=Compilers http://openclassroom.stanford.edu/MainFolder/CoursePage.php?...
- sn9 9y ago
  You can find this on Stanford Lagunita in a MOOC format.
kerkeslager 9y ago
Matt Might doesn't have an organized course for free online, but I found that his blog filled in a lot of the gaps for me between compiling a language like C, and a more modern language like Scheme or Python, which are missing from other resources I've found online. You'll have to click around to different posts, but here's a good starting point: http://matt.might.net/articles/compiling-scheme-to-c/ http://matt.might.net/articles/compiling-scheme-to-c/
- DonaldPShimoda 9y ago
  Well... he kind of does, actually! http://matt.might.net/teaching/compilers/spring-2015/ http://matt.might.net/teaching/compilers/spring-2015/
  - kerkeslager 9y ago
    Awesome! Thanks for that.
jpolitz 9y ago
My compilers course has all the lectures recorded, and has starter code for all the assignments provided. It provides all the parsers, and focuses on the backend, including memory management and various details of value representations. This is just my materials, I don't have an associated platform with verification/certification. However, some folks from HN have previously done the course and emailed me after, and seem to have gotten some value out of it. https://cseweb.ucsd.edu/classes/sp17/cse131-a/ https://cseweb.ucsd.edu/classes/sp17/cse131-a/ https://podcast.ucsd.edu/podcasts/default.aspx?PodcastId=4014 https://podcast.ucsd.edu/podcasts/default.aspx?PodcastId=401... https://github.com/ucsd-cse131-sp17 https://github.com/ucsd-cse131-sp17 Earlier offering: https://www.cs.swarthmore.edu/~jpolitz/cs75/s16/ https://www.cs.swarthmore.edu/~jpolitz/cs75/s16/
- rmusial 9y ago
  Thanks for this, this looks amazing
- gilmi 9y ago
  I'm using the earlier offering of your course and another[0] to learn about compilers for a while now and it's the only method that really clicked for me. Thank you very much for making this open! [0]: http://www.ccs.neu.edu/course/cs4410 http://www.ccs.neu.edu/course/cs4410
  - jpolitz 9y ago
    Ben Lerner did a great job writing notes [0] for his version, which are super helpful if you prefer reading to videos. [0] https://course.ccs.neu.edu/cs4410/#%28part._lectures%29 https://course.ccs.neu.edu/cs4410/#%28part._lectures%29
    - gilmi 9y ago
      Definitely! They are really well done and actually worked better for me than videos. Unfortunately they only cover the first half of the course.
- 9y ago
dochtman 9y ago
I liked the Stanford course given by Aiken, on Coursera: https://dirkjan.ochtman.nl/writing/2012/07/21/compilers-on-coursera.html https://dirkjan.ochtman.nl/writing/2012/07/21/compilers-on-c... Also, if you like this sort of thing, my compiler in Python that compiles to LLVM IR might be interesting: https://github.com/djc/runa https://github.com/djc/runa
dipper 9y ago
Most of this stuff flew over my head. While I understand C, this stiff feels out of grasp. Can anybody also please suggest recommended reading for beginners?
- phenylene 9y ago
  Crafting Interpreters is a great read: http://www.craftinginterpreters.com/contents.html http://www.craftinginterpreters.com/contents.html
  - dipper 9y ago
    This looks great, thanks!

CalChris 9y ago

This was really good. I could imagine it being required background reading for a lab of the compilation pipeline in 61C at Berkeley. Add in a section on linking.

stephengillie 9y ago
Great read! I learned a lot about LLVM and Clang. Would like a section on JITs.
sitkack 9y ago
Levine's "Linkers and Loaders" is available online https://www.iecc.com/linker/ https://www.iecc.com/linker/

jacquesm 9y ago

If this stuff interests you, even though it is quite old you really should read the 'dragon book': https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...

tmccrmck 9y ago
We've rehashed the debate over the utility of the dragon book in the 21st century so many times on HN that I'm not going to comment on it's usefulness. (Search if interested) But, for those interested, I highly recommend Engineering a Compiler by Cooper and Torczon OR Modern Compiler Implementation in ML by Appel. I've read all three and would only recommend the dragon book to someone very interested in the subject.
- timthorn 9y ago
  Appel's book is also available in many other languages, if the thought of ML is offputting.
  - sigjuice 9y ago
    Why would the thought of ML be off-putting?
    - timthorn 9y ago
      If you're unfamiliar with it but want to learn about compilers, a text in a language you know will decrease the cognitive load.
- pbiggar 9y ago
  +1 for Cooper/Torczon (as someone who has a PhD in compilers, and still hates the Dragon book).
- CalChris 9y ago
  The Monica Lam sections in the second edition of the Dragon Book are out of this world good. Also, she's an excellent lecturer. Muchnick's book is still quite good. A second semester compiler class is rarely taught and so everyone tries to squeeze too much into one semester. I almost wish they broke it in two and allowed students to take either half. LL(1) parsing isn't a prerequisite to static single assignment.

pbiggar 9y ago

Pet peeve about compiler education that is not repeated by this article (yay, well done!): the way you have to wade through months of parsing bullshit to get to the really interesting stuff (optimization and static analysis).

gizmo686 9y ago
As much as I enjoyed optimization and static analysis, parsing is probably the single most useful knowledge I got from my formal CS education; and probably the only part of a compiler that most CS students will ever need to know.
- olewhalehunter 9y ago
  The symbiotic relationship between compiler development and hardware architecture design has a defining role in CS problems, and while you don't need to understand that relationship to write CRUD apps for a living, I think ignorance of it robs those who really want to understand this stuff of truths both technical and profound.
  - yeowMeng 9y ago
    Totally! Compiler development = Finite State Automaton + Push Down Automaton + Context Free Grammar + Intermediate representation + Static Analysis/Optimiation + Stack Machine + ... Hardware Architecture = Stack Machine/Turing Machine + electricity + creativity Stack Machine == Turing Machine Compiler development starts and ends with Turing Machines. Hardware architecture ends with Turing Machines operating at the speed of electricity through metal.
    - olewhalehunter 9y ago
      There are alternatives to this mainstream style of computer architecture, such as dataflow or hybrid quantum-classical systems, which both require a very different kind of compiler. https://en.wikipedia.org/wiki/Dataflow_architecture https://en.wikipedia.org/wiki/Dataflow_architecture

userbinator 9y ago

I know it might be a contrived case, but it's rather disappointing to see that even with the -O2 optimisation level, the final generated code contains 43% (3/7) useless instructions to mess around with RBP. I mean, it should be bleeding obvious to the compiler that this function doesn't require any stack allocation, much less an RBP-based one (the tradeoff between using RBP/RSP-based allocation is far more subtle, and I can forgive a compiler for choosing nonoptimally in that case), so why did it emit those useless instructions? There's plenty of articles about how intelligent compiler optimisers can be, and I don't doubt that they can do some pretty advanced transformations, having read a lot of compiler output; and then, I see things like this, which just make you go why!?!? It's puzzling how compilers behave, applying very sophisticated optimisation techniques but then missing the easy cases. The effect might not be as great as more advanced optimisations, but so is the effort required to do this type of optimisation. This is not even low-hanging fruit, it's sitting on the ground. However, the compiler will use as few registers as possible. Compilers usually try to use all the registers they can (although sometimes they do exhibit odd non-optimal behaviour, as described above); eschewing register use and using memory instead will increase code size and time.

brigade 9y ago
The "useless" instructions aren't for potential stack allocation, they're there so backtraces work. If you don't care about that then you can add -fomit-frame-pointer and they disappear. Compilers don't default to this because having backtraces on crashes and profiling are more useful than the like 1% speed gain from another available register on x86-64.
- userbinator 9y ago
  Backtraces work without that. http://yosefk.com/blog/getting-the-call-stack-without-a-frame-pointer.html http://yosefk.com/blog/getting-the-call-stack-without-a-fram...
  - brigade 9y ago
    Are you arguing that they do work on ELF+DWARF with sufficient extra debug info, when running under a debugger, despite documentation that explicitly says it doesn't work? Because I certainly don't expect my users to have a debugger installed (let alone regularly run programs under one) but I'd still like to get useful crashlogs automatically. Or are you saying that you could potentially reconstruct a backtrace, if someone wrote code to do so that is smart enough to locate and account for all the stack adjustments in reconstructing where each function stored its return address, including runtime alloca() / VLA adjustments and multiple adjustments in the same function (potentially needing to reconstruct the code flow), just from the disassembly? Because the linked MIPS code is nowhere near that smart, and to my and that author's knowledge, such code has not been written for x86. Either way, nice in theory but not good enough in practice.

fleshweasel 9y ago

I'm a little confused as it looks like an image in the article labels a string literal as being a comment. Am I misunderstanding something?

6nf 9y ago
Yea it's just a mistake, it should be string literal.
b4ux1t3 9y ago
Note that it is underlined in yellow. The color of the underline is what denotes it as a literal, not the color of the text itself.

simonebrunozzi 9y ago

Ha, sweet memories. I am 40 now; back in 2004-2006, for two years I was one of the youngest professors in Italy, teaching "compilers and programming languages". I still feel so fortunate to have had that experience. To help my students save the relatively huge amount of money to buy the dragon book(s), I created a condensed version of the parts that were required for the course - and I didn't charge anything for it, unlike what usually happens pretty much everywhere in Italy. They were available in PDF and OpenOffice formats, on the website that I created for the course (yes, the CS department didn't really have a proper website to use as CMS - I kid you not). You can find the material here, it's in Italian but it might be fun to take a quick look: http://www.lulu.com/shop/simone-brunozzi/dispense-lab-linguaggi-di-programmazione-e-compilatori-informatica-unipgit/ebook/product-17491425.html http://www.lulu.com/shop/simone-brunozzi/dispense-lab-lingua... Such good memories.

negativ0 9y ago
Do you have a link to download it without registering to lulu.com ?
- simonebrunozzi 9y ago
  Oh, sure, I just put the most relevant stuff (in PDF and SXW) in a single zip file here: https://www.dropbox.com/s/medbtnjbd4lgoeb/lab-compilatori_brunozzi.zip?dl=0 https://www.dropbox.com/s/medbtnjbd4lgoeb/lab-compilatori_br...
Rodd45 9y ago
This is great Simone, thanks!
agumonkey 9y ago
There are two Aho Ullman books at my library, dense but amazing books. ps: how did students do on this class ? too hard but loved ?
- simonebrunozzi 9y ago

WalterBright 9y ago

One nice thing today is the source code to professional compilers is readily available. Pick one for a simpler language, and just read the code.

sigjuice 9y ago
Is there a particular language that you could recommend? Thanks!
- blacksmythe 9y ago
  Perhaps the one he wrote? Walter Bright is the creator and first implementer of the D programming language... http://www.walterbright.com/
  - WalterBright 9y ago
    D is a fairly complex language. I'd start with a simpler one, like a Pascal or Javascript compiler. For the latter, you can look at: https://github.com/DigitalMars/DMDScript/tree/master/engine/source/dmdscript https://github.com/DigitalMars/DMDScript/tree/master/engine/...
    - b4ux1t3 9y ago
      Cheers to you for not just trying to force your own creation down people's throats. D is a cool language, but you're right, it's a bit complex for a beginner.
    - jnordwick 9y ago
      I'd also say the Java compiler is fairly simple too, but it lack any real optimization passes.
      - WalterBright 9y ago
        A Java compiler lacks optimization and code generation (generating IR is not code generation). So does Javascript. But they are both great languages for learning how lexing, parsing, and semantic analysis works because those operations are relatively simple. C is a harder one because the multiple "phases of translation" add quite a bit of complexity. It's easy to get lost in the frustrating and pointless complexity of the preprocesser. C++ layers onto that mixing semantic analysis up with parsing, and an unusually complex semantic analysis. Not for beginners. I suggest reading the source code to a professional compiler because there are books about how compilers work, and then there's how compilers really work. Pro compilers tend to be built differently from academic or side project compilers.

Tehnix 9y ago

> Some compilers translate source code into another programming language. These compilers are called source-to-source translators or transpilers I was wondering how compile-to-JS languages would be classified. Technically they are all transpilers, but seeing as there is no lower-level for the browser than JS (barring WebASM), one could also argue that they are in fact also compilers. Anyone have any thoughts on this?

pbiggar 9y ago
Transpiler is a recently made up word, and describes something that's just as well described as a compiler. I wouldn't spend too much time hoping for a distinction here.
- nostrademons 9y ago
  I'd thought a transpiler is a compiler where the source and target language are the same and the semantics of the program are preserved across transpilation (eg. Closure Compiler, Babel, LLVM optimization passes). That's a useful distinction: it implies that you can feed the output of a transpiler back into the input and at worse the result will be idempotent, and that you can mix transpiled output with raw input and the result will still be interpretable. Evidently Wikipedia has a more broad definition of source-to-source compilation, which I'd agree is pretty meaningless. The distinction between high- and low-level languages is pretty arbitrary; you can write machine-language "source code", so in some ways all compilers are source-to-source.
  - jlouis 9y ago
    We could newspeak it to be an endo-compiler (endo- is greek for internal/within). It runs well with endo-functor.
- chrisseaton 9y ago
  > Transpiler is a recently made up word People keep saying this, but it's not true. You can find the word being used, in its modern meaning, as far back as 1964. https://academic.oup.com/comjnl/article/7/1/28/558689/The-communication-of-algorithms https://academic.oup.com/comjnl/article/7/1/28/558689/The-co...

bogomipz 9y ago

Wow I enjoyed both the content and the design aesthetic of this post. I guess that's what happens what a designer turns software engineer? Please post more like this!

bollu 9y ago

I've been writing an llvm-lite in haskell to show of the main optimisation ideas of LLVM [here](https://github.com/bollu/tiny-optimising-compiler https://github.com/bollu/tiny-optimising-compiler). Thought someone maybe interested :)

yazilimci_adam 9y ago

Thanks. I liked this blog post. I've questions. Why should I prefer LLVM? What is LLVM and how it is different from GCC. I understand, every compiler has three parts. Front end, Optimizer and Back End. Looks simple.

legulere 9y ago
I haven't looked at the GCC code myself, but what I heard is that you can see that it's a codebase that grew massively over a large timespan and things that should be separated are not. At least a few years ago there were actually two different IR formats (the newer one being based on SSA) which are converted between each other several times. I think GCC's IR does not have a canonical text representation, this is really helpful for understanding and debugging in LLVM. Still also LLVM has its weird parts, like their variable naming scheme

kp25 9y ago

I'm usually scared to look at these compilers titled articles, feeling I do not understand or learn anything from it. This article is a very good intro to compilers and now I understood how these things work. Thanks for the article.

lmirosevic 9y ago

Can anyone point out to me where the linker fits into the equation?

deleted 9y ago

[deleted]

andreasgonewild 9y ago

Compiler design depends a lot on the language being compiled though, this would be a typical design for a C-style language. When doing Forth-style languages for example; I've found that it's not very helpful to parse to trees, since I can't tell the structure of function calls before seeing the actual running stack anyway. Which in turn affects the compiler, since all it has to work with is a sequential stream of tokens. And not all languages are stand-alone, or compile all the way down to machine code. Compiling to byte-code for running immediately, with the backup of a runtime library; is an attractive option for more specialized languages; and this means that it's possible to carry more information straight over from compilation to runtime. I've been working on a scripting language that raised some of these questions lately: https://github.com/andreas-gone-wild/snackis/blob/master/snabel.md https://github.com/andreas-gone-wild/snackis/blob/master/sna...

xoroshiro 9y ago

I don't understand why this still looks scary to me. A while back after learning regex (though only at a basic level) I thought, maybe I can make my own custom C preprocessor as an exercise. Perfect right? I get to choose the syntax AND the rules. But somehow I just can't write it. Nested ifdefs, defines, undefs mixing together too OP. Reading through this, it seems like there's a huge amount of work into real compilers. Front end, optimizer, backend, etc. I do appreciate it more, but as useful as compilers are, maybe I'll just leave it to the pros (:

le-mark 9y ago
> maybe I'll just leave it to the pros (: Don't ever do that! It really isn't that complicated at a basic level. Regex aren't the solution for parsing. What you're missing is the recursive nature of "context free languages"[1]. Formal language theory [2] was one of the big, early wins of Computer Science. There's a lot to it, but writing a simple recursive descent parser doesn't require any of it. The big caveat is that parsing is only about 1/3 of the problem, the others as described in this article are optimization and code generation. And of these, optimization can be skipped entirely leaving only code generation, which can be naively done by walking the AST. If this all seems foriegn to you, there's a lot of really good info online nowadays ie people love writing about this subject. Understanding this subject is very important in my opinion, this is one of the foundational things we do. Attaining a comfort level with compiler engineering is one the two or three things anyone can do to really "level up" as a software developer. Some other things are writing multi threaded servers in C, and 3d software rasterization. Again, my opinion here. [1] https://stackoverflow.com/questions/559763/regular-vs-context-free-grammars https://stackoverflow.com/questions/559763/regular-vs-contex... [2] https://en.wikipedia.org/wiki/Formal_language https://en.wikipedia.org/wiki/Formal_language
- xoroshiro 9y ago
  >Understanding this subject is very important in my opinion, this is one of the foundational things we do. Attaining a comfort level with compiler engineering is one the two or three things anyone can do to really "level up" as a software developer. I think it depends on the level of abstraction. Then again, I'm not really a software developer, most of the work I do is scripting stuff for data analysis, which is where I learned regex from. I did learn C in college which I somehow got fascinated with, but I never really do any serious work with it. Still, over time, reading about quite lower level stuff (compared to what I do) does seem like it helps take the mystery out of things like unintuitive behaviors with multiple references to a Python list (I suspect it was pointers all along). Taking it to the next lower level with studying compilers and how assembly gets generated doesn't seem like it will benefit me much more. Still, I do like C enough to possibly consider doing something in it for fun if I get an idea, so maybe one day I'll come back to this.

codingbear 9y ago

Can anyone help me understand what kind of employment are available in the market which requires deep knowledge of compilers? I love this subject, but I don't know to which domains it is applied on outside of compiling languages like Javascript/JAVA/D/C/Rust and so on on into Machine code.

147 9y ago
Steve Yegge's rant opened my eyes to how useful knowledge of compilers can be: http://steve-yegge.blogspot.com/2007/06/rich-programmer-food.html http://steve-yegge.blogspot.com/2007/06/rich-programmer-food...

JustSomeNobody 9y ago

I love reading about compilers. It's fascinating. I have implemented my own PL/0 compiler in various languages as a way to learn those languages. It's fun without having to think about designing a new language. Question: Does anyone know of some resources for adding concurrency to a simple stack based VM? I've been wanting to look into that for a while just for kicks. So, basically, take something like the machine here: https://en.wikipedia.org/wiki/P-code_machine https://en.wikipedia.org/wiki/P-code_machine and add concurrency to it.