diff options
Diffstat (limited to 'Cython/Plex/DFA.py')
| -rw-r--r-- | Cython/Plex/DFA.py | 39 |
1 files changed, 12 insertions, 27 deletions
diff --git a/Cython/Plex/DFA.py b/Cython/Plex/DFA.py index 76324621f..66dc4a379 100644 --- a/Cython/Plex/DFA.py +++ b/Cython/Plex/DFA.py @@ -1,11 +1,9 @@ -#======================================================================= -# -# Python Lexical Analyser -# -# Converting NFA to DFA -# -#======================================================================= +# cython: auto_cpdef=True +""" +Python Lexical Analyser +Converting NFA to DFA +""" from __future__ import absolute_import from . import Machines @@ -29,12 +27,14 @@ def nfa_to_dfa(old_machine, debug=None): # 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: @@ -45,6 +45,7 @@ def nfa_to_dfa(old_machine, debug=None): 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) @@ -95,14 +96,11 @@ class StateMap(object): 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 = {} + self.new_machine = new_machine # Machine + self.old_to_new_dict = {} # {(old_state,...) : new_state} + self.new_to_old_dict = {} # {id(new_state) : old_state_set} def old_to_new(self, old_state_set): """ @@ -119,8 +117,6 @@ class StateMap(object): 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): @@ -133,13 +129,6 @@ class StateMap(object): 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)] @@ -149,9 +138,7 @@ class StateMap(object): Convert a set of states into a uniquified sorted tuple suitable for use as a dictionary key. """ - lst = list(state_set) - lst.sort() - return tuple(lst) + return tuple(sorted(state_set)) def dump(self, file): from .Transitions import state_set_str @@ -160,5 +147,3 @@ class StateMap(object): 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))) - - |