From 301ced0922e4e79291569b6117efd20780c9d5b8 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Tue, 15 Mar 2016 08:28:02 +0000 Subject: [PATCH] Added comments. --- re2c/src/ir/dfa/minimization.cc | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) diff --git a/re2c/src/ir/dfa/minimization.cc b/re2c/src/ir/dfa/minimization.cc index 8b6cc039..b15714c2 100644 --- a/re2c/src/ir/dfa/minimization.cc +++ b/re2c/src/ir/dfa/minimization.cc @@ -40,6 +40,7 @@ static void minimization_table( tbl[i + 1] = tbl[i] + i; } + // see note [distinguish states by contexts] for (size_t i = 0; i < count; ++i) { dfa_state_t *s1 = states[i]; @@ -83,6 +84,19 @@ static void minimization_table( } } + // Equivalence relation defined by the matrix is transitive + // by construction. Thus we can simply find the first state + // which is not distinguishable from current and choose it as a + // representative: all other states with the same representative + // have to be equivalent to current state due to transitivity. + // + // The only requirement is to deterministically choose the + // representative: e.g. always choose the one with the lowest + // index. + // + // Note that transitivity is crucial: without it the problem + // would be equivalent to the clique cover problem. + for (size_t i = 0; i < count; ++i) { part[i] = i; @@ -120,6 +134,7 @@ static void minimization_moore( size_t *next = new size_t[count]; + // see note [distinguish states by contexts] std::map, size_t> init; for (size_t i = 0; i < count; ++i) { @@ -197,6 +212,15 @@ static void minimization_moore( delete[] next; } +/* note [distinguish states by contexts] + * + * States that differ only in context set must still be distinguished + * otherwise contexts that start with iteration will be broken, e.g.: + * "" / "b"* {} + * because first iteration will be merged with other iterations + * causing context being saved on each iteration. + */ + void minimization(dfa_t &dfa) { const size_t count = dfa.states.size(); -- 2.40.0