]> granicus.if.org Git - re2c/commit
Restructured determinization algorithm DFA construction in a more canonical way.
authorUlya Trofimovich <skvadrik@gmail.com>
Mon, 26 Sep 2016 16:09:18 +0000 (17:09 +0100)
committerUlya Trofimovich <skvadrik@gmail.com>
Mon, 26 Sep 2016 16:09:18 +0000 (17:09 +0100)
commit101bad34f8a31a21a2a919f1109e1e9857e346b0
tree16eee5730e4bc3763045a933d8a33c4cfbf123a6
parent150c84722952f4163ba6e37650f69c362683c85e
Restructured determinization algorithm DFA construction in a more canonical way.

All textbooks describe determinization (powerset construction)
like this:

    S0 <- epsilon-closure of start NFA state
    add S0 to DFA
    while there is unmarked state S:
        mark S
        for each symbol X in the alphabet:
            R <- the set of NFA states reachable from S on X
            T <- epsilon-closure of R
            if T is not in DFA
                add T to DFA

In re2c the inner loop on alphabet symbols was split in two parts
and somewhat obfuscated; this commit makes re2c follow textbook
version more closely.
re2c/src/ir/dfa/determinization.cc