]> granicus.if.org Git - re2c/commit
Stop loosing arcs in DFA loops when building path cover with --skeleton.
authorUlya Trofimovich <skvadrik@gmail.com>
Mon, 10 Aug 2015 11:03:07 +0000 (12:03 +0100)
committerUlya Trofimovich <skvadrik@gmail.com>
Mon, 10 Aug 2015 11:03:07 +0000 (12:03 +0100)
commit87c08466220673a429be0b5f2ff1bc0c37a85e39
treea692b04836becf6fce680072e4b001e8e78a714f
parentf5e9045c3ff1083695beb8da19277241bd50f8e2
Stop loosing arcs in DFA loops when building path cover with --skeleton.

The problem with the algorithm was that when one and the same skeleton
node is visited for the 3rd time, the algorithm would abandon this
branch and drop all the path prefixes that lead to it. It's ok when
bruteforcing all paths (the arcs in the dropped prefixes will occur in
other paths that lead to final states), but it's not ok for path cover:
some arcs may have occured only in these dropped prefixes).

The fix is easy: just check if the branch was cancelled and in case it
was try the same prefixes with another branch.

This small example demonstrates the problem:

    /*!re2c
        [^\x00]* [\x00] {}
    */

DFA skeleton looks like this:

    state 0:
        arcs to state 0: [0x01, 0xFF]
        arcs to state 1: [0x00]
    state 1: final

Before the fix, re2c would generate the following paths (provided
path cover construction is forced instead of generating all paths):

    - 0x01,0x00
    - 0x00

Clearly the [0xFF] arc looping from state 0 to state 0 is missing
(uncovered). After the fix:

    - 0x01,0x00
    - 0xFF,0x01,0x00
    - 0x01,0xFF,0x00
    - 0x00

Not a minimal path cover, but we don't need it. We just need a small
enough one.
re2c/src/codegen/skeleton/skeleton.cc