Cython/Plex/Machines.py

   1 #=======================================================================
   2 #
   3 #   Python Lexical Analyser
   4 #
   5 #   Classes for building NFAs and DFAs
   6 #
   7 #=======================================================================
   8
   9 import sys
  10
  11 from Transitions import TransitionMap
  12
  13 LOWEST_PRIORITY = -sys.maxint
  14
  15 class Machine(object):
  16   """A collection of Nodes representing an NFA or DFA."""
  17   states = None         # [Node]
  18   next_state_number = 1
  19   initial_states = None # {(name, bol): Node}
  20
  21   def __init__(self):
  22     self.states = []
  23     self.initial_states = {}
  24
  25   def __del__(self):
  26     #print "Destroying", self ###
  27     for state in self.states:
  28       state.destroy()
  29
  30   def new_state(self):
  31     """Add a new state to the machine and return it."""
  32     s = Node()
  33     n = self.next_state_number
  34     self.next_state_number = n + 1
  35     s.number = n
  36     self.states.append(s)
  37     return s
  38
  39   def new_initial_state(self, name):
  40     state = self.new_state()
  41     self.make_initial_state(name, state)
  42     return state
  43
  44   def make_initial_state(self, name, state):
  45     self.initial_states[name] = state
  46
  47   def get_initial_state(self, name):
  48     return self.initial_states[name]
  49
  50   def dump(self, file):
  51     file.write("Plex.Machine:\n")
  52     if self.initial_states is not None:
  53       file.write("   Initial states:\n")
  54       for (name, state) in self.initial_states.iteritems():
  55         file.write("      '%s': %d\n" % (name, state.number))
  56     for s in self.states:
  57       s.dump(file)
  58
  59 class Node(object):
  60   """A state of an NFA or DFA."""
  61   transitions = None       # TransitionMap
  62   action = None            # Action
  63   action_priority = None   # integer
  64   number = 0               # for debug output
  65   epsilon_closure = None   # used by nfa_to_dfa()
  66
  67   def __init__(self):
  68     # Preinitialise the list of empty transitions, because
  69     # the nfa-to-dfa algorithm needs it
  70     #self.transitions = {'':[]}
  71     self.transitions = TransitionMap()
  72     self.action_priority = LOWEST_PRIORITY
  73
  74   def destroy(self):
  75     #print "Destroying", self ###
  76     self.transitions = None
  77     self.action = None
  78     self.epsilon_closure = None
  79
  80   def add_transition(self, event, new_state):
  81     self.transitions.add(event, new_state)
  82
  83   def link_to(self, state):
  84     """Add an epsilon-move from this state to another state."""
  85     self.add_transition('', state)
  86
  87   def set_action(self, action, priority):
  88     """Make this an accepting state with the given action. If
  89     there is already an action, choose the action with highest
  90     priority."""
  91     if priority > self.action_priority:
  92       self.action = action
  93       self.action_priority = priority
  94
  95   def get_action(self):
  96     return self.action
  97
  98   def get_action_priority(self):
  99     return self.action_priority
 100
 101   def is_accepting(self):
 102     return self.action is not None
 103
 104   def __str__(self):
 105     return "State %d" % self.number
 106
 107   def dump(self, file):
 108     # Header
 109     file.write("   State %d:\n" % self.number)
 110     # Transitions
 111 #        self.dump_transitions(file)
 112     self.transitions.dump(file)
 113     # Action
 114     action = self.action
 115     priority = self.action_priority
 116     if action is not None:
 117       file.write("      %s [priority %d]\n" % (action, priority))
 118
 119   def __lt__(self, other):
 120     return self.number < other.number
 121
 122 class FastMachine(object):
 123   """
 124   FastMachine is a deterministic machine represented in a way that
 125   allows fast scanning.
 126   """
 127   initial_states = None # {state_name:state}
 128   states = None         # [state]
 129                         # where state = {event:state, 'else':state, 'action':Action}
 130   next_number = 1       # for debugging
 131
 132   new_state_template = {
 133     '':None, 'bol':None, 'eol':None, 'eof':None, 'else':None
 134   }
 135
 136   def __init__(self, old_machine = None):
 137     self.initial_states = initial_states = {}
 138     self.states = []
 139     if old_machine:
 140       self.old_to_new = old_to_new = {}
 141       for old_state in old_machine.states:
 142         new_state = self.new_state()
 143         old_to_new[old_state] = new_state
 144       for name, old_state in old_machine.initial_states.iteritems():
 145         initial_states[name] = old_to_new[old_state]
 146       for old_state in old_machine.states:
 147         new_state = old_to_new[old_state]
 148         for event, old_state_set in old_state.transitions.iteritems():
 149           if old_state_set:
 150             new_state[event] = old_to_new[old_state_set.keys()[0]]
 151           else:
 152             new_state[event] = None
 153         new_state['action'] = old_state.action
 154
 155   def __del__(self):
 156     for state in self.states:
 157       state.clear()
 158
 159   def new_state(self, action = None):
 160     number = self.next_number
 161     self.next_number = number + 1
 162     result = self.new_state_template.copy()
 163     result['number'] = number
 164     result['action'] = action
 165     self.states.append(result)
 166     return result
 167
 168   def make_initial_state(self, name, state):
 169     self.initial_states[name] = state
 170
 171   def add_transitions(self, state, event, new_state, maxint=sys.maxint):
 172     if type(event) is tuple:
 173       code0, code1 = event
 174       if code0 == -maxint:
 175         state['else'] = new_state
 176       elif code1 != maxint:
 177         while code0 < code1:
 178           state[chr(code0)] = new_state
 179           code0 = code0 + 1
 180     else:
 181       state[event] = new_state
 182
 183   def get_initial_state(self, name):
 184     return self.initial_states[name]
 185
 186   def dump(self, file):
 187     file.write("Plex.FastMachine:\n")
 188     file.write("   Initial states:\n")
 189     for name, state in self.initial_states.iteritems():
 190       file.write("      %s: %s\n" % (repr(name), state['number']))
 191     for state in self.states:
 192       self.dump_state(state, file)
 193
 194   def dump_state(self, state, file):
 195     # Header
 196     file.write("   State %d:\n" % state['number'])
 197     # Transitions
 198     self.dump_transitions(state, file)
 199     # Action
 200     action = state['action']
 201     if action is not None:
 202       file.write("      %s\n" % action)
 203
 204   def dump_transitions(self, state, file):
 205     chars_leading_to_state = {}
 206     special_to_state = {}
 207     for (c, s) in state.iteritems():
 208       if len(c) == 1:
 209         chars = chars_leading_to_state.get(id(s), None)
 210         if chars is None:
 211           chars = []
 212           chars_leading_to_state[id(s)] = chars
 213         chars.append(c)
 214       elif len(c) <= 4:
 215         special_to_state[c] = s
 216     ranges_to_state = {}
 217     for state in self.states:
 218       char_list = chars_leading_to_state.get(id(state), None)
 219       if char_list:
 220         ranges = self.chars_to_ranges(char_list)
 221         ranges_to_state[ranges] = state
 222     ranges_list = ranges_to_state.keys()
 223     ranges_list.sort()
 224     for ranges in ranges_list:
 225       key = self.ranges_to_string(ranges)
 226       state = ranges_to_state[ranges]
 227       file.write("      %s --> State %d\n" % (key, state['number']))
 228     for key in ('bol', 'eol', 'eof', 'else'):
 229       state = special_to_state.get(key, None)
 230       if state:
 231         file.write("      %s --> State %d\n" % (key, state['number']))
 232
 233   def chars_to_ranges(self, char_list):
 234     char_list.sort()
 235     i = 0
 236     n = len(char_list)
 237     result = []
 238     while i < n:
 239       c1 = ord(char_list[i])
 240       c2 = c1
 241       i = i + 1
 242       while i < n and ord(char_list[i]) == c2 + 1:
 243         i = i + 1
 244         c2 = c2 + 1
 245       result.append((chr(c1), chr(c2)))
 246     return tuple(result)
 247
 248   def ranges_to_string(self, range_list):
 249     return ','.join(map(self.range_to_string, range_list))
 250
 251   def range_to_string(self, range_tuple):
 252     (c1, c2) = range_tuple
 253     if c1 == c2:
 254       return repr(c1)
 255     else:
 256       return "%s..%s" % (repr(c1), repr(c2))