#======================================================================= # # Python Lexical Analyser # # Classes for building NFAs and DFAs # #======================================================================= from __future__ import absolute_import import sys from .Transitions import TransitionMap try: from sys import maxsize as maxint except ImportError: from sys import maxint try: unichr except NameError: unichr = chr LOWEST_PRIORITY = -maxint class Machine(object): """A collection of Nodes representing an NFA or DFA.""" states = None # [Node] next_state_number = 1 initial_states = None # {(name, bol): Node} def __init__(self): self.states = [] self.initial_states = {} def __del__(self): #print "Destroying", self ### for state in self.states: state.destroy() def new_state(self): """Add a new state to the machine and return it.""" s = Node() n = self.next_state_number self.next_state_number = n + 1 s.number = n self.states.append(s) return s def new_initial_state(self, name): state = self.new_state() self.make_initial_state(name, state) return state def make_initial_state(self, name, state): self.initial_states[name] = state def get_initial_state(self, name): return self.initial_states[name] def dump(self, file): file.write("Plex.Machine:\n") if self.initial_states is not None: file.write(" Initial states:\n") for (name, state) in sorted(self.initial_states.items()): file.write(" '%s': %d\n" % (name, state.number)) for s in self.states: s.dump(file) class Node(object): """A state of an NFA or DFA.""" transitions = None # TransitionMap action = None # Action action_priority = None # integer number = 0 # for debug output epsilon_closure = None # used by nfa_to_dfa() def __init__(self): # Preinitialise the list of empty transitions, because # the nfa-to-dfa algorithm needs it #self.transitions = {'':[]} self.transitions = TransitionMap() self.action_priority = LOWEST_PRIORITY def destroy(self): #print "Destroying", self ### self.transitions = None self.action = None self.epsilon_closure = None def add_transition(self, event, new_state): self.transitions.add(event, new_state) def link_to(self, state): """Add an epsilon-move from this state to another state.""" self.add_transition('', state) def set_action(self, action, priority): """Make this an accepting state with the given action. If there is already an action, choose the action with highest priority.""" if priority > self.action_priority: self.action = action self.action_priority = priority def get_action(self): return self.action def get_action_priority(self): return self.action_priority def is_accepting(self): return self.action is not None def __str__(self): return "State %d" % self.number def dump(self, file): # Header file.write(" State %d:\n" % self.number) # Transitions # self.dump_transitions(file) self.transitions.dump(file) # Action action = self.action priority = self.action_priority if action is not None: file.write(" %s [priority %d]\n" % (action, priority)) def __lt__(self, other): return self.number < other.number class FastMachine(object): """ FastMachine is a deterministic machine represented in a way that allows fast scanning. """ initial_states = None # {state_name:state} states = None # [state] where state = {event:state, 'else':state, 'action':Action} next_number = 1 # for debugging new_state_template = { '': None, 'bol': None, 'eol': None, 'eof': None, 'else': None } def __init__(self): self.initial_states = {} self.states = [] def __del__(self): for state in self.states: state.clear() def new_state(self, action=None): number = self.next_number self.next_number = number + 1 result = self.new_state_template.copy() result['number'] = number result['action'] = action self.states.append(result) return result def make_initial_state(self, name, state): self.initial_states[name] = state def add_transitions(self, state, event, new_state, maxint=maxint): if type(event) is tuple: code0, code1 = event if code0 == -maxint: state['else'] = new_state elif code1 != maxint: while code0 < code1: state[unichr(code0)] = new_state code0 += 1 else: state[event] = new_state def get_initial_state(self, name): return self.initial_states[name] def dump(self, file): file.write("Plex.FastMachine:\n") file.write(" Initial states:\n") for name, state in sorted(self.initial_states.items()): file.write(" %s: %s\n" % (repr(name), state['number'])) for state in self.states: self.dump_state(state, file) def dump_state(self, state, file): # Header file.write(" State %d:\n" % state['number']) # Transitions self.dump_transitions(state, file) # Action action = state['action'] if action is not None: file.write(" %s\n" % action) def dump_transitions(self, state, file): chars_leading_to_state = {} special_to_state = {} for (c, s) in state.items(): if len(c) == 1: chars = chars_leading_to_state.get(id(s), None) if chars is None: chars = [] chars_leading_to_state[id(s)] = chars chars.append(c) elif len(c) <= 4: special_to_state[c] = s ranges_to_state = {} for state in self.states: char_list = chars_leading_to_state.get(id(state), None) if char_list: ranges = self.chars_to_ranges(char_list) ranges_to_state[ranges] = state ranges_list = ranges_to_state.keys() ranges_list.sort() for ranges in ranges_list: key = self.ranges_to_string(ranges) state = ranges_to_state[ranges] file.write(" %s --> State %d\n" % (key, state['number'])) for key in ('bol', 'eol', 'eof', 'else'): state = special_to_state.get(key, None) if state: file.write(" %s --> State %d\n" % (key, state['number'])) def chars_to_ranges(self, char_list): char_list.sort() i = 0 n = len(char_list) result = [] while i < n: c1 = ord(char_list[i]) c2 = c1 i += 1 while i < n and ord(char_list[i]) == c2 + 1: i += 1 c2 += 1 result.append((chr(c1), chr(c2))) return tuple(result) def ranges_to_string(self, range_list): return ','.join(map(self.range_to_string, range_list)) def range_to_string(self, range_tuple): (c1, c2) = range_tuple if c1 == c2: return repr(c1) else: return "%s..%s" % (repr(c1), repr(c2))