]> granicus.if.org Git - re2c/commit
Explicitly track order of closure items for leftmost disambiguation.
authorUlya Trofimovich <skvadrik@gmail.com>
Thu, 16 Mar 2017 22:39:57 +0000 (22:39 +0000)
committerUlya Trofimovich <skvadrik@gmail.com>
Fri, 17 Mar 2017 08:25:24 +0000 (08:25 +0000)
commit7944e063631c3d61cb852c653a5e6c7fb2ddaf6b
treee576df69f4cb684004e46f6d58b7c4cdd022a36e
parent685c038d464cbb962866898b87b892f0396ca499
Explicitly track order of closure items for leftmost disambiguation.

Before this commit leftmost order was maintained implicitly by construction
of closure: NFA is traversed in left-first order, so the earliest item added
to closure is also the leftmost. Special care was taken to preserve this
order and never rearrange closure elements.

This is convenient if leftmost disambiguation strategy is the only one.
However, other strategies require explicit bookkeeping of disambiguation
information (POSIX needs tag history for orbit tags, maximize/minimize
needs most recent tag versions). Implicit handling of leftmost strategy
does not fall in line with other strategies.

By tracking leftmost order explicitly we achieve several goals:
    - uniform handling of disambiguation strategies
    - DFA states can be treated as good old sets again, which is more
      conventional and means less work for minimization

POSIX tests changed (but the '/test/posix_captures/.run/__run.sh' script
still passes all tests) because there was an error in the order items were
added to closure, which probably prevented minimization (if the new item
dominated the existing one, the old one was substituted with the new one,
while it should have been removed and the new one appended at the end).

Skeleton tests changed because the order of NFA states in DFA state does
not matter, so more states can be merged by determinization.
15 files changed:
re2c/src/dfa/closure.cc
re2c/src/dfa/closure.h
re2c/src/dfa/determinization.cc
re2c/src/dfa/dump.cc
re2c/src/dfa/dump.h
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/posix_captures/basic/19.i--flex-syntax.c
re2c/test/posix_captures/basic/20.i--flex-syntax.c
re2c/test/posix_captures/categorize/02.i--flex-syntax.c
re2c/test/posix_captures/repetition/80.i--flex-syntax.c
re2c/test/posix_captures/repetition/81.i--flex-syntax.c
re2c/test/posix_captures/repetition/90.i--flex-syntax.c
re2c/test/posix_captures/repetition/91.i--flex-syntax.c