Merge: Contract implementation

[nit.git] / contrib / nitcc / src / autom.nit

diff --git a/contrib/nitcc/src/autom.nit b/contrib/nitcc/src/autom.nit
index 2a97bd3..c771408 100644 (file)
--- a/contrib/nitcc/src/autom.nit
+++ b/contrib/nitcc/src/autom.nit
@@ -358,10 +358,14 @@ class Automaton
                        if not goods.has(s) then bads.add(s)
                end
 
-               # Remove their transitions
+               # Remove their transitions and tags
                for s in bads do
                        for t in s.ins.to_a do t.delete
                        for t in s.outs.to_a do t.delete
+                       if tags.has_key(s) then
+                               for t in tags[s] do retrotags[t].remove(s)
+                               tags.keys.remove(s)
+                       end
                end
 
                # Keep only the good stuff
@@ -386,10 +390,9 @@ class Automaton
 
                # split accept states.
                # An accept state is distinct with a non accept state.
-               for s1 in states do
+               for s1 in accept do
                        for s2 in states do
                                if distincts[s1].has(s2) then continue
-                               if not accept.has(s1) then continue
                                if not accept.has(s2) then
                                        distincts[s1].add(s2)
                                        distincts[s2].add(s1)
@@ -527,7 +530,7 @@ class Automaton
                                                f.append("s{names[s]}->s{names[s2]} [label=\"{labe.escape_to_dot}\"];\n")
                                        end
                                end
-                               if merge_transitions == null or merge_transitions == true then
+                               if merge_transitions or else true then
                                        f.append("s{names[s]}->s{names[s2]} [label=\"{labe.escape_to_c}\"];\n")
                                end
                        end
@@ -627,6 +630,58 @@ class Automaton
                return dfa
        end
 
+       # Transform a NFA to a epsilonless NFA.
+       fun to_nfa_noe: Automaton
+       do
+               assert_valid
+
+               trim
+
+               var dfa = new Automaton.empty
+               var n2d = new ArrayMap[Set[State], State]
+               var seen = new ArraySet[Set[State]]
+               var st = eclosure([start])
+               var todo = [st]
+               n2d[st] = dfa.start
+               seen.add(st)
+               while not todo.is_empty do
+                       var nfa_states = todo.pop
+                       #print "* work on {nfa_states.inspect}={nfa_states} (remains {todo.length}/{seen.length})"
+                       var dfa_state = n2d[nfa_states]
+                       for s in nfa_states do
+                               for t in s.outs do
+                                       if t.symbol == null then continue
+                                       var nfa_dest = eclosure([t.to])
+                                       #print "{nfa_states} -> {sym} -> {nfa_dest}"
+                                       var dfa_dest
+                                       if seen.has(nfa_dest) then
+                                               #print "* reuse {nfa_dest.inspect}={nfa_dest}"
+                                               dfa_dest = n2d[nfa_dest]
+                                       else
+                                               #print "* new {nfa_dest.inspect}={nfa_dest}"
+                                               dfa_dest = new State
+                                               dfa.states.add(dfa_dest)
+                                               n2d[nfa_dest] = dfa_dest
+                                               todo.add(nfa_dest)
+                                               seen.add(nfa_dest)
+                                       end
+                                       dfa_state.add_trans(dfa_dest, t.symbol)
+                               end
+
+                               # Mark accept and tags
+                               if accept.has(s) then
+                                       if tags.has_key(s) then
+                                               for t in tags[s] do
+                                                       dfa.add_tag(dfa_state, t)
+                                               end
+                                       end
+                                       dfa.accept.add(dfa_state)
+                               end
+                       end
+               end
+               return dfa
+       end
+
        # Epsilon-closure on a state of states.
        # Used by `to_dfa`.
        private fun eclosure(states: Collection[State]): Set[State]