7 ms·

Semi-tangential rant: I went to grad school for compilers, and yet I've been struggling for several months to get started building something real-world. I can b

Semi-tangential rant: I went to grad school for compilers, and yet I've been struggling for several months to get started building something real-world. I can build interpreters and parsers in my sleep at this point, but the crucial next step nobody talks about is having a deep knowledge and understanding of the target language that your compiler will be emitting. For a conventional native ahead-of-time compiler that requires knowledge of x86, the ELF format, OS loading and more. I suppose this is why toolkits like LLVM are so popular :/

akovaski 10y ago
Why don't you compile to a language that you know already or that is easy to understand, and then compile that? (Ex. C, Java, C#, C++, go)
- akkartik 10y ago
  Yes, that's a perfectly valid option if the goal is just to implement a new language. My goal (similar to OP) is to learn how a native compiler works.
  - MaulingMonkey 10y ago
    Some of this starts delving into linking as well. Aside from documentation, you might consider reverse engineering tiny binaries. For example: http://timelessname.com/elfbin/ http://timelessname.com/elfbin/ Cheat a lot. They point out some disassembly for you. ".ELF" is clearly some kind of magic string to confirm it's an elf file. "A4 00 00 00" looks like a 4-byte little endian integer (164) or perhaps an offset (0x000000A4 happens to be exactly where all the strings start), "34 00 20 00" might be a pair of shorts... 0x34 = 52 = "Start of program headers" among other matches - it probably corresponds to one of these fields! Try mutating the file and re-running readelf to see what fields change, or if the program still runs. Just a hex editor and a way to correlate the raw bytes of the disassembly to where the occur in the file can get you surprisingly far. While there will be "dead" data that you can't determine the nature of, documentation can help fill in the holes once you start getting a hold on the "important" bits that actually do stuff (mostly make your program un-runable, I assume.)
emeraldd 10y ago
One way around this is to divide the problem ... Compile to an intermediate format that is closer to what you want your final output to be. FORTH is a reasonable example and P-Code is another one (https://en.wikipedia.org/wiki/P-code_machine https://en.wikipedia.org/wiki/P-code_machine) then you can get the all the "easy" stuff into a stable state with an runtime library and back into a native code generator later. If you can get that working, you can probably jump to something like an assembler output with as or nasm to produce a "real" executable. I got about half way there with https://github.com/arlaneenalra/insomniac https://github.com/arlaneenalra/insomniac and have been stuck looking for time to get back to it.
- akkartik 10y ago
  Thanks, particularly for the tip about P-code. Are you aware of any interpreters/assemblers for P-code? The Wikipedia page didn't seem to have any links.
  - emeraldd 10y ago
    A quick google search pulls up: https://gist.github.com/r-lyeh/0af42b2788bb75219061 https://gist.github.com/r-lyeh/0af42b2788bb75219061 http://scara.com/~schirmer/o/pcodevm/ http://scara.com/~schirmer/o/pcodevm/ Here's another ref: http://homepages.cwi.nl/~steven/pascal/book/pascalimplementation.html http://homepages.cwi.nl/~steven/pascal/book/pascalimplementa... But really, all you need is an understanding of the ISA (i.e. the instruction set and the machine it runs on), and have a file format in mind for a middle layer and you can build a runtime. (Basically P-code one form of ISA that's supposed to be portable.) That's kind of what insomniac with a custom isa does: ISA: https://github.com/arlaneenalra/insomniac/blob/master/insomniac_as https://github.com/arlaneenalra/insomniac/blob/master/insomn... ( a little FORTH happy ...) Assembler Core: https://github.com/arlaneenalra/insomniac/tree/master/src/libinsomniac_asm https://github.com/arlaneenalra/insomniac/tree/master/src/li... VM eval loop: https://github.com/arlaneenalra/insomniac/blob/master/src/libinsomniac_vm/vm_eval.c https://github.com/arlaneenalra/insomniac/blob/master/src/li... and Instructions: https://github.com/arlaneenalra/insomniac/tree/master/src/libinsomniac_vm/libinsomniac_vm_instructions https://github.com/arlaneenalra/insomniac/tree/master/src/li... https://github.com/arlaneenalra/insomniac/blob/master/src/libinsomniac_vm/libinsomniac_vm_instructions/vm_ops.c https://github.com/arlaneenalra/insomniac/blob/master/src/li... It helps to build the assembler and vm backend first so you have a pipeline in play that you can use to add in ops as you discover they are needed. (keep in mind all my code is toy stuff..)
deleted 10y ago
[deleted]
jfoutz 10y ago
I'd suggest, make your first big goal to emit assembly, and use an existing toolchain to assemble and link. It gives you the opportunity to run your code much quicker. if you can handle compilers, assemblers are a piece of cake. So you can add a flag to emit a .o instead of a .S when you get down to that level. I've never actually written a linker, but when you're down at that level it's fairly obvious what needs to happen. There's some sort of binary prolog that indicates this is an executable. Then you have this table of symbolic names to offsets, you replace the symbolic references with actual numbers. If you have something like a.o, b.o, and c.o, and a.o needs to call foo in c.o, it's kind of just sizeof(a.o) + sizeof(b.o) + offset(foo, c.o) assemblers and linkers are kinda tough because they need to be perfect, but you don't have the hard algorithmic problems you have in compilers, like register allocation. Also, if you limit yourself to a small subset of x86, you can pretty quickly verify correctness using existing tools, then make toy versions of your assembler and linker. Adding more instructions only means touching the assembler. You can do it!
- sedachv 10y ago
  +1. Direct compilation is simpler and faster than layering everything. Abdulaziz Ghuloum wrote a great tutorial to "show that building a compiler can be as easy as building an interpreter": http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf A great compiler based on this principle is TCC: http://bellard.org/tcc/ http://bellard.org/tcc/ The code generators are basically built around calling parser.next_token(). It is simple (highly recommend reading the source) and very fast. There is also a linker included.
  - userbinator 10y ago
    building a compiler can be as easy as building an interpreter I prefer this demonstration to the one in that paper: Interpreter: https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8558822 JIT compiler: https://news.ycombinator.com/item?id=8746054 https://news.ycombinator.com/item?id=8746054 To make things more interesting, it's "real syntax", i.e. C-like, rather than the "almost no parsing required" syntax of a Lisp, even smaller than TCC, and yet it can still compile itself. C4 and the few variants it's spawned have probably become my favourite family of tiny, understandable, but complete compilers. The sheer elegance and simplicity --- one file of less than 1K lines --- makes studying them highly recommended. Almost all the other tiny/teaching/toy compilers I've seen are larger, less capable, or both. I don't know if anyone has made a variant of C4 that generates an AST, but doing that would probably not be too difficult either, and then you'd have a tiny compiler you could experiment on with optimisation and such.
chubot 10y ago
Have you looked at the Go toolchain at all? I don't know much about it, but they implemented their back ends in a manner that is much smaller than LLVM and GCC. And it sounds like the architecture of the compiler is significantly different. I watched this talk and it was pretty interesting: https://www.youtube.com/watch?v=KINIAgRpkDA https://www.youtube.com/watch?v=KINIAgRpkDA https://talks.golang.org/2016/asm.slide#1 https://talks.golang.org/2016/asm.slide#1 If I am understanding right, the claim is that they have a single assembly language for ALL GO architectures, based on something Ken Thompson wrote in the 90's for some National Instruments (?) chip. He actually says that all assembly language looks the same now. I was sort of surprised by that claim. I would like to hear a critique of this from other compiler writers. Does the fact that Go uses a single assembly language make the code slower? I imagine taking advantage of target-specific knowledge is useful, but I don't know how much. LLVM has this pretty elaborate TableGen system to express target-specific knowledge. He also makes the claim that they will be able auto-generate a new backend from the PDF description of the architecture. And he says somewhere that they reduce a lot of the work to simple "text processing" (symbol manipulation) and didn't require opening up any processor manuals. I can see how arithmetic and bitshifting is the same among all architectures. But I would think that even loads and stores have differences, at least if you want to use the processor efficiently. But he says everything kinda looks the same. Also, another thought is that compiling to WebAssembly might be simpler than native executables?
- akkartik 10y ago
  Thanks for that brain dump! The details on Go were fascinating. I haven't looked more than superficially at any existing compilers outside of small toys. Reading large codebases is hard, and I have a harder time with it than most. (Hence my current project involving compilers: https://lobste.rs/s/n0d3qo/what_are_you_working_on_this_week/comments/rue8pf#c_rue8pf https://lobste.rs/s/n0d3qo/what_are_you_working_on_this_week... ) But let me put Go back on the head of the queue..
- GFK_of_xmaspast 10y ago
  Looking at those slides and watching the first part of the talk, it sounds as if he's re-invented LLVM IR, and poorly.
dochtman 10y ago
I built a compiler that just threw out LLVM IR to stdout. Pretty great way to get something working, if you ask me, and lots of potential to do FFI or other kinds of integration. LLVM takes care of lots of portability issues, and optimizes your stuff. My experimental stuff is here: https://github.com/djc/runa https://github.com/djc/runa. The compiler is written in Python, and shouldn't be that hard to understand. I'm also happy to answer any questions about it here.
- emeraldd 10y ago
  I still need to find the time figure out LLVM IR, do you have anything easier to read through than the official docs?
Someone 10y ago
If you want to roll your own code throughout, writing your own lexer, parser, and backend, for your first attempt, pick a dead simple source language and do not may any attempt at generating efficient code. An option would be a Basic from the '80s: no functions, all variables are global. If you think implementing a return stack is too hard, forget about supporting gosub; goto may be harmful, but it is enough to write some interesting programs (Certainly forget about computed gosub/goto in your first version) That makes lots of stuff incredibly easy. Variable 'a' always has the same address (the simplest implementation even would just allocate room for variables a-z, a%-z% and a$-z$ regardless of whether they got used, so that 'a' has the same address in every program) Forgetting about optimization means that, for example a = a + 1 a = 2 * a would compile to load a add 1 store a load a mul 2 store a , independently of where it appears in the program. That makes your compiler consist of two steps: - compute a map mapping line number to generated code for that line - fix up the targets of goto's (in the first version, don't bother about trying to use short jumps; just assume all jumps will be long) Inefficient? Yes, but make it work first, then make it fast (or skip that, as, frankly, if you want something for use in the real world, you should try and build on the likes of LLVM) Don't think that's cheating; it gives you around a tenfold speed up over a basic interpreter, and back then, people sold compilers doing the above. If you want advanced functions such as sin, do not hesitate to call into an external library. Those compilers from the '80s weren't afraid to call into ROM code, either.
- jfoutz 10y ago
  This is a great approach. I'd probably advise adding lexical scoping, because managing the stack is pretty interesting. Going from source to binary on your own code is incredibly satisfying and incredibly enlightening. It thoroughly drives out any "magic" in your mental model of computation. I agree wholeheartedly use LLVM (or something like it) for anything real. tens or hundreds of thousands of hours, by really smart people, gives you optimizations a lone wolf can never duplicate.
- stevekemp 10y ago
  That's a great suggestion. I went one step lower and wrote a (perl-based) virtual-machine. As you suggested I did the bare minimum at first, for example when I see labels I just remember their locations. Later on I patch up the offsets in the code, to make jumps to them point to the correct location. The project seems reasonably popular, for reasons that I don't understand, but it is very simple: https://github.com/skx/simple.vm https://github.com/skx/simple.vm
nickpsecurity 10y ago
Check out the QBE backend as it's designed for simplicity: http://c9x.me/compile/ http://c9x.me/compile/ Note: You could both target and learn from QBE potentially. ELF: http://www.cirosantilli.com/elf-hello-world/ http://www.cirosantilli.com/elf-hello-world/
Sir_Cmpwn 10y ago
I often work on tangental projects to understand problem spaces more. Try writing a mini libc, for example, with a dynamic loader. Try writing a linker and an assembler.
zura 10y ago
One would say Compilers is a multi-disciplinary field. You might enjoy some topics more than others. E.g. I personally favor stages after the parsing and before the actual code gen. :)
wfunction 10y ago
Are you talking about compilers, or just ("dumb") interpreters? To me, the hardest part of writing a compiler is the middle part that you totally neglected to mention: the static analysis & optimization. Not the parsing or the codegen.
jpolitz 10y ago
Plug for my compilers course, which is incremental and uses some of the ideas from sibling comments re: emitting assembly and Ghuloum's great work. Last time I posted it on HN, someone got back to me in a few weeks that they'd successfully gone through the assignments, so it seems at least somewhat concretely useful: https://www.cs.swarthmore.edu/~jpolitz/cs75/s16/ https://www.cs.swarthmore.edu/~jpolitz/cs75/s16/
- akkartik 10y ago
  Thanks! I'm gonna check it out.
webkike 10y ago
Well, it's the reason separation of concerns exist. You don't have to know all of the requirement to begin writing something real world, depending on what you mean by "real world". If you're trying to rewrite a feature complete GCC from scratch you're going to have to start somewhere and you won't be able to write everything from the start. So you divide the work in pieces and focus on each individually. Start out dumping assembly. If you really want to custom write ELF files that's fine but no place to start.
devwastaken 10y ago
Unrelated, but how would one get started creating a proper parser for textual content? For example, I have { "key" { "key" "value" "morekeys" { "key2" "value2" } } } The markup would be seperated by newlines, with the key-value pairs on the same line, always in quotes. I've solved it with regex and a crude parser before, but I've always heard of things like Bison and such but never found a 'good' way to impliment a real parser in a language like Python.
- userbinator 10y ago
  I would go with a simple recursive descent parser, unless you are interested in learning a DSL, the intricacies of the parsing algorithm your particular parser generator uses, and willing to debug one --- IMHO not worth it. Even "real", production-quality compilers like GCC, Clang, MSVC, and ICC use recursive-descent; and some, like GCC, switched away from parser generators.
  - david-given 10y ago
    Parser generators work really well for context-free grammars, but as soon as you start needing context-sensitive lexing (like C does) you enter World Of Pain time. And they avoid having to deal with lookahead, which is always messy in hand-written parsers. But I think I'd agree that writing a recursive descent parser from scratch is probably the best way to learn about parsing; at least for a simple grammar. BTW, fun fact: it turns out that BNF was invented by an Indian linguist called Pāṇini about 2500 years ago, in order to parse Sanskrit. https://en.wikipedia.org/wiki/P%C4%81%E1%B9%87ini https://en.wikipedia.org/wiki/P%C4%81%E1%B9%87ini
- akkartik 10y ago
  To elaborate on userbinator's comment, you want to think of your format as a set of definitions: A clause consists of a '{', one or more key-value pairs, and a '}'. A key-value pair consists of a string and a value. A value is either a string or a clause. Now turn each definition into a function. Here's a nice-looking article from Googling for "writing a recursive descent parser": http://weblog.jamisbuck.org/2015/7/30/writing-a-simple-recursive-descent-parser.html http://weblog.jamisbuck.org/2015/7/30/writing-a-simple-recur...
readittwice 10y ago
True, but if you are willing to use some libraries or tools you can get pretty far. And if not, use them too :) you could always replace them later with your own tools. IMHO you need to decide on what part of the compiler you want to focus on. You mentioned you already know how to write a lexer and parser. So maybe you should start with an IR like WebAssembly you could compile. Maybe you could even reuse your lexer/parser from your interpreter. Compiling can be as simple as writing an interpreter, you "just" have to replace some code in the interpreter with `printf`s, that dump e.g. LLVM IR or Assembly. Then use LLVM or any assembler to get a binary. Even GCC basically works that way, gcc just dumps an assembly file and then passes it to assembler and linker. So GCC doesn't really emit ELF or Mach-O either, so don't let that stop you. That doesn't mean you don't have a "full" compiler. If you don't know assembly use tools like gcc.godbolt.org to see what code gcc generates. The most important thing: Think what code to generate for each feature of your language or IR. If you have figured that out all the rest will be trivial. For example: What code to generate for `if`? So don't try to compile a language with many fancy features at first and please don't try to generate fast code. You want a translation that works in every case, although it might be somewhat inefficient compared to `gcc -O3`. Your first program to compile could be something like `int main() {}`. If you can compile and execute this program, you can start to add features. This are the restrictions I would make at the beginning: * use a statically typed language, it is easier to generate (faster) code for that * start with global variables, add local variables later * support if, while and then functions (in this order) * only support few datatypes: int, int-array/pointer and string literals for printing. This should be enough to run the benchmarks binarytrees and fannkuch from The Computer Language Benchmark Game. You will already beat many dynamically typed and interpreted languages for those. Don't try to generate fast code at first, spill everything onto the stack so you don't have to care about register allocation. Even the V8 full-codegen jit works this way, so you don't have to be ashamed of it ;) If you don't care about ELF, linking and stuff you could also avoid this by writing a JIT-Compiler: Just emit code into some buffer and then directly start to execute. Although I have to admit that a JIT can introduce some challenges of its own. Ah and don't forget to write tests. Write a lot of tests from the beginning. Testing a compiler is pretty simple and is is also easy pretty easy to introduce subtle bugs. You will save a lot of time.

akovaski 10y ago

Why don't you compile to a language that you know already or that is easy to understand, and then compile that? (Ex. C, Java, C#, C++, go)

akkartik 10y ago
Yes, that's a perfectly valid option if the goal is just to implement a new language. My goal (similar to OP) is to learn how a native compiler works.
- MaulingMonkey 10y ago
  Some of this starts delving into linking as well. Aside from documentation, you might consider reverse engineering tiny binaries. For example: http://timelessname.com/elfbin/ http://timelessname.com/elfbin/ Cheat a lot. They point out some disassembly for you. ".ELF" is clearly some kind of magic string to confirm it's an elf file. "A4 00 00 00" looks like a 4-byte little endian integer (164) or perhaps an offset (0x000000A4 happens to be exactly where all the strings start), "34 00 20 00" might be a pair of shorts... 0x34 = 52 = "Start of program headers" among other matches - it probably corresponds to one of these fields! Try mutating the file and re-running readelf to see what fields change, or if the program still runs. Just a hex editor and a way to correlate the raw bytes of the disassembly to where the occur in the file can get you surprisingly far. While there will be "dead" data that you can't determine the nature of, documentation can help fill in the holes once you start getting a hold on the "important" bits that actually do stuff (mostly make your program un-runable, I assume.)

emeraldd 10y ago

One way around this is to divide the problem ... Compile to an intermediate format that is closer to what you want your final output to be. FORTH is a reasonable example and P-Code is another one (https://en.wikipedia.org/wiki/P-code_machine https://en.wikipedia.org/wiki/P-code_machine) then you can get the all the "easy" stuff into a stable state with an runtime library and back into a native code generator later. If you can get that working, you can probably jump to something like an assembler output with as or nasm to produce a "real" executable. I got about half way there with https://github.com/arlaneenalra/insomniac https://github.com/arlaneenalra/insomniac and have been stuck looking for time to get back to it.

akkartik 10y ago
Thanks, particularly for the tip about P-code. Are you aware of any interpreters/assemblers for P-code? The Wikipedia page didn't seem to have any links.
- emeraldd 10y ago
  A quick google search pulls up: https://gist.github.com/r-lyeh/0af42b2788bb75219061 https://gist.github.com/r-lyeh/0af42b2788bb75219061 http://scara.com/~schirmer/o/pcodevm/ http://scara.com/~schirmer/o/pcodevm/ Here's another ref: http://homepages.cwi.nl/~steven/pascal/book/pascalimplementation.html http://homepages.cwi.nl/~steven/pascal/book/pascalimplementa... But really, all you need is an understanding of the ISA (i.e. the instruction set and the machine it runs on), and have a file format in mind for a middle layer and you can build a runtime. (Basically P-code one form of ISA that's supposed to be portable.) That's kind of what insomniac with a custom isa does: ISA: https://github.com/arlaneenalra/insomniac/blob/master/insomniac_as https://github.com/arlaneenalra/insomniac/blob/master/insomn... ( a little FORTH happy ...) Assembler Core: https://github.com/arlaneenalra/insomniac/tree/master/src/libinsomniac_asm https://github.com/arlaneenalra/insomniac/tree/master/src/li... VM eval loop: https://github.com/arlaneenalra/insomniac/blob/master/src/libinsomniac_vm/vm_eval.c https://github.com/arlaneenalra/insomniac/blob/master/src/li... and Instructions: https://github.com/arlaneenalra/insomniac/tree/master/src/libinsomniac_vm/libinsomniac_vm_instructions https://github.com/arlaneenalra/insomniac/tree/master/src/li... https://github.com/arlaneenalra/insomniac/blob/master/src/libinsomniac_vm/libinsomniac_vm_instructions/vm_ops.c https://github.com/arlaneenalra/insomniac/blob/master/src/li... It helps to build the assembler and vm backend first so you have a pipeline in play that you can use to add in ops as you discover they are needed. (keep in mind all my code is toy stuff..)

deleted 10y ago

[deleted]

jfoutz 10y ago

I'd suggest, make your first big goal to emit assembly, and use an existing toolchain to assemble and link. It gives you the opportunity to run your code much quicker. if you can handle compilers, assemblers are a piece of cake. So you can add a flag to emit a .o instead of a .S when you get down to that level. I've never actually written a linker, but when you're down at that level it's fairly obvious what needs to happen. There's some sort of binary prolog that indicates this is an executable. Then you have this table of symbolic names to offsets, you replace the symbolic references with actual numbers. If you have something like a.o, b.o, and c.o, and a.o needs to call foo in c.o, it's kind of just sizeof(a.o) + sizeof(b.o) + offset(foo, c.o) assemblers and linkers are kinda tough because they need to be perfect, but you don't have the hard algorithmic problems you have in compilers, like register allocation. Also, if you limit yourself to a small subset of x86, you can pretty quickly verify correctness using existing tools, then make toy versions of your assembler and linker. Adding more instructions only means touching the assembler. You can do it!

sedachv 10y ago
+1. Direct compilation is simpler and faster than layering everything. Abdulaziz Ghuloum wrote a great tutorial to "show that building a compiler can be as easy as building an interpreter": http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf A great compiler based on this principle is TCC: http://bellard.org/tcc/ http://bellard.org/tcc/ The code generators are basically built around calling parser.next_token(). It is simple (highly recommend reading the source) and very fast. There is also a linker included.
- userbinator 10y ago
  building a compiler can be as easy as building an interpreter I prefer this demonstration to the one in that paper: Interpreter: https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8558822 JIT compiler: https://news.ycombinator.com/item?id=8746054 https://news.ycombinator.com/item?id=8746054 To make things more interesting, it's "real syntax", i.e. C-like, rather than the "almost no parsing required" syntax of a Lisp, even smaller than TCC, and yet it can still compile itself. C4 and the few variants it's spawned have probably become my favourite family of tiny, understandable, but complete compilers. The sheer elegance and simplicity --- one file of less than 1K lines --- makes studying them highly recommended. Almost all the other tiny/teaching/toy compilers I've seen are larger, less capable, or both. I don't know if anyone has made a variant of C4 that generates an AST, but doing that would probably not be too difficult either, and then you'd have a tiny compiler you could experiment on with optimisation and such.

chubot 10y ago

Have you looked at the Go toolchain at all? I don't know much about it, but they implemented their back ends in a manner that is much smaller than LLVM and GCC. And it sounds like the architecture of the compiler is significantly different. I watched this talk and it was pretty interesting: https://www.youtube.com/watch?v=KINIAgRpkDA https://www.youtube.com/watch?v=KINIAgRpkDA https://talks.golang.org/2016/asm.slide#1 https://talks.golang.org/2016/asm.slide#1 If I am understanding right, the claim is that they have a single assembly language for ALL GO architectures, based on something Ken Thompson wrote in the 90's for some National Instruments (?) chip. He actually says that all assembly language looks the same now. I was sort of surprised by that claim. I would like to hear a critique of this from other compiler writers. Does the fact that Go uses a single assembly language make the code slower? I imagine taking advantage of target-specific knowledge is useful, but I don't know how much. LLVM has this pretty elaborate TableGen system to express target-specific knowledge. He also makes the claim that they will be able auto-generate a new backend from the PDF description of the architecture. And he says somewhere that they reduce a lot of the work to simple "text processing" (symbol manipulation) and didn't require opening up any processor manuals. I can see how arithmetic and bitshifting is the same among all architectures. But I would think that even loads and stores have differences, at least if you want to use the processor efficiently. But he says everything kinda looks the same. Also, another thought is that compiling to WebAssembly might be simpler than native executables?

akkartik 10y ago
Thanks for that brain dump! The details on Go were fascinating. I haven't looked more than superficially at any existing compilers outside of small toys. Reading large codebases is hard, and I have a harder time with it than most. (Hence my current project involving compilers: https://lobste.rs/s/n0d3qo/what_are_you_working_on_this_week/comments/rue8pf#c_rue8pf https://lobste.rs/s/n0d3qo/what_are_you_working_on_this_week... ) But let me put Go back on the head of the queue..
GFK_of_xmaspast 10y ago
Looking at those slides and watching the first part of the talk, it sounds as if he's re-invented LLVM IR, and poorly.

dochtman 10y ago

I built a compiler that just threw out LLVM IR to stdout. Pretty great way to get something working, if you ask me, and lots of potential to do FFI or other kinds of integration. LLVM takes care of lots of portability issues, and optimizes your stuff. My experimental stuff is here: https://github.com/djc/runa https://github.com/djc/runa. The compiler is written in Python, and shouldn't be that hard to understand. I'm also happy to answer any questions about it here.

emeraldd 10y ago
I still need to find the time figure out LLVM IR, do you have anything easier to read through than the official docs?

Someone 10y ago

If you want to roll your own code throughout, writing your own lexer, parser, and backend, for your first attempt, pick a dead simple source language and do not may any attempt at generating efficient code. An option would be a Basic from the '80s: no functions, all variables are global. If you think implementing a return stack is too hard, forget about supporting gosub; goto may be harmful, but it is enough to write some interesting programs (Certainly forget about computed gosub/goto in your first version) That makes lots of stuff incredibly easy. Variable 'a' always has the same address (the simplest implementation even would just allocate room for variables a-z, a%-z% and a$-z$ regardless of whether they got used, so that 'a' has the same address in every program) Forgetting about optimization means that, for example a = a + 1 a = 2 * a would compile to load a add 1 store a load a mul 2 store a , independently of where it appears in the program. That makes your compiler consist of two steps: - compute a map mapping line number to generated code for that line - fix up the targets of goto's (in the first version, don't bother about trying to use short jumps; just assume all jumps will be long) Inefficient? Yes, but make it work first, then make it fast (or skip that, as, frankly, if you want something for use in the real world, you should try and build on the likes of LLVM) Don't think that's cheating; it gives you around a tenfold speed up over a basic interpreter, and back then, people sold compilers doing the above. If you want advanced functions such as sin, do not hesitate to call into an external library. Those compilers from the '80s weren't afraid to call into ROM code, either.

jfoutz 10y ago
This is a great approach. I'd probably advise adding lexical scoping, because managing the stack is pretty interesting. Going from source to binary on your own code is incredibly satisfying and incredibly enlightening. It thoroughly drives out any "magic" in your mental model of computation. I agree wholeheartedly use LLVM (or something like it) for anything real. tens or hundreds of thousands of hours, by really smart people, gives you optimizations a lone wolf can never duplicate.
stevekemp 10y ago
That's a great suggestion. I went one step lower and wrote a (perl-based) virtual-machine. As you suggested I did the bare minimum at first, for example when I see labels I just remember their locations. Later on I patch up the offsets in the code, to make jumps to them point to the correct location. The project seems reasonably popular, for reasons that I don't understand, but it is very simple: https://github.com/skx/simple.vm https://github.com/skx/simple.vm

nickpsecurity 10y ago

Check out the QBE backend as it's designed for simplicity: http://c9x.me/compile/ http://c9x.me/compile/ Note: You could both target and learn from QBE potentially. ELF: http://www.cirosantilli.com/elf-hello-world/ http://www.cirosantilli.com/elf-hello-world/

Sir_Cmpwn 10y ago

I often work on tangental projects to understand problem spaces more. Try writing a mini libc, for example, with a dynamic loader. Try writing a linker and an assembler.

zura 10y ago

One would say Compilers is a multi-disciplinary field. You might enjoy some topics more than others. E.g. I personally favor stages after the parsing and before the actual code gen. :)

wfunction 10y ago

Are you talking about compilers, or just ("dumb") interpreters? To me, the hardest part of writing a compiler is the middle part that you totally neglected to mention: the static analysis & optimization. Not the parsing or the codegen.

jpolitz 10y ago

Plug for my compilers course, which is incremental and uses some of the ideas from sibling comments re: emitting assembly and Ghuloum's great work. Last time I posted it on HN, someone got back to me in a few weeks that they'd successfully gone through the assignments, so it seems at least somewhat concretely useful: https://www.cs.swarthmore.edu/~jpolitz/cs75/s16/ https://www.cs.swarthmore.edu/~jpolitz/cs75/s16/

akkartik 10y ago
Thanks! I'm gonna check it out.

webkike 10y ago

Well, it's the reason separation of concerns exist. You don't have to know all of the requirement to begin writing something real world, depending on what you mean by "real world". If you're trying to rewrite a feature complete GCC from scratch you're going to have to start somewhere and you won't be able to write everything from the start. So you divide the work in pieces and focus on each individually. Start out dumping assembly. If you really want to custom write ELF files that's fine but no place to start.

devwastaken 10y ago

Unrelated, but how would one get started creating a proper parser for textual content? For example, I have { "key" { "key" "value" "morekeys" { "key2" "value2" } } } The markup would be seperated by newlines, with the key-value pairs on the same line, always in quotes. I've solved it with regex and a crude parser before, but I've always heard of things like Bison and such but never found a 'good' way to impliment a real parser in a language like Python.

userbinator 10y ago
I would go with a simple recursive descent parser, unless you are interested in learning a DSL, the intricacies of the parsing algorithm your particular parser generator uses, and willing to debug one --- IMHO not worth it. Even "real", production-quality compilers like GCC, Clang, MSVC, and ICC use recursive-descent; and some, like GCC, switched away from parser generators.
- david-given 10y ago
  Parser generators work really well for context-free grammars, but as soon as you start needing context-sensitive lexing (like C does) you enter World Of Pain time. And they avoid having to deal with lookahead, which is always messy in hand-written parsers. But I think I'd agree that writing a recursive descent parser from scratch is probably the best way to learn about parsing; at least for a simple grammar. BTW, fun fact: it turns out that BNF was invented by an Indian linguist called Pāṇini about 2500 years ago, in order to parse Sanskrit. https://en.wikipedia.org/wiki/P%C4%81%E1%B9%87ini https://en.wikipedia.org/wiki/P%C4%81%E1%B9%87ini
akkartik 10y ago
To elaborate on userbinator's comment, you want to think of your format as a set of definitions: A clause consists of a '{', one or more key-value pairs, and a '}'. A key-value pair consists of a string and a value. A value is either a string or a clause. Now turn each definition into a function. Here's a nice-looking article from Googling for "writing a recursive descent parser": http://weblog.jamisbuck.org/2015/7/30/writing-a-simple-recursive-descent-parser.html http://weblog.jamisbuck.org/2015/7/30/writing-a-simple-recur...

readittwice 10y ago

True, but if you are willing to use some libraries or tools you can get pretty far. And if not, use them too :) you could always replace them later with your own tools. IMHO you need to decide on what part of the compiler you want to focus on. You mentioned you already know how to write a lexer and parser. So maybe you should start with an IR like WebAssembly you could compile. Maybe you could even reuse your lexer/parser from your interpreter. Compiling can be as simple as writing an interpreter, you "just" have to replace some code in the interpreter with `printf`s, that dump e.g. LLVM IR or Assembly. Then use LLVM or any assembler to get a binary. Even GCC basically works that way, gcc just dumps an assembly file and then passes it to assembler and linker. So GCC doesn't really emit ELF or Mach-O either, so don't let that stop you. That doesn't mean you don't have a "full" compiler. If you don't know assembly use tools like gcc.godbolt.org to see what code gcc generates. The most important thing: Think what code to generate for each feature of your language or IR. If you have figured that out all the rest will be trivial. For example: What code to generate for `if`? So don't try to compile a language with many fancy features at first and please don't try to generate fast code. You want a translation that works in every case, although it might be somewhat inefficient compared to `gcc -O3`. Your first program to compile could be something like `int main() {}`. If you can compile and execute this program, you can start to add features. This are the restrictions I would make at the beginning: * use a statically typed language, it is easier to generate (faster) code for that * start with global variables, add local variables later * support if, while and then functions (in this order) * only support few datatypes: int, int-array/pointer and string literals for printing. This should be enough to run the benchmarks binarytrees and fannkuch from The Computer Language Benchmark Game. You will already beat many dynamically typed and interpreted languages for those. Don't try to generate fast code at first, spill everything onto the stack so you don't have to care about register allocation. Even the V8 full-codegen jit works this way, so you don't have to be ashamed of it ;) If you don't care about ELF, linking and stuff you could also avoid this by writing a JIT-Compiler: Just emit code into some buffer and then directly start to execute. Although I have to admit that a JIT can introduce some challenges of its own. Ah and don't forget to write tests. Write a lot of tests from the beginning. Testing a compiler is pretty simple and is is also easy pretty easy to introduce subtle bugs. You will save a lot of time.