]> granicus.if.org Git - re2c/commit
Changed disambiguation policy: leftmost rather than tag-centric.
authorUlya Trofimovich <skvadrik@gmail.com>
Mon, 13 Feb 2017 21:59:06 +0000 (21:59 +0000)
committerUlya Trofimovich <skvadrik@gmail.com>
Tue, 14 Feb 2017 09:42:32 +0000 (09:42 +0000)
commit919017a13d2f908a327e0d1442ba9f3c8039b3ef
treef63414f3322b8dae95bbb177e5ccdf68a0e895f6
parentab269c6970bcd7bbfcda49a88b96b188959c1986
Changed disambiguation policy: leftmost rather than tag-centric.

Instead of tracking priority for each tag version and resolving conflicting
configurations encountered by the epsilon-closure based on version priorities
(trying to minimize or maximize each tag), we now simply pick the leftmost
epsilon-path through the NFA.

NFA construction has to accommodate this policy: for example, greedy iteration
should be compiled so that always choosing the left alternative correpongs to
re-iteration, while choosing the right alternative corresponds to leaving the
iteration. The necessary adjustments have been done by earlier commit
03c65121da3f8bcb412576568cfff6cbca039470.

Now we can drop priority comparison when mapping TDFA states and stick to
simple bijection. This may add cycles in reordering commands. (Has not been
done yet.)

The rationale of switching to leftmost policy is this: with tag maximization/
minimization policy tags could influence the regexp: for example, regexp
    "a"* @p "a"*
has different meaning depending on whether tag 'p' is minimized (first iteration
is non-greedy) or maximized (first iteration is greedy). Moreover, adding
another tag with the opposite policy and higher priority would change the
meaning (suppose 'q' is minimized and earlier tags have higher priority):
    "a"* @q @p "a"*
This all makes regexps somewhat fragile, since adding just one tag may change
the whole regexp (and in the presence of other tags, it may change parse
results).

But even worse, with tag-centric disambiguation simple (untagged) subexpressions
are inferior to tagged ones. This contradicts intuition and even POSIX standard,
where  a*(a*)  is the same as  (a*)(a*) . We don't keep to POSIX (and we can't
because of last-longest instead of first-longest semantics of iteration as shown
by the  (<|<a|<ab|<aba|abab|baba|b>|>)*  example), but even this somewhat
tag-centric standard respects non-captured parts of the regexp. Note that
Laurikari in his TRE library has to do special preprocessing of the regexp in
order to assign correct minimization/maximisation direction to each tag
depending on the context of the tag. His original tag-centric policy (open tag
is minimized and has higher priority than closing tag which is maximized,
nested tags have lower priority) is insufficient to accommodate POSIX.
re2c/src/ir/dfa/closure.cc
re2c/src/ir/dfa/closure.h
re2c/src/ir/dfa/dump.cc
re2c/test/php20150211_var_unserializer.ig--skeleton.c
re2c/test/php20150211_zend_ini_scanner.igcd--skeleton--flex-syntax--case-inverted.c
re2c/test/php20150211_zend_language_scanner.igcd--skeleton--flex-syntax--case-inverted.c
re2c/test/tags/nondet_iter.--tags.c