Experimental parser: Abstact state matching

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 20 matching lines @@
 
 class DfaState(AutomatonState):
 
   def __init__(self, name, action):
     super(DfaState, self).__init__()
     self.__name = name
     self.__transitions = {}
     self.__action = action
     assert isinstance(action, Action)
 
-  def transitions_to_multiple_states(self):
-    return False
-
   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 transitions(self):
-    return self.__transitions
 
   def epsilon_closure_iter(self):
     return iter([])
 
-  # TODO abstract state matching
-  def __matches(self, match_func, value):
-    items = self.__transitions.items()
-    return [state for (key, state) in items if match_func(key, value)]
+  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 transition_state_iter_for_char(self, value):
-    return iter(self.__matches(lambda k, v : k.matches_char(v), value))
-
-  def transition_state_iter_for_key(self, value):
-    return iter(self.__matches(lambda k, v : k.is_superset_of_key(v), value))
-
-  def transition_state_for_key(self, value):
-    matches = self.__matches(lambda k, v : k.is_superset_of_key(v), value)
-    if not matches:
-      return None
-    # Since this is a dfa, we should have at most one such state. Return it.
-    assert len(matches) == 1
-    return matches[0]
+  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):
 
   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
@@ skipping 298 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)