1#======================================================================= 2# 3# Python Lexical Analyser 4# 5# Classes for building NFAs and DFAs 6# 7#======================================================================= 8 9import sys 10 11from Transitions import TransitionMap 12 13LOWEST_PRIORITY = -sys.maxint 14 15class 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 59class 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 122class 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)) 257