News for hackers. Stuff that matters.
Re:c4x86 - JIT compiler for x86 in 86 lines by userbinator on Saturday December 13, 2014 @08:38PM (#8747166)
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.

Re:c4x86 - JIT compiler for x86 in 86 lines by abecedarius on Saturday December 13, 2014 @09:46PM (#8747284)
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.

P.S. precedence climbing in Python: https://github.com/darius/sketchbook/blob/master/parsing/pre... . Pratt's top-down operator precedence parsing is essentially an object-oriented way to express the same algorithm: https://github.com/darius/sketchbook/blob/master/parsing/pra...

Re:c4x86 - JIT compiler for x86 in 86 lines by statictype on Monday December 15, 2014 @09:16AM (#8752021)
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.