6 ms·

Let’s Build a Compiler (1995)

240 points by undreren 7y ago

ainar-g 7y ago
I love this series! Does anybody know, if anyone ever made a version that outputs AMD64 assembly instead of 68000? Or some kind of gentle introduction to a reduced version of the AMD64 instruction set, so that I could do it myself? The instruction set is quite huge, so having a number of primitive commands that get the job done would be nice.
- barrkel 7y ago
  You can go along way with not much more than a couple dozen instructions (mnemonics, though when encoded with addressing modes it'll be more opcodes, but Jack's compiler delegates that work to the assembler). MOV, MOVZX, JMP, CALL, RET, CMP, TEST, Jcc, ADD, SUB, MUL, DIV, AND, OR, NOT, XOR, INC, DEC would about cover it for basic control flow and integer operations. Adding floating point arithmetic needs another dozen or so instructions. The x87 opcodes (FLD, FST, FADD etc.) are very easy to program against, since it's a stack machine - a post-order traversal of an expression tree is usually sufficient if the stack won't overflow, though SSE2 instructions are more usual for x64. Large portions of the full instruction set are vector operations which you wouldn't realistically be emitting for a didactic toy compiler. You can get by perfectly well without the string operations too.
  - fizixer 7y ago
    I agree with you. However, a quick personal anecdote: I tried to create "assembler", in python, for just one instruction, MOV. And not even 64, or 32-bit, (it was either 16-bit or 8-bit). After scratching my head with all the corner cases, and handling about 80% of them, my python code looked like a complete mess. There is an article floating around (posted here multiple times) that says MOV is turing complete [0]. [0] https://www.google.com/search?q=MOV+is+turing+complete https://www.google.com/search?q=MOV+is+turing+complete
    - nikeee 7y ago
      One simple way to show that MOV is turing complete is how this project does it: https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator This compiler compiles C to MOV instructions only.
    - blattimwind 7y ago
      MOV+ is a mnemonic for at least something like two or three dozen different opcodes though.
    - vidarh 7y ago
      But a compiler does not need to be able to generate every version in a generic way. You only need to generate the variations you're specifically intending to use.
    - wolfgke 7y ago
      > There is an article floating around (posted here multiple times) that says MOV is turing complete [0]. Don't believe this claim - any computer has only access to a finite amount of memory while a Turing machine needs an infinite tape to work. So the proof must be false. In other words: only a mathematically idealized version of MOV might be Turing complete - but this cannot be the MOV that x86 implements.
      - chrisseaton 7y ago
        Cone on... anyone reading the claim knows it has a silent ‘(but obviously with a machine-bound tape)’ at the end of it.
        wolfgke 7y ago
        The class of machines with the ‘(but obviously with a machine-bound tape)’ are even weaker than finite-state machines (because the number of states is bound by a fixed constant instead of "just" assumed to be finite). So if you argue that the silent ‘(but obviously with a machine-bound tape)’ assumption is OK, you argue that it is OK to identify Turing machines with a class of machines that is even weaker than finite-state machines. Any professor for (theoretical) computer science will be horrified by such claims.
- nils-m-holm 7y ago
  If 386 is sufficient: https://t3x.org/reload/index.html https://t3x.org/reload/index.html The later versions of the compiler even have an x86-64 backend. Or, if you want to skip assembly language entirely and compile directly to 386/ELF: https://t3x.org/t3x/book.html https://t3x.org/t3x/book.html
- tyingq 7y ago
  "a version that outputs AMD64 assembly" It's not based on the linked guide, but there's 8cc. Outputs x86-64 only. Diary of it being made: https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compiler-in-40-days https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compile... Github sources and history: https://github.com/rui314/8cc https://github.com/rui314/8cc The "gen.c" source file might be helpful for some of your questions about x86-64: https://github.com/rui314/8cc/blob/b8a46abdb5f0633bdbff314820daf560cb987377/gen.c https://github.com/rui314/8cc/blob/b8a46abdb5f0633bdbff31482...
- userbinator 7y ago
  There's an x86 version 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 64-bit is almost entirely a superset of 32-bit, so that will at least get you started.
einpoklum 7y ago
I would be a bit wary of a 30-year-old book on compiler construction. If it were more on the theoretical side then fine, but this sounds kind of hands-on. "Let's build a compiler with 1980s tools!" doesn't sound very appealing. That is just a shallow impression though. Convince me I'm wrong?
- makotoNagano 7y ago
  Sometimes learning on older technologies is very helpful to learning more of the fundamentals than learning practical skills directly. For example I studied how to program assembly code for an STM32F0 microprocessor. Would never do that in practice. but worked wonders in teaching me the intricacies of a processor at a very low level.
  - Athas 7y ago
    Old techniques are not necessarily more fundamental, they are just more primitive. (And often, but not always, more efficient.) In particular, old compiler texts will often do things like emit code directly from the parser, try to minimise the number of AST passes, or keep complex global symbol tables separate from the AST. These are mostly workarounds for technical limitations that are no longer relevant, and in fact only obscure the principles being taught (code generation during parsing is my pet example of this).
    - bakery2k 7y ago
      Isn't code generation during parsing still common today? In particular, bytecode generation in interpreters (and JIT compilers) for scripting languages, e.g. Lua?
      - vidarh 7y ago
        Yes, it is. It also doesn't really make much difference per se, as e.g. Wirth-style compilers still maintain careful separation of the code generation and parsing. And if you want to/need to later, you can trivially introduce an AST in those compilers by replacing the calls to the code-generator with calls to a tree builder, and then write a visitor-style driver for the code generation.
merricksb 7y ago
Previous HN discussions: https://news.ycombinator.com/item?id=6641117 https://news.ycombinator.com/item?id=6641117 (2013) https://news.ycombinator.com/item?id=1727004 https://news.ycombinator.com/item?id=1727004 (2010) https://news.ycombinator.com/item?id=232024 https://news.ycombinator.com/item?id=232024 (2008) (Links provided for info, not complaining about dupes.)
- svat 7y ago
  Also https://news.ycombinator.com/item?id=19890918 https://news.ycombinator.com/item?id=19890918 discusses https://xmonader.github.io/letsbuildacompiler-pretty/ https://xmonader.github.io/letsbuildacompiler-pretty/ which is a prettification of these plain .txt files — thanks to it I was able to read this series on my phone during lunch breaks.
eismcc 7y ago
Looks like it took a number of years for the article to be finished. From “back to the future”: I won't spend a lot of time making excuses; only point out that things happen, and priorities change. In the four years since installment fourteen, I've managed to get laid off, get divorced, have a nervous breakdown, begin a new career as a writer, begin another one as a consultant, move, work on two real-time systems, and raise fourteen baby birds, three pigeons, six possums, and a duck. The author has quite a diverse work history: https://www.linkedin.com/in/jack-crenshaw https://www.linkedin.com/in/jack-crenshaw
jimws 7y ago
This tutorial uses Pascal as the implementation language. Is there a similar tutorial done in a language that is mainstream today? Like Python? Go? Rust?
- mhh__ 7y ago
  Modern Compiler implementation in [x] follows a similar structure (in much more depth) and can be consumed in Java, C or - the correct choice - ML.
- Solarsail 7y ago
  Well, the tutorial itself has received translations from m68k Turbo Pascal to x86 C : https://github.com/lotabout/Let-s-build-a-compiler https://github.com/lotabout/Let-s-build-a-compiler
brianobush 7y ago
I really enjoyed Crenshaw's series on a Sweet 16-like interpreter in Embedded Programming (Programmer's Toolbox section) around 1999. He has a charming way of tying technology with history from his point of view. Found one article: https://m.eet.com/media/1171254/toolbox.pdf https://m.eet.com/media/1171254/toolbox.pdf

240 points by undreren 7y ago

I love this series! Does anybody know, if anyone ever made a version that outputs AMD64 assembly instead of 68000? Or some kind of gentle introduction to a reduced version of the AMD64 instruction set, so that I could do it myself? The instruction set is quite huge, so having a number of primitive commands that get the job done would be nice.

barrkel 7y ago
You can go along way with not much more than a couple dozen instructions (mnemonics, though when encoded with addressing modes it'll be more opcodes, but Jack's compiler delegates that work to the assembler). MOV, MOVZX, JMP, CALL, RET, CMP, TEST, Jcc, ADD, SUB, MUL, DIV, AND, OR, NOT, XOR, INC, DEC would about cover it for basic control flow and integer operations. Adding floating point arithmetic needs another dozen or so instructions. The x87 opcodes (FLD, FST, FADD etc.) are very easy to program against, since it's a stack machine - a post-order traversal of an expression tree is usually sufficient if the stack won't overflow, though SSE2 instructions are more usual for x64. Large portions of the full instruction set are vector operations which you wouldn't realistically be emitting for a didactic toy compiler. You can get by perfectly well without the string operations too.
- fizixer 7y ago
  I agree with you. However, a quick personal anecdote: I tried to create "assembler", in python, for just one instruction, MOV. And not even 64, or 32-bit, (it was either 16-bit or 8-bit). After scratching my head with all the corner cases, and handling about 80% of them, my python code looked like a complete mess. There is an article floating around (posted here multiple times) that says MOV is turing complete [0]. [0] https://www.google.com/search?q=MOV+is+turing+complete https://www.google.com/search?q=MOV+is+turing+complete
  - nikeee 7y ago
    One simple way to show that MOV is turing complete is how this project does it: https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator This compiler compiles C to MOV instructions only.
  - blattimwind 7y ago
    MOV+ is a mnemonic for at least something like two or three dozen different opcodes though.
  - vidarh 7y ago
    But a compiler does not need to be able to generate every version in a generic way. You only need to generate the variations you're specifically intending to use.
  - wolfgke 7y ago
    > There is an article floating around (posted here multiple times) that says MOV is turing complete [0]. Don't believe this claim - any computer has only access to a finite amount of memory while a Turing machine needs an infinite tape to work. So the proof must be false. In other words: only a mathematically idealized version of MOV might be Turing complete - but this cannot be the MOV that x86 implements.
    - chrisseaton 7y ago
      Cone on... anyone reading the claim knows it has a silent ‘(but obviously with a machine-bound tape)’ at the end of it.
      - wolfgke 7y ago
        The class of machines with the ‘(but obviously with a machine-bound tape)’ are even weaker than finite-state machines (because the number of states is bound by a fixed constant instead of "just" assumed to be finite). So if you argue that the silent ‘(but obviously with a machine-bound tape)’ assumption is OK, you argue that it is OK to identify Turing machines with a class of machines that is even weaker than finite-state machines. Any professor for (theoretical) computer science will be horrified by such claims.
nils-m-holm 7y ago
If 386 is sufficient: https://t3x.org/reload/index.html https://t3x.org/reload/index.html The later versions of the compiler even have an x86-64 backend. Or, if you want to skip assembly language entirely and compile directly to 386/ELF: https://t3x.org/t3x/book.html https://t3x.org/t3x/book.html
tyingq 7y ago
"a version that outputs AMD64 assembly" It's not based on the linked guide, but there's 8cc. Outputs x86-64 only. Diary of it being made: https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compiler-in-40-days https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compile... Github sources and history: https://github.com/rui314/8cc https://github.com/rui314/8cc The "gen.c" source file might be helpful for some of your questions about x86-64: https://github.com/rui314/8cc/blob/b8a46abdb5f0633bdbff314820daf560cb987377/gen.c https://github.com/rui314/8cc/blob/b8a46abdb5f0633bdbff31482...
userbinator 7y ago
There's an x86 version 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 64-bit is almost entirely a superset of 32-bit, so that will at least get you started.

einpoklum 7y ago

I would be a bit wary of a 30-year-old book on compiler construction. If it were more on the theoretical side then fine, but this sounds kind of hands-on. "Let's build a compiler with 1980s tools!" doesn't sound very appealing. That is just a shallow impression though. Convince me I'm wrong?

makotoNagano 7y ago
Sometimes learning on older technologies is very helpful to learning more of the fundamentals than learning practical skills directly. For example I studied how to program assembly code for an STM32F0 microprocessor. Would never do that in practice. but worked wonders in teaching me the intricacies of a processor at a very low level.
- Athas 7y ago
  Old techniques are not necessarily more fundamental, they are just more primitive. (And often, but not always, more efficient.) In particular, old compiler texts will often do things like emit code directly from the parser, try to minimise the number of AST passes, or keep complex global symbol tables separate from the AST. These are mostly workarounds for technical limitations that are no longer relevant, and in fact only obscure the principles being taught (code generation during parsing is my pet example of this).
  - bakery2k 7y ago
    Isn't code generation during parsing still common today? In particular, bytecode generation in interpreters (and JIT compilers) for scripting languages, e.g. Lua?
    - vidarh 7y ago
      Yes, it is. It also doesn't really make much difference per se, as e.g. Wirth-style compilers still maintain careful separation of the code generation and parsing. And if you want to/need to later, you can trivially introduce an AST in those compilers by replacing the calls to the code-generator with calls to a tree builder, and then write a visitor-style driver for the code generation.

merricksb 7y ago

Previous HN discussions: https://news.ycombinator.com/item?id=6641117 https://news.ycombinator.com/item?id=6641117 (2013) https://news.ycombinator.com/item?id=1727004 https://news.ycombinator.com/item?id=1727004 (2010) https://news.ycombinator.com/item?id=232024 https://news.ycombinator.com/item?id=232024 (2008) (Links provided for info, not complaining about dupes.)

svat 7y ago
Also https://news.ycombinator.com/item?id=19890918 https://news.ycombinator.com/item?id=19890918 discusses https://xmonader.github.io/letsbuildacompiler-pretty/ https://xmonader.github.io/letsbuildacompiler-pretty/ which is a prettification of these plain .txt files — thanks to it I was able to read this series on my phone during lunch breaks.

eismcc 7y ago

Looks like it took a number of years for the article to be finished. From “back to the future”: I won't spend a lot of time making excuses; only point out that things happen, and priorities change. In the four years since installment fourteen, I've managed to get laid off, get divorced, have a nervous breakdown, begin a new career as a writer, begin another one as a consultant, move, work on two real-time systems, and raise fourteen baby birds, three pigeons, six possums, and a duck. The author has quite a diverse work history: https://www.linkedin.com/in/jack-crenshaw https://www.linkedin.com/in/jack-crenshaw

jimws 7y ago

This tutorial uses Pascal as the implementation language. Is there a similar tutorial done in a language that is mainstream today? Like Python? Go? Rust?

mhh__ 7y ago
Modern Compiler implementation in [x] follows a similar structure (in much more depth) and can be consumed in Java, C or - the correct choice - ML.
Solarsail 7y ago
Well, the tutorial itself has received translations from m68k Turbo Pascal to x86 C : https://github.com/lotabout/Let-s-build-a-compiler https://github.com/lotabout/Let-s-build-a-compiler

brianobush 7y ago

I really enjoyed Crenshaw's series on a Sweet 16-like interpreter in Embedded Programming (Programmer's Toolbox section) around 1999. He has a charming way of tying technology with history from his point of view. Found one article: https://m.eet.com/media/1171254/toolbox.pdf https://m.eet.com/media/1171254/toolbox.pdf