]> granicus.if.org Git - re2c/commit
Remove useless final states; calculate fallback states more accurately.
authorUlya Trofimovich <skvadrik@gmail.com>
Mon, 23 May 2016 21:07:00 +0000 (22:07 +0100)
committerUlya Trofimovich <skvadrik@gmail.com>
Mon, 23 May 2016 21:27:20 +0000 (22:27 +0100)
commitf51403dc4a79242b812ed9e51f4dc94fc9790256
treec7169b5eccc60e91cedbc7787b68fbe6e1042cb7
parent1478ee98f93719a8d1b592a35a647c293e8b0c65
Remove useless final states; calculate fallback states more accurately.

Removing useless final states allows some further optimizations
which would otherwise be impossible (see the changed tests for
example).

However, removing useless final states revealed previously hidden
defects in calculating fallback states: in some tests spurious
new 'yyaccept' values appeared. It turned out that we used incorrect
(imprecise, too pessimistic) algorithm to calculate fallback states:
the given state was considered to be fallback state if it was final
and had transitions to non-default and non-final states. This
algorithm erroneousl captures cases when all paths from the given
state are accepting and long enough (longer than one transition).
The new algorithm to find fallback states uses information obtained
by rule liveness analyses (reachability of "none-rule" in particular).

Some important tests changed a lot; skeleton says the changes are
correct (as well as manual looking into the changes).
31 files changed:
re2c/Makefile.am
re2c/src/ir/adfa/adfa.cc
re2c/src/ir/dfa/dead_rules.cc
re2c/src/ir/dfa/dfa.h
re2c/src/ir/dfa/fallback.cc [deleted file]
re2c/src/ir/dfa/tag_deduplication.cc
re2c/test/bug60_redundant_yymarker.ci.c
re2c/test/default_dup_star_1.ic.c
re2c/test/input4.--empty-class(match-empty).c
re2c/test/input4.c
re2c/test/input6.--empty-class(match-empty).c
re2c/test/input6.c
re2c/test/php20150211_pdo_sql_parser.ig--skeleton.c
re2c/test/php20150211_pdo_sql_parser.ig.c
re2c/test/php20150211_pdo_sql_parser_trimmed.ig--skeleton.c [new file with mode: 0644]
re2c/test/php20150211_pdo_sql_parser_trimmed.ig--skeleton.re [new file with mode: 0644]
re2c/test/php20150211_pdo_sql_parser_trimmed.ig.c [new file with mode: 0644]
re2c/test/php20150211_pdo_sql_parser_trimmed.ig.re [new file with mode: 0644]
re2c/test/php20150211_zend_ini_scanner.c--emit-dot--flex-syntax--case-inverted.c
re2c/test/php20150211_zend_ini_scanner.igcd--flex-syntax--case-inverted.c
re2c/test/php20150211_zend_ini_scanner.igcd--skeleton--flex-syntax--case-inverted.c
re2c/test/php20150211_zend_ini_scanner_trimmed.ic--flex-syntax.c
re2c/test/php20150211_zend_ini_scanner_trimmed.icwb--flex-syntax.c
re2c/test/segfault_full_range_star.bi.c
re2c/test/segfault_full_range_star_startlabel.ci.c
re2c/test/segfault_full_range_star_startlabel.i.c
re2c/test/segfault_full_range_star_startlabel2.ci.c
re2c/test/segfault_full_range_star_startlabel2.i.c
re2c/test/tags/dedup2.i--input(custom).c
re2c/test/tags/dedup2.i.c
re2c/test/wunreachable_rules.i.c