You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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?
The text was updated successfully, but these errors were encountered:
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.
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.
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?
The text was updated successfully, but these errors were encountered: