This is old news, but I'm thinking of getting into the next stage of this project. My "state table only" parser started passing all 70 of its test-cases some time in the middle of this year.

I've just been too busy to blog about it. I'm getting a few things out of the way before some other projects shift into gear.

Or for something more amusing...

http://blog.metawrap.com/blog/content/binary/MetaWrap/Parser/test66.dot.png

I'll be applying this to real time XML schema parsing and validation, GL shader construction, protocol generators and data-flow based computing.

My algorithm builds a near optimal state transition table in one pass - the next step is adding some of the standard modifiers such as the Kleene Closure and other standard EBNF unary operations. The KC will be the hardest because its at the root of one of the hardest greedy grammar problems.

( a | b )* abb

The others will be fairly trivial. My KC solution will not be perfect; I'm limiting myself on purpose. Its not my aim to end up with yet another general solution. I want the fastest for my problem space. I'm limiting myself to grammars that don't contain the ambiguities that lead to greediness. My theory is that they don't end up in real world situations often, if they do they can be worked around by a simple re-factoring, or are sign that the grammar is messy.

 More about this in previous posts on the topic.