This is amazingly elegant and concise. I've heard a lot of people, including the compiler academics, claim that even the simplest non-optimising compiler for x86 would be extremely complex; this is a great counterexample to that, alongside (O)TCC. It looks like it's using mainly two registers only for code generation, eax and ecx, and the stack.
Jack Crenshaw's "Let's build a compiler" tutorial series uses the same code generation method but with eax/edx (http://www.pp4s.co.uk/main/tu-trans-comp-jc-intro.html ); not sure if he was the first one to come up with it, however. Incidentally, I think his tutorial series is one of the best ones I've read for understanding how compilers work, even better than all the "traditional" literature like the Dragon Book.
The other article that'll probably be very helpful for those understanding how the rest of this compiler works is http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing which describes the "precedence climbing" way of parsing expressions.
Compilers are often thought of as "magic" that only very few people can understand, but I don't think that has to be true in general. While "production-quality" compilers like gcc are certainly very complex, the essence of a compiler is really quite simple. However, this wouldn't be the impression one gets by reading a lot of the compiler books out there --- the heavy emphasis on theory in the majority of them has a somewhat obfuscating effect. They also tend to focus a lot more on compiler-compilers (Lex, Yacc) and more general parsing techniques like LR, while spending very little on the simple methods of syntax-directed translation and recursive descent. AFAIK precedence-climbing is not even described in the Dragon Book.
I've never seen precedence climbing in any compiler textbook, unless you count the lcc book. (I learned of it instead from an unconventional algorithms class by Dave Gillespie, who wrote Gnu Calc.) You can see how it gets squeezed out of the curriculum since you can write a conventional parser just fine without it, but it's a loss -- when you see it how can you not go "Oh yes, that's sweet, that's just right"?
Crenshaw's series turned me off when the first parser he showed would incorrectly accept incorrect inputs, and it could've been done rightly just as easily -- or so it looked to me. I did not test it or read further, and since it's so often recommended I seem to've missed something.
Incidentally, I think his tutorial series is one of the best ones I've read for understanding how compilers work, even better than all the "traditional" literature like the Dragon Book.
Totally agree. I was interested in how compilers work when in high school - long before I heard of the dragon book and had no idea how to even start on making a parser and code generator.
When he walked through a basic recursive descent parser, it was like a light bulb went off over my head - such a simple and elegant solution to a otherwise seemingly tricky problem.
Allowing it to call arbitrary functions using dlopen()/dlsym() would be the idea I have for fixing the first problem - it'd also increase its power substantially since it can then make use of any other library's functions instead of the currently hardcoded list. Supporting function pointers would be a bit harder and involve changing the parser/code generator.
How would you tell it which shared library to dlopen?
Was looking into changing the order of arguments to go the right way 'round. Also changing address refs to be PC-relative, to avoid the relocation phase. Seems pretty straightforward.
This greatly helped my understanding of how compilers work.
How different would the implementation be for x64? Would it primarily be a matter of translating opcodes and calling conventions? For example, pop ecx is 59 [1], and on x64 it looks like it would be pop rcx, which is also 59 [2][3].
For x64 under both *nix and Windows sizeof(int) remains at 4 while the sizes of pointers increase to 8 bytes (64 bits), so anything in the compiler that depends on those sizes would also have to change. As for the opcodes, with x86/x64 it's a little weird since 64-bit mode actually defaults to 32-bit data sizes and uses mostly the same opcodes as 32-bit mode, with a prefix byte needed to override this to 64 bits. Addresses default to 64 bits, however. The 32-bit environment is "nice" in that pointers and integers are the same size; not true for most 64-bit in general (http://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_mo... )
But still, trying to fit the x64 version in 64 lines is probably going to be the harder problem. ;-)
Aside from 'dmytrish (the author of this fork)'s point about the code generator: this is extraordinarily tight C code. There's no fat on it anywhere, unless you want to call support for the ternary operator "fat". It's not obfuscated or artificially shrunk down at all. It's just sort of perfect.
I took an hour to read through it and comment the hell out of it, and it was some of the most pleasant reading I've done all year. I really, really like this code.
I meant the code generator size: it starts at line 448 and ends at 535, so its size is about 86 lines. The rest of the code is taken from original c4 and is not changed.
..and SNAP! Great work, dmytrish. This is a godsend to people trying to fight their way through traditional compiler texts. Thanks for a truly impressive contribution to the language dev world.
Jack Crenshaw's "Let's build a compiler" tutorial series uses the same code generation method but with eax/edx (http://www.pp4s.co.uk/main/tu-trans-comp-jc-intro.html ); not sure if he was the first one to come up with it, however. Incidentally, I think his tutorial series is one of the best ones I've read for understanding how compilers work, even better than all the "traditional" literature like the Dragon Book.
The other article that'll probably be very helpful for those understanding how the rest of this compiler works is http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing which describes the "precedence climbing" way of parsing expressions.
Compilers are often thought of as "magic" that only very few people can understand, but I don't think that has to be true in general. While "production-quality" compilers like gcc are certainly very complex, the essence of a compiler is really quite simple. However, this wouldn't be the impression one gets by reading a lot of the compiler books out there --- the heavy emphasis on theory in the majority of them has a somewhat obfuscating effect. They also tend to focus a lot more on compiler-compilers (Lex, Yacc) and more general parsing techniques like LR, while spending very little on the simple methods of syntax-directed translation and recursive descent. AFAIK precedence-climbing is not even described in the Dragon Book.