Experimental lexer generator: rename_things(Dfa minimization) += comments

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 50 matching lines @@
     matches = reduce(f, self.__transitions.items(), set())
     # Since this is a dfa, we should have at most one such state. Return it.
     if not matches:
       return None
     assert len(matches) == 1
     return iter(matches).next()
 
   def next_state_with_char(self, value):
     return self.__matches(lambda k, v : k.matches_char(v), value)
 
-  def key_matches(self, value):
-    return self.__matches(lambda k, v : k.is_superset_of_key(v), value)
+  def transition_state_with_key(self, key):
+    # 'key' can be a subkey of one of the TransitionKeys for this state, but it
+    # cannot partially overlap a TransitionKey for this state.
+    return self.__matches(lambda k, v : k.is_superset_of_key(v), key)
 
 class Dfa(Automaton):
 
   def __init__(self, start_name, mapping):
     super(Dfa, self).__init__()
     self.__terminal_set = set()
     name_map = {}
     for name, node_data in mapping.items():
       node = DfaState(name, node_data['action'])
       name_map[name] = node
@@ skipping 117 matching lines @@
   @staticmethod
   def set_verify(verify):
     DfaMinimizer.__verify = verify
 
   def __init__(self, dfa):
     self.__dfa = dfa
     self.__id_map = None
     self.__reverse_id_map = None
     self.__alphabet = None
 
-  def __partition(self):
+  def __create_initial_partitions(self):
     assert not self.__id_map
     assert not self.__reverse_id_map
     assert not self.__alphabet
-    action_map = {}
+
+    # For the minimization, we associate each state with an ID. A set of states
+    # is represented as a set of state IDs.
     id_map = {}
+
+    # First we partition the states into the following groups:
+    # - terminal states without action
+    # - nonterminal states without action
+    # - one group per action: terminal states which have the action
+    # - one group per action: nonterminal states which have the action
+    # These are the keys of initial_partitions. The values are lists of state
+    # IDs.
+    initial_partitions = {}
     terminal_set = self.__dfa.terminal_set()
-    all_keys = []
+    all_keys = [] # Will contain all TransitionKeys in the dfa.
+
+    # f fills in initial_partitions, id_map and all_keys.
     def f(state, visitor_state):
       state_id = len(id_map)
       id_map[state_id] = state
       action = state.action()
       all_keys.append(state.key_iter())
       if action:
         if state not in terminal_set:
           assert action.entry_action()
           key = ("nonterminal action", action)
         else:
           key = ("terminal action", action)
       elif state in terminal_set:
         key = ("terminal set",)
       else:
         key = ("nonterminal set",)
-      if not key in action_map:
-        action_map[key] = set()
-      action_map[key].add(state_id)
+      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()
-    for k, p in action_map.items():
+
+    # Create StatePartition objects:
+    for k, p in initial_partitions.items():
       p = StatePartition(p)
       partitions.add(p)
-      if k[0] == "terminal_set" or k[0] == "terminal action" or True:
-        working_set.add(p)
+      working_set.add(p)
     reverse_id_map = {v : k for k, v in id_map.items()}
     assert len(id_map) == len(reverse_id_map)
     self.__reverse_id_map = reverse_id_map
     self.__id_map = id_map
+
+    # The alphabet defines the TransitionKeys we need to check when dedicing if
+    # to states of the dfa can be in the same partition. See the doc string of
+    # TransitionKey.disjoint_keys.
+
+    # For example, if the TransitionKeys are {[a-d], [c-h]}, the alphabet is
+    # {[a-b], [c-d], [e-h]}. If state S1 has a transition to S2 with
+    # TransitionKey [a-d], and state S3 has a transition to S4 with
+    # TransitionKey [c-h], S1 and S3 cannot be in the same partition. This will
+    # become clear when we check the transition for TransitionKey [c-d] (S1 has
+    # a transition to S2, S3 has a transition to S4).
     self.__alphabet = list(TransitionKey.disjoint_keys(chain(*all_keys)))
-    # map transitions wrt alphabet mapping
+
+    # For each state and each TransitionKey in the alphabet, find out which
+    # transition we take from the state with the TransitionKey.
     transitions = {}
     for state_id, state in id_map.items():
       def f((key_id, key)):
-        transition = state.key_matches(key)
-        if transition:
-          return reverse_id_map[transition]
+        transition_state = state.transition_state_with_key(key)
+        if transition_state:
+          return reverse_id_map[transition_state]
         return None
       transitions[state_id] = map(f, enumerate(self.__alphabet))
     self.__transitions = transitions
     # verify created structures
     if self.__verify:
       for partition in partitions:
         for state_id in partition:
-          transition_array = transitions[state_id]
+          transition_state_array = transitions[state_id]
           state = id_map[state_id]
           for key_id, key in enumerate(self.__alphabet):
-            transition_id = transition_array[key_id]
-            transition_state = state.key_matches(key)
+            transition_state_id = transition_state_array[key_id]
+            transition_state = state.transition_state_with_key(key)
             if not transition_state:
-              assert transition_id == None
+              assert transition_state_id == None
             else:
-              assert transition_id != None
-              assert transition_id == reverse_id_map[transition_state]
+              assert transition_state_id != None
+              assert transition_state_id == reverse_id_map[transition_state]
     return (working_set, partitions)
 
   @staticmethod
   def __partition_count(partitions):
     return len(reduce(lambda acc, p: acc | p.set(), partitions, set()))
 
   def __merge_partitions(self, partitions):
     id_map = self.__id_map
     reverse_id_map = self.__reverse_id_map
     verify = self.__verify
@@ skipping 13 matching lines @@
         'transitions' : {},
         'terminal' : state in self.__dfa.terminal_set(),
         'action' : state.action(),
       }
       mapping[str(partition)] = node
       transition_array = transitions[state_id]
       for key_id, key in enumerate(self.__alphabet):
         transition_id = transition_array[key_id]
         if transition_id == None:
           if verify:
-            assert not state.key_matches(key)
+            assert not state.transition_state_with_key(key)
             for s_id in state_ids:
-              assert not id_map[s_id].key_matches(key)
+              assert not id_map[s_id].transition_state_with_key(key)
           continue
         transition_partition = reverse_partition_map[transition_id]
         assert transition_partition
         if verify:
           for s_id in state_ids:
-            transition = id_map[s_id].key_matches(key)
+            transition = id_map[s_id].transition_state_with_key(key)
             assert transition
             test_partition = reverse_partition_map[reverse_id_map[transition]]
             assert test_partition == transition_partition
         node['transitions'][key] = name_map[transition_partition]
     start_id = reverse_id_map[self.__dfa.start_state()]
     start_name = name_map[reverse_partition_map[start_id]]
     return (start_name, mapping)
 
   def minimize(self):
-    (working_set, partitions) = self.__partition()
+    '''Minimize the dfa. For the general idea of minimizing automata, see
+    http://en.wikipedia.org/wiki/DFA_minimization. In addition, we need to take
+    account the actions associated to stages, i.e., we cannot merge two states
+    which have different actions.'''
+    (working_set, partitions) = self.__create_initial_partitions()
     node_count = self.__dfa.node_count()
     id_map = self.__id_map
     reverse_id_map = self.__reverse_id_map
     transitions = self.__transitions
     key_range = range(0, len(self.__alphabet))
     while working_set:
       assert working_set <= partitions
       assert self.__partition_count(partitions) == node_count
       test_partition = iter(working_set).next()
       working_set.remove(test_partition)
@@ skipping 29 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.__merge_partitions(partitions)
     return Dfa(start_name, mapping)