Experimental lexer generator: transfer actions across epsilon transitions correctly when constructi…

tools/lexer_generator/nfa.py

 # Copyright 2013 the V8 project authors. All rights reserved.
 # Redistribution and use in source and binary forms, with or without
 # modification, are permitted provided that the following conditions are
 # met:
 #
 #     * Redistributions of source code must retain the above copyright
 #       notice, this list of conditions and the following disclaimer.
 #     * Redistributions in binary form must reproduce the above
 #       copyright notice, this list of conditions and the following
 #       disclaimer in the documentation and/or other materials provided
@@ skipping 315 matching lines @@
     name = ".".join(str(x.node_number()) for x in sorted(nfa_state_set))
     if name in dfa_nodes:
       return name
     dfa_nodes[name] = {
       'transitions': {},
       'terminal': end_node in nfa_state_set}
     for key in NfaState.gather_transition_keys(nfa_state_set):
       f = lambda acc, state: acc | state.key_matches(key)
       transitions = reduce(f, nfa_state_set, set())
       match_states = set()
-      actions = set()
+      actions = []
       for (state, action) in transitions:
         match_states.add(state)
         if action:
-          actions.add(action)
+          actions.append(action)
+
+        # Pull in actions which can be taken with an epsilon transition from the
+        # match state.
+        e = TransitionKey.epsilon()
+        if e in state.transitions():
+          for e_trans in state.transitions()[e]:
+            if e_trans[1]:
+              actions.append(e_trans[1])
+
       assert len(match_states) == len(transitions)
-      assert not actions or len(actions) == 1
-      action = iter(actions).next() if actions else None
+
+      actions.sort()
+      action = actions[0] if actions else None
       transition_state = Nfa.__to_dfa(match_states, dfa_nodes, end_node)
       dfa_nodes[name]['transitions'][key] = (transition_state, action)
     return name
 
   def compute_dfa(self):
     self.__compute_epsilon_closures()
     dfa_nodes = {}
     start_name = self.__to_dfa(set([self.__start]), dfa_nodes, self.__end)
     return (start_name, dfa_nodes)
 
@@ skipping 22 matching lines @@
 digraph finite_state_machine {
   rankdir=LR;
   node [shape = circle, style=filled, bgcolor=lightgrey]; S_%s
   node [shape = doublecircle, style=unfilled]; S_%s
   node [shape = circle];
 %s
 }
     ''' % (self.__start.node_number(),
            self.__end.node_number(),
            "\n".join(node_content))