| |
| """ |
| Python Lexical Analyser |
| |
| Converting NFA to DFA |
| """ |
|
|
| import cython |
| from . import Machines |
| from .Machines import LOWEST_PRIORITY |
| from .Transitions import TransitionMap |
|
|
| if cython.compiled: |
| from cython.cimports.Cython.Plex.Machines import Node, FastMachine |
| from cython.cimports.Cython.Plex.Transitions import TransitionMap as type_TransitionMap |
| else: |
| from Cython.Plex.Machines import Node, FastMachine |
| from Cython.Plex.Transitions import TransitionMap as type_TransitionMap |
|
|
|
|
| def nfa_to_dfa(old_machine, debug=None): |
| """ |
| Given a nondeterministic Machine, return a new equivalent |
| Machine which is deterministic. |
| """ |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| transitions: type_TransitionMap |
| new_machine: FastMachine = Machines.FastMachine() |
| state_map: StateMap = StateMap(new_machine) |
|
|
| |
| |
| |
| 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) |
|
|
| |
| |
| for new_state in new_machine.states: |
| transitions = TransitionMap() |
| for old_state in state_map.new_to_old(new_state): |
| 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 |
|
|
|
|
| @cython.cfunc |
| def set_epsilon_closure(state_set: set) -> set: |
| """ |
| Given a set of states, return the union of the epsilon |
| closures of its member states. |
| """ |
| result = set() |
| for state1 in state_set: |
| for state2 in epsilon_closure(state1): |
| result.add(state2) |
| return result |
|
|
|
|
| @cython.cfunc |
| def epsilon_closure(state: Node) -> set: |
| """ |
| Return the set of states reachable from the given state |
| by epsilon moves. |
| """ |
| |
| result = state.epsilon_closure |
| if result is None: |
| result = set() |
| state.epsilon_closure = result |
| add_to_epsilon_closure(result, state) |
| return result |
|
|
|
|
| @cython.cfunc |
| def add_to_epsilon_closure(state_set: set, state: Node): |
| """ |
| Recursively add to |state_set| states reachable from the given state |
| by epsilon moves. |
| """ |
| state_set_2: set |
| state2: Node |
|
|
| if state not in state_set: |
| state_set.add(state) |
| state_set_2 = state.transitions.get_epsilon() |
| if state_set_2: |
| for state2 in state_set_2: |
| 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. |
| """ |
|
|
| 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: 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 |
| return new_state |
|
|
| def highest_priority_action(self, state_set: set): |
| best_action = None |
| best_priority = LOWEST_PRIORITY |
| state: Node |
| for state in state_set: |
| priority = state.action_priority |
| if priority > best_priority: |
| best_action = state.action |
| best_priority = priority |
| return best_action |
|
|
| 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: set): |
| """ |
| Convert a set of states into a uniquified |
| sorted tuple suitable for use as a dictionary key. |
| """ |
| return tuple(sorted(state_set)) |
|
|
| 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))) |
|
|