Experimental parser: cleanup dfa.py

tools/lexer_generator/dfa.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 13 matching lines @@
 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 from itertools import chain
 from automaton import *
 from transition_keys import TransitionKey
 
 class DfaState(AutomatonState):
 
-  def __init__(self, name, action):
+  def __init__(self, name, action, transitions):
     super(DfaState, self).__init__()
     self.__name = name
-    self.__transitions = {}
+    self.__transitions = transitions
     self.__action = action
     assert isinstance(action, Action)
 
   def name(self):
     return self.__name
 
   def action(self):
     return self.__action
 
-  def add_transition(self, key, state):
-    assert key != None
-    assert not key == TransitionKey.epsilon()
-    assert not self.__transitions.has_key(key)
-    self.__transitions[key] = state
-
-
   def epsilon_closure_iter(self):
     return iter([])
 
   def transition_state_for_key(self, value):
     matches = list(self.transition_state_iter_for_key(value))
     assert len(matches) <= 1
     return matches[0] if matches else None
 
   def key_state_iter(
     self,
     key_filter = lambda x: True,
     state_filter = lambda x: True,
     match_func = lambda x, y: True,
     yield_func = lambda x, y: (x, y)):
     for key, state in self.__transitions.items():
       if key_filter(key) and state_filter(state) and match_func(key, state):
         yield yield_func(key, state)
 
 class Dfa(Automaton):
 
+  @staticmethod
+  def __add_transition(transitions, key, state):
+    assert key != None
+    assert not key == TransitionKey.epsilon()
+    assert not transitions.has_key(key)
+    transitions[key] = state
+
   def __init__(self, encoding, start_name, mapping):
     super(Dfa, self).__init__(encoding)
     self.__terminal_set = set()
     name_map = {}
     for name, node_data in mapping.items():
-      node = DfaState(name, node_data['action'])
-      name_map[name] = node
+      transitions = {}
+      node = DfaState(name, node_data['action'], transitions)
+      name_map[name] = (node, transitions)
       if node_data['terminal']:
         self.__terminal_set.add(node)
     for name, node_data in mapping.items():
-      node = name_map[name]
+      (node, transitions) = name_map[name]
       inversion = {}
       for key, state in node_data['transitions'].items():
         if not state in inversion:
           inversion[state] = []
         inversion[state].append(key)
       for state, keys in inversion.items():
         merged_key = TransitionKey.merged_key(encoding, keys)
-        node.add_transition(merged_key, name_map[state])
-    self.__start = name_map[start_name]
+        self.__add_transition(transitions, merged_key, name_map[state][0])
+    self.__start = name_map[start_name][0]
     self.__node_count = len(mapping)
     self.__verify()
 
   def __verify(self):
     assert self.__terminal_set
     state_count = self.visit_all_states(lambda state, count: count + 1, 0)
     assert self.__node_count == state_count
 
   def node_count(self):
     return self.__node_count
@@ skipping 68 matching lines @@
     initial_partitions = {}
     terminal_set = self.__dfa.terminal_set()
     all_keys = [] # Will contain all TransitionKeys in the dfa.
 
     # f fills in initial_partitions, id_to_state and all_keys.
     def f(state, visitor_state):
       state_id = len(id_to_state)
       id_to_state[state_id] = state
       action = state.action()
       all_keys.append(state.key_iter())
-      if action:
-        if state not in terminal_set:
-          # Match actions are valid only if we have matched the whole token, not
-          # just some sub-part of it.
-          assert not action.match_action()
-          key = ("nonterminal action", action)
-        else:
-          key = ("terminal action", action)
-      elif state in terminal_set:
-        key = ("terminal set",)
+      if state in terminal_set:
+        key = ("terminal set", action)
       else:
-        key = ("nonterminal set",)
+        # Match actions are valid only if we have matched the whole token, not
+        # just some sub-part of it.
+        assert not action.match_action()
+        key = ("nonterminal set", action)
       if not key in initial_partitions:
         initial_partitions[key] = set()
       initial_partitions[key].add(state_id)
     self.__dfa.visit_all_states(f)
     partitions = set()
     working_set = set()
 
     # Create StatePartition objects:
     for k, p in initial_partitions.items():
       p = StatePartition(p)
@@ skipping 175 matching lines @@
           elif len(intersection) <= len(difference):
             working_set.add(intersection)
           else:
             working_set.add(difference)
         if old_partitions:
           partitions -= old_partitions
         if new_partitions:
           partitions |= new_partitions
     (start_name, mapping) = self.__create_states_from_partitions(partitions)
     return Dfa(self.__dfa.encoding(), start_name, mapping)