third_party/cython/src/Cython/Plex/DFA.py

   1 #=======================================================================
   2 #
   3 #   Python Lexical Analyser
   4 #
   5 #   Converting NFA to DFA
   6 #
   7 #=======================================================================
   8
   9 import Machines
  10 from Machines import LOWEST_PRIORITY
  11 from Transitions import TransitionMap
  12
  13 def nfa_to_dfa(old_machine, debug = None):
  14   """
  15   Given a nondeterministic Machine, return a new equivalent
  16   Machine which is deterministic.
  17   """
  18   # We build a new machine whose states correspond to sets of states
  19   # in the old machine. Initially we add a new state corresponding to
  20   # the epsilon-closure of each initial old state. Then we give transitions
  21   # to each new state which are the union of all transitions out of any
  22   # of the corresponding old states. The new state reached on a given
  23   # character is the one corresponding to the set of states reachable
  24   # on that character from any of the old states. As new combinations of
  25   # old states are created, new states are added as needed until closure
  26   # is reached.
  27   new_machine = Machines.FastMachine()
  28   state_map = StateMap(new_machine)
  29   # Seed the process using the initial states of the old machine.
  30   # Make the corresponding new states into initial states of the new
  31   # machine with the same names.
  32   for (key, old_state) in old_machine.initial_states.iteritems():
  33     new_state = state_map.old_to_new(epsilon_closure(old_state))
  34     new_machine.make_initial_state(key, new_state)
  35   # Tricky bit here: we add things to the end of this list while we're
  36   # iterating over it. The iteration stops when closure is achieved.
  37   for new_state in new_machine.states:
  38     transitions = TransitionMap()
  39     for old_state in state_map.new_to_old(new_state):
  40       for event, old_target_states in old_state.transitions.iteritems():
  41         if event and old_target_states:
  42           transitions.add_set(event, set_epsilon_closure(old_target_states))
  43     for event, old_states in transitions.iteritems():
  44       new_machine.add_transitions(new_state, event, state_map.old_to_new(old_states))
  45   if debug:
  46     debug.write("\n===== State Mapping =====\n")
  47     state_map.dump(debug)
  48   return new_machine
  49
  50 def set_epsilon_closure(state_set):
  51   """
  52   Given a set of states, return the union of the epsilon
  53   closures of its member states.
  54   """
  55   result = {}
  56   for state1 in state_set:
  57     for state2 in epsilon_closure(state1):
  58       result[state2] = 1
  59   return result
  60
  61 def epsilon_closure(state):
  62   """
  63   Return the set of states reachable from the given state
  64   by epsilon moves.
  65   """
  66   # Cache the result
  67   result = state.epsilon_closure
  68   if result is None:
  69     result = {}
  70     state.epsilon_closure = result
  71     add_to_epsilon_closure(result, state)
  72   return result
  73
  74 def add_to_epsilon_closure(state_set, state):
  75   """
  76   Recursively add to |state_set| states reachable from the given state
  77   by epsilon moves.
  78   """
  79   if not state_set.get(state, 0):
  80     state_set[state] = 1
  81     state_set_2 = state.transitions.get_epsilon()
  82     if state_set_2:
  83       for state2 in state_set_2:
  84         add_to_epsilon_closure(state_set, state2)
  85
  86 class StateMap(object):
  87   """
  88   Helper class used by nfa_to_dfa() to map back and forth between
  89   sets of states from the old machine and states of the new machine.
  90   """
  91   new_machine     = None # Machine
  92   old_to_new_dict = None # {(old_state,...) : new_state}
  93   new_to_old_dict = None # {id(new_state) : old_state_set}
  94
  95   def __init__(self, new_machine):
  96     self.new_machine = new_machine
  97     self.old_to_new_dict = {}
  98     self.new_to_old_dict= {}
  99
 100   def old_to_new(self, old_state_set):
 101     """
 102     Return the state of the new machine corresponding to the
 103     set of old machine states represented by |state_set|. A new
 104     state will be created if necessary. If any of the old states
 105     are accepting states, the new state will be an accepting state
 106     with the highest priority action from the old states.
 107     """
 108     key = self.make_key(old_state_set)
 109     new_state = self.old_to_new_dict.get(key, None)
 110     if not new_state:
 111       action = self.highest_priority_action(old_state_set)
 112       new_state = self.new_machine.new_state(action)
 113       self.old_to_new_dict[key] = new_state
 114       self.new_to_old_dict[id(new_state)] = old_state_set
 115       #for old_state in old_state_set.keys():
 116         #new_state.merge_actions(old_state)
 117     return new_state
 118
 119   def highest_priority_action(self, state_set):
 120     best_action = None
 121     best_priority = LOWEST_PRIORITY
 122     for state in state_set:
 123       priority = state.action_priority
 124       if priority > best_priority:
 125         best_action = state.action
 126         best_priority = priority
 127     return best_action
 128
 129 #    def old_to_new_set(self, old_state_set):
 130 #        """
 131 #        Return the new state corresponding to a set of old states as
 132 #        a singleton set.
 133 #        """
 134 #        return {self.old_to_new(old_state_set):1}
 135
 136   def new_to_old(self, new_state):
 137     """Given a new state, return a set of corresponding old states."""
 138     return self.new_to_old_dict[id(new_state)]
 139
 140   def make_key(self, state_set):
 141     """
 142     Convert a set of states into a uniquified
 143     sorted tuple suitable for use as a dictionary key.
 144     """
 145     lst = list(state_set)
 146     lst.sort()
 147     return tuple(lst)
 148
 149   def dump(self, file):
 150     from Transitions import state_set_str
 151     for new_state in self.new_machine.states:
 152       old_state_set = self.new_to_old_dict[id(new_state)]
 153       file.write("   State %s <-- %s\n" % (
 154         new_state['number'], state_set_str(old_state_set)))
 155
 156