Direct access to compactly represented results for ambiguous grammars

[girving]

The README seems to imply that there's no way to directly traverse the DAG produced by highly ambiguous parses. That is, I'd like a polynomial time structure that compactly represents all possible parses so that I can manually filter the exponential size stream in polynomial time using dynamic programming.

Am I correct that this feature is currently missing?

[djspiewak]

You're correct that this feature is absent at present. Well, of a sort. It is possible to produce a DAG that represents the ambiguous parse forest simply by using immutable tree nodes and natural sharing, but this will not prune shared suffixes. As a result, any recursively ambiguous parse will result in a DAG with unnecessary nodes. Clearly this is not a good answer.

Unfortunately, I haven't been able to cleanly solve the problem of how to encode a proper SPPF in a functional, combinatorial style. Definitely open to suggestions here.

[girving]

Thanks, I'll let you know if I come up with anything. For the moment I'm trying to avoid digging into parser algorithms as much as possible, though I may have to if I can't find a nice GLR parser generator. It's a beautiful yak, but that's not a good reason to shave it.