Parser

I want to build a generic context-free Parser in Go.

I've already built a lexer, though it may need some work.

I build a top down parser, but it only produces an equivalent parse tree, which doesn't quite work and I haven't been able to figure out how to convert it back to the actual parse tree.

I'm not very worried about efficiency, at least not right now.

FA

I really should build a DFA/NFA library. I started on one, but it ends up more complicated than one would expect.

In Go the real tough part is that I'd like to be able to handle different node/transition types (string/rune, int/int, int/rune) but that gets kind of tricky. I could treat everything as []byte and use crc32 vals for keys in maps.

If I had this, I could build a light weight regex library which would be great for the lexer.

Packrat Parser

A variant of top down.

Bottom Up

This is a whole class of parser, most of which use FA.

CYK

This algorithm looks pretty simple, but it requires that notation be in Chomsky Normalized Form, A → BC or A → α, but it might be easier to do something like this:

 A → BCDE
 To
 A → A1A2
 A1 → BC
 A2 → DE

or

 A → BCD
 A → A1A2
 A1 → BC
 A2 → DA0
 A0 → ε

And then write a corresponding routine to recover the original parse tree.