Support zero-width lookahead
pczarn opened this issue · 0 comments
pczarn commented
Earley parsing is breadth-first with respect to ambiguity. It is unclear how zero-width lookaround could work breadth-first, if at all. In cases where the zero-width group is shorter or the same length as the rest of the rule, the signal to block the rule's completion can be stored and accessed later. However, when the zero-width group is longer than the rest of the rule, the parser would need to kill threads that have moved on.
Instead, enter zero-width groups depth-first. Once they complete, rewind the Earley table. This affects the worst-case complexity.