Use SPPF-style structure

[tjvr]

Switch to using an SSPF-style internal structure, similar to @joshuagrams's pint-sized Earley Parser.

This lets us:

• Avoid running unnecessary postprocessors #33 (predicates are a separate issue)
• Not output an exponential number of parses for ambiguous things #53
• Implement operator precedence in a nice way #81 (actually I think we could do this anyway)
• Produce a parse forest as output, should anyone want such a thing...?

This would also:

• Avoid adding duplicate states to tables #22
• I believe it's possible to do some aggressive GC / wantedBy optimisation to reduce memory usage when parsing a very long file #31 (it's possible we could do this anyway)

[tjvr]

It seems that postprocessors are going to be a blocker for this. :(

[tjvr]

We've made lots of performance gains particularly in #171. I'm no longer convinced SPPF is a massive win here. We'd have to drop support for predicates, and the only real advantage is you get a full parse forest (rather than a list of possible parses, which is the exponential in the number of ambiguities).

What do you think @hardmath123? :-)

[kach]

Hmm, yeah, I suppose so — it might not be worth the effort. But I'd leave the issue open anyway, regardless of what you decide, because someone-in-the-future might want to try it out to see what would happen. :-)

[heatherleaf]

Just crashing the party... I wrote some parsing papers a while ago, perhaps one or two of them could be interesting?

Ljunglöf & Wirén (2010) Syntactic Parsing. Handbook of Natural Language Processing Ljunglöf (2008) Transition-based parsing. Swedish Language Technology Conference Ljunglöf (2003) An Abstract View of Generalized LR Parsing. Nordic Workshop on Programming Theory Ljunglöf (2002) Pure Functional Parsing. Licenciate thesis

You can download all of them from here: http://www.cse.chalmers.se/~peb/bibliography.html

(Sorry for the spamming, but perhaps there's something interesting somewhere there)

[kach]

Hey, thanks for the links! It's not spam at all — it's actually really nice to have clean, academic references for what we're doing.

By the way, Section 4.9 in Ljunglöf & Wirén (2010) Syntactic Parsing. Handbook of Natural Language Processing was especially fascinating. It reminds me of a post by Jeffrey Kegler, over here (x/posted in brief over here).

[heatherleaf]

Thanks for the timeline -- I haven't seen that before.

[erezsh]

Just to chime in with my own 10 cents: I re-implemented Earley in Lark with a parse-forest. It's actually relatively simple to add. The idea is to build a tree structure normally, at the same points that you currently use for callbacks. But when a rule is completed more than once, you need to insert an "ambiguity branch". My implementation is here: https://github.com/erezsh/lark/blob/master/lark/parsers/earley.py I'll be happy to walk you through my solution if it helps.