Introduce cut marker optimization #19

Open
sirthias opened this Issue Apr 22, 2011 · 0 comments

Comments

Projects
None yet
1 participant
Owner

sirthias commented Apr 22, 2011

Essentially this optimization will allow for "early exits" in FirstOf rules.

Consider this example

FirstOf(
    Sequence(A(), B(), C()),
    Sequence(A(), D())
)

Currently parboiled will try the second alternative in all cases where the first alternative failed.
However, if the first alternative already matched A and B and only failed at C the second alternative would not actually need to be tried since the already matched A B is not a prefix of the second alternative.
This analysis can be done statically after rule tree generation and so called "cut markers" can be introduced at all points, where FirstOf alternatives have matched far enough to become "non-prefixes" of all following alternatives.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment