One of the things I wanted to do involves having a parser generated from a grammar, similar to YACC.

But I need the code generated in Objective C. And I need a parser that is re-entrant, so it can be run in a separate thread.

Now there are a number of solutions out there. But what I want is an LR(1) or GLR based parser built via a state machine which can be incorporated into Xcode and which generates Objective C code that can be used in an iPhone or iPad.

And let’s be honest, a lot of advise out there is really fucking stupid. Like this:

Code generation is not the “true way” in dynamic languages like Objective-C. Anything that can be achieved by a parser generator can be achieved at runtime. So, I’d suggest you try something like ParseKit, which will take a BNF-like grammar, and give you various delegate hooks you can implement to construct your parser.

That sound you just heard was my eyes rolling.

The reason, by the way, why you may wish to precompile a grammar rather than compile it at runtime is because generally (a) your grammar won’t change, and (b) the more computational time you can use evaluating the grammar, the more compact the grammar can be that you generate.

So without any real good solutions I thought how hard can it be to roll my own?

Well, fairly hard, mostly because the documentation out there for constructing LR(1) grammars sorta sucks.

So I started writing a document that attempts to describe the LR parsing algorithms out there in sufficient detail to roll my own YACC-like parser.

I haven’t quite figured out the GLR grammar parsing techniques in “Efficient Parsing for Natural Language, so it hasn’t been included yet.

But the rest should be there.

And sadly the whole thing grew to 66 pages in length, even without the GLR stuff.

This is a preliminary version, of course. Eventually I plan to upload all this to my GitHub account.