nitcc: add transformation from a NFA to a epsilonless NFA

Signed-off-by: Jean Privat <jean@pryen.org>

diff --git a/contrib/nitcc/src/autom.nit b/contrib/nitcc/src/autom.nit
index 0e9dc87..bec0f07 100644 (file)
--- a/contrib/nitcc/src/autom.nit
+++ b/contrib/nitcc/src/autom.nit
@@ -626,6 +626,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]