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.

https://stackoverflow.com/questions/4931346/how-to-output-the-ast-built-using-antlr

https://tomassetti.me/domain-specific-languages/#textual_languages

Top Down

I could just calm the fuck down and use a top-down parser. Sure, I can't do left recursion, but it's easy to write a grammar to avoid it. And I could start experimenting with using the parser before writing a bottom up parser.

I think I'll do this for now and keep working on the FA stuff and eventually build a shift-reduce parser.

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.

This https://github.com/pointlander/peg could be an example, but it's build as a damn CLI instead of pulling the guts into a package. I might fork it and do a pull request.

Hrm... looks like it still can't handle left recursion. I kind of want that.

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.