]> granicus.if.org Git - re2c/commit
Untwined determinization and '-Wnondeterministic-tags' analysis.
authorUlya Trofimovich <skvadrik@gmail.com>
Tue, 6 Dec 2016 13:35:07 +0000 (13:35 +0000)
committerUlya Trofimovich <skvadrik@gmail.com>
Tue, 6 Dec 2016 13:35:07 +0000 (13:35 +0000)
commit314eb5c705cf45b19b5637b7f2b6d58bc6909e28
tree262db64fed33fe852f8e6db1223d38a7fb12684c
parent064520e0f2720fc59f7008cebe524830d67ea414
Untwined determinization and '-Wnondeterministic-tags' analysis.

Now '-Wnondeterministic-tags' analysis is done right after determinization,
while we still have all the kernels available. Instead of comparing
transition tags (which are available in closure items, but not in kernels)
we now compare tag versions: maximum number of distinct versions per tag is
the desired degree of nondeterminism. Kernel items that belong to another
rule do not count (all tags that don't belong to a particular rule should
have initial versions in all items belonging to this rule).

Added test with an example of pathological regexp: counted repetition
cannot be folded efficiently in DFA, and combined with nondeterministic
tags it results in arbitrary long chains of reordering commands.
Length of command choin grows linearly with the number of repetitions
(as DFA itself does).
15 files changed:
re2c/src/conf/warn.cc
re2c/src/conf/warn.h
re2c/src/ir/dfa/closure.cc
re2c/src/ir/dfa/closure.h
re2c/src/ir/dfa/determinization.cc
re2c/test/tags/copy_save.i--tags.c
re2c/test/tags/counter1.i--tags.c [new file with mode: 0644]
re2c/test/tags/counter1.i--tags.re [new file with mode: 0644]
re2c/test/tags/nondet_cat1.--tags.c
re2c/test/tags/nondet_cat3.i.c
re2c/test/tags/nondet_cat4.--tags.c
re2c/test/tags/topsort1.i--tags.c
re2c/test/tags/topsort2.i--tags.c
re2c/test/tags/twopass.i--tags.c
re2c/test/tags/uniq.i--tags.c