]> granicus.if.org Git - re2c/commit
Avoid exponential blowup in tagged epsilon-closure construction.
authorUlya Trofimovich <skvadrik@gmail.com>
Tue, 16 May 2017 17:07:00 +0000 (18:07 +0100)
committerUlya Trofimovich <skvadrik@gmail.com>
Tue, 16 May 2017 17:46:08 +0000 (18:46 +0100)
commit51fe1a5b457c9af40bdcb7f8b5907af4c4b40223
tree36641019b66634d89b4a231ddeb19de21ec2c634
parent194d41a76ae68a23b515a6b74fd997b69de86cdc
Avoid exponential blowup in tagged epsilon-closure construction.

The previous algorithm waited until the full epsilon-path is built,
then compared it to already existing paths. The new algorithm compares
and merges partial epsilon-paths as soon as they arrive at the same
NFA state, so the overall number of paths is bounded by the number of
NFA states at all times.
re2c/src/dfa/closure.cc
re2c/src/dfa/closure.h
re2c/src/dfa/determinization.cc
re2c/src/dfa/dump.cc
re2c/src/dfa/find_state.cc
re2c/src/dfa/tagtree.cc
re2c/src/dfa/tagtree.h
re2c/src/nfa/nfa.h
re2c/test/posix_captures/exponential_epsilon_closure.i--posix-captures.c [new file with mode: 0644]
re2c/test/posix_captures/exponential_epsilon_closure.i--posix-captures.re [new file with mode: 0644]