Category Archives: Compilers

New DFA/LALR compiler stuff in Ruby

Just put the following into the README for my new GitHub project, which is basically the DFA/LALR core of compiler framework. I think it just about sums up everything you need to know. 🙂

This is one of those bugs that bites me from time to time. I find myself wanting to design my own parser/compiler for something. Then I decide I don’t like any of the available parser/compiler frameworks, and I want to design one of my own. For some reason, I decide recursive descent is too wimpish. (even though it’s used by GCC now…)

Well, that’s not the point. If you’re going to do it yourself, you might as well bite the bullet and do it the hardest way possible.


And yes, I know Ruby has things like String#scan, but that’s NFA, dammit! Non-deterministic Finite Automata. If people have gone to all sorts of lengths to make DFAs optimal and Deterministic, there must be something in it! (maybe 50-odd years ago, I know…)

And yes, it’s true, I haven’t checked to see whether there already is something like this out there for Ruby. Except that I know there is at least one NFA/recursive-descent based framework already (TreeTop). Which is probably perfectly fine for any conceivable purpose. I’m just insane.

Seriously, this isn’t really finished. It needs a good facade or two built around it, and then a couple of command-line tools perhaps…



Leave a comment

Filed under Compilers