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 157
