2 replies to this topic

[laztrezort]

I'm trying to implement an Earley parser (in C#), as described here: http://en.wikipedia....i/Earley_parser.

Unfortunately, parser theory is far beyond my comfortable knowledge zone, so I'm wondering if anyone here has done something like this before.

I've managed to put together a working recognizer (which is basically what the linked algorithm describes), and it seems to produce the charts accurately. Where I'm coming up short is how to translate the chart into a parse tree (or forest, since I'll eventually be working with ambiguous grammars).

My searching has revealed mostly thesis papers and such, which are beyond my understanding. If anyone has a good link or other recommendation that would help, please share. Worse case, I suppose I can purchase a book on compiler/parser theory, and start self-teaching, but at the moment this looks rather daunting - I'd also certainly appreciate any book suggestions of the sort that can be considered "accessible".

thanks!

[jwezorek]

The wikipedia article links to two C implementations and three Java implementations. Take a look at all them. Find the one you like the best, compile it, play around with it, make sure it works, etc. And then port it to C#. Anyway, that's probably what I'd do in your situation.

[laztrezort]

Good point, looks like at least one of the Java implementations isn't too much of a mess. Good excuse to learn some Java, anyway.