diff options
Diffstat (limited to 'debian/pyrex/pyrex-0.9.9/Pyrex/Plex/DFA.py')
-rwxr-xr-x | debian/pyrex/pyrex-0.9.9/Pyrex/Plex/DFA.py | 156 |
1 files changed, 0 insertions, 156 deletions
diff --git a/debian/pyrex/pyrex-0.9.9/Pyrex/Plex/DFA.py b/debian/pyrex/pyrex-0.9.9/Pyrex/Plex/DFA.py deleted file mode 100755 index 2c0004b0..00000000 --- a/debian/pyrex/pyrex-0.9.9/Pyrex/Plex/DFA.py +++ /dev/null @@ -1,156 +0,0 @@ -#======================================================================= -# -# Python Lexical Analyser -# -# Converting NFA to DFA -# -#======================================================================= - -import Machines -from Machines import LOWEST_PRIORITY -from Transitions import TransitionMap - -def nfa_to_dfa(old_machine, debug = None): - """ - Given a nondeterministic Machine, return a new equivalent - Machine which is deterministic. - """ - # We build a new machine whose states correspond to sets of states - # in the old machine. Initially we add a new state corresponding to - # the epsilon-closure of each initial old state. Then we give transitions - # to each new state which are the union of all transitions out of any - # of the corresponding old states. The new state reached on a given - # character is the one corresponding to the set of states reachable - # on that character from any of the old states. As new combinations of - # old states are created, new states are added as needed until closure - # is reached. - new_machine = Machines.FastMachine() - state_map = StateMap(new_machine) - # Seed the process using the initial states of the old machine. - # Make the corresponding new states into initial states of the new - # machine with the same names. - for (key, old_state) in old_machine.initial_states.items(): - new_state = state_map.old_to_new(epsilon_closure(old_state)) - new_machine.make_initial_state(key, new_state) - # Tricky bit here: we add things to the end of this list while we're - # iterating over it. The iteration stops when closure is achieved. - for new_state in new_machine.states: - transitions = TransitionMap() - for old_state in state_map.new_to_old(new_state).keys(): - for event, old_target_states in old_state.transitions.items(): - if event and old_target_states: - transitions.add_set(event, set_epsilon_closure(old_target_states)) - for event, old_states in transitions.items(): - new_machine.add_transitions(new_state, event, state_map.old_to_new(old_states)) - if debug: - debug.write("\n===== State Mapping =====\n") - state_map.dump(debug) - return new_machine - -def set_epsilon_closure(state_set): - """ - Given a set of states, return the union of the epsilon - closures of its member states. - """ - result = {} - for state1 in state_set.keys(): - for state2 in epsilon_closure(state1).keys(): - result[state2] = 1 - return result - -def epsilon_closure(state): - """ - Return the set of states reachable from the given state - by epsilon moves. - """ - # Cache the result - result = state.epsilon_closure - if result is None: - result = {} - state.epsilon_closure = result - add_to_epsilon_closure(result, state) - return result - -def add_to_epsilon_closure(state_set, state): - """ - Recursively add to |state_set| states reachable from the given state - by epsilon moves. - """ - if not state_set.get(state, 0): - state_set[state] = 1 - state_set_2 = state.transitions.get_epsilon() - if state_set_2: - for state2 in state_set_2.keys(): - add_to_epsilon_closure(state_set, state2) - -class StateMap: - """ - Helper class used by nfa_to_dfa() to map back and forth between - sets of states from the old machine and states of the new machine. - """ - new_machine = None # Machine - old_to_new_dict = None # {(old_state,...) : new_state} - new_to_old_dict = None # {id(new_state) : old_state_set} - - def __init__(self, new_machine): - self.new_machine = new_machine - self.old_to_new_dict = {} - self.new_to_old_dict= {} - - def old_to_new(self, old_state_set): - """ - Return the state of the new machine corresponding to the - set of old machine states represented by |state_set|. A new - state will be created if necessary. If any of the old states - are accepting states, the new state will be an accepting state - with the highest priority action from the old states. - """ - key = self.make_key(old_state_set) - new_state = self.old_to_new_dict.get(key, None) - if not new_state: - action = self.highest_priority_action(old_state_set) - new_state = self.new_machine.new_state(action) - self.old_to_new_dict[key] = new_state - self.new_to_old_dict[id(new_state)] = old_state_set - #for old_state in old_state_set.keys(): - #new_state.merge_actions(old_state) - return new_state - - def highest_priority_action(self, state_set): - best_action = None - best_priority = LOWEST_PRIORITY - for state in state_set.keys(): - priority = state.action_priority - if priority > best_priority: - best_action = state.action - best_priority = priority - return best_action - -# def old_to_new_set(self, old_state_set): -# """ -# Return the new state corresponding to a set of old states as -# a singleton set. -# """ -# return {self.old_to_new(old_state_set):1} - - def new_to_old(self, new_state): - """Given a new state, return a set of corresponding old states.""" - return self.new_to_old_dict[id(new_state)] - - def make_key(self, state_set): - """ - Convert a set of states into a uniquified - sorted tuple suitable for use as a dictionary key. - """ - lst = state_set.keys() - lst.sort() - return tuple(lst) - - def dump(self, file): - from Transitions import state_set_str - for new_state in self.new_machine.states: - old_state_set = self.new_to_old_dict[id(new_state)] - file.write(" State %s <-- %s\n" % ( - new_state['number'], state_set_str(old_state_set))) - - |