I’ve been working on a Ruby implementation of an NFA. I think it’s working! I’ve only implemented the concatenation, union/alternation, kleene star, optional, and one-or-more operators. It currently operates as a state graph. I’m trying to figure out how to implement intersection and subtraction. I haven’t figure those out yet. Ragel’s user manual and source code have given me several ideas on how to implement these operators in my NFA. I’ve been trying to design my NFA much like the implementation presented at http://swtch.com/~rsc/regexp/regexp1.html. I think it’s safe to say that my implementation is not nearly as attractive as the one presented there. It’ll get better though.