15f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#======================================================================= 25f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)# 35f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)# Python Lexical Analyser 45f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)# 55f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)# Classes for building NFAs and DFAs 65f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)# 75f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#======================================================================= 85f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 95f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)import sys 105f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 115f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)from Transitions import TransitionMap 125f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 135f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)LOWEST_PRIORITY = -sys.maxint 145f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 155f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)class Machine(object): 165f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) """A collection of Nodes representing an NFA or DFA.""" 175f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) states = None # [Node] 185f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) next_state_number = 1 195f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) initial_states = None # {(name, bol): Node} 205f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 215f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def __init__(self): 225f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.states = [] 235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.initial_states = {} 245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 255f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def __del__(self): 265f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) #print "Destroying", self ### 275f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for state in self.states: 285f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) state.destroy() 295f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 305f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def new_state(self): 315f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) """Add a new state to the machine and return it.""" 325f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) s = Node() 335f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) n = self.next_state_number 345f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.next_state_number = n + 1 355f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) s.number = n 365f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.states.append(s) 375f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return s 385f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 395f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def new_initial_state(self, name): 405f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) state = self.new_state() 415f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.make_initial_state(name, state) 425f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return state 435f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 445f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def make_initial_state(self, name, state): 455f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.initial_states[name] = state 465f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 475f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def get_initial_state(self, name): 485f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return self.initial_states[name] 495f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 505f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def dump(self, file): 515f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) file.write("Plex.Machine:\n") 525f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if self.initial_states is not None: 535f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) file.write(" Initial states:\n") 545f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for (name, state) in self.initial_states.iteritems(): 555f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) file.write(" '%s': %d\n" % (name, state.number)) 565f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for s in self.states: 575f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) s.dump(file) 585f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 595f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)class Node(object): 605f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) """A state of an NFA or DFA.""" 615f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) transitions = None # TransitionMap 625f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) action = None # Action 635f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) action_priority = None # integer 645f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) number = 0 # for debug output 655f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) epsilon_closure = None # used by nfa_to_dfa() 665f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 675f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def __init__(self): 685f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) # Preinitialise the list of empty transitions, because 695f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) # the nfa-to-dfa algorithm needs it 705f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) #self.transitions = {'':[]} 715f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.transitions = TransitionMap() 725f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.action_priority = LOWEST_PRIORITY 735f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 745f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def destroy(self): 755f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) #print "Destroying", self ### 765f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.transitions = None 775f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.action = None 785f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.epsilon_closure = None 795f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 805f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def add_transition(self, event, new_state): 815f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.transitions.add(event, new_state) 825f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 835f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def link_to(self, state): 845f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) """Add an epsilon-move from this state to another state.""" 855f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.add_transition('', state) 865f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 875f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def set_action(self, action, priority): 885f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) """Make this an accepting state with the given action. If 895f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) there is already an action, choose the action with highest 905f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) priority.""" 915f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if priority > self.action_priority: 925f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.action = action 935f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.action_priority = priority 945f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 955f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def get_action(self): 965f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return self.action 975f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 985f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def get_action_priority(self): 995f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return self.action_priority 1005f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1015f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def is_accepting(self): 1025f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return self.action is not None 1035f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1045f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def __str__(self): 1055f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return "State %d" % self.number 1065f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1075f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def dump(self, file): 1085f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) # Header 1095f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) file.write(" State %d:\n" % self.number) 1105f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) # Transitions 1115f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)# self.dump_transitions(file) 1125f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.transitions.dump(file) 1135f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) # Action 1145f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) action = self.action 1155f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) priority = self.action_priority 1165f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if action is not None: 1175f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) file.write(" %s [priority %d]\n" % (action, priority)) 1185f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1195f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def __lt__(self, other): 1205f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return self.number < other.number 1215f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1225f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)class FastMachine(object): 1235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) """ 1245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) FastMachine is a deterministic machine represented in a way that 1255f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) allows fast scanning. 1265f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) """ 1275f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) initial_states = None # {state_name:state} 1285f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) states = None # [state] 1295f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) # where state = {event:state, 'else':state, 'action':Action} 1305f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) next_number = 1 # for debugging 1315f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1325f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) new_state_template = { 1335f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) '':None, 'bol':None, 'eol':None, 'eof':None, 'else':None 1345f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 1355f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1365f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def __init__(self, old_machine = None): 1375f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.initial_states = initial_states = {} 1385f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.states = [] 1395f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if old_machine: 1405f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.old_to_new = old_to_new = {} 1415f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for old_state in old_machine.states: 1425f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) new_state = self.new_state() 1435f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) old_to_new[old_state] = new_state 1445f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for name, old_state in old_machine.initial_states.iteritems(): 1455f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) initial_states[name] = old_to_new[old_state] 1465f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for old_state in old_machine.states: 1475f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) new_state = old_to_new[old_state] 1485f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for event, old_state_set in old_state.transitions.iteritems(): 1495f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if old_state_set: 1505f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) new_state[event] = old_to_new[old_state_set.keys()[0]] 1515f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) else: 1525f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) new_state[event] = None 1535f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) new_state['action'] = old_state.action 1545f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1555f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def __del__(self): 1565f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for state in self.states: 1575f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) state.clear() 1585f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1595f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def new_state(self, action = None): 1605f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) number = self.next_number 1615f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.next_number = number + 1 1625f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) result = self.new_state_template.copy() 1635f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) result['number'] = number 1645f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) result['action'] = action 1655f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.states.append(result) 1665f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return result 1675f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1685f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def make_initial_state(self, name, state): 1695f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.initial_states[name] = state 1705f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1715f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def add_transitions(self, state, event, new_state, maxint=sys.maxint): 1725f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if type(event) is tuple: 1735f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) code0, code1 = event 1745f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if code0 == -maxint: 1755f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) state['else'] = new_state 1765f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) elif code1 != maxint: 1775f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) while code0 < code1: 1785f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) state[chr(code0)] = new_state 1795f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) code0 = code0 + 1 1805f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) else: 1815f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) state[event] = new_state 1825f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1835f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def get_initial_state(self, name): 1845f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return self.initial_states[name] 1855f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1865f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def dump(self, file): 1875f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) file.write("Plex.FastMachine:\n") 1885f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) file.write(" Initial states:\n") 1895f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for name, state in self.initial_states.iteritems(): 1905f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) file.write(" %s: %s\n" % (repr(name), state['number'])) 1915f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for state in self.states: 1925f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.dump_state(state, file) 1935f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1945f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def dump_state(self, state, file): 1955f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) # Header 1965f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) file.write(" State %d:\n" % state['number']) 1975f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) # Transitions 1985f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) self.dump_transitions(state, file) 1995f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) # Action 2005f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) action = state['action'] 2015f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if action is not None: 2025f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) file.write(" %s\n" % action) 2035f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 2045f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def dump_transitions(self, state, file): 2055f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) chars_leading_to_state = {} 2065f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) special_to_state = {} 2075f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for (c, s) in state.iteritems(): 2085f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if len(c) == 1: 2095f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) chars = chars_leading_to_state.get(id(s), None) 2105f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if chars is None: 2115f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) chars = [] 2125f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) chars_leading_to_state[id(s)] = chars 2135f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) chars.append(c) 2145f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) elif len(c) <= 4: 2155f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) special_to_state[c] = s 2165f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ranges_to_state = {} 2175f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for state in self.states: 2185f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) char_list = chars_leading_to_state.get(id(state), None) 2195f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if char_list: 2205f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ranges = self.chars_to_ranges(char_list) 2215f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ranges_to_state[ranges] = state 2225f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ranges_list = ranges_to_state.keys() 2235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) ranges_list.sort() 2245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for ranges in ranges_list: 2255f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) key = self.ranges_to_string(ranges) 2265f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) state = ranges_to_state[ranges] 2275f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) file.write(" %s --> State %d\n" % (key, state['number'])) 2285f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) for key in ('bol', 'eol', 'eof', 'else'): 2295f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) state = special_to_state.get(key, None) 2305f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if state: 2315f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) file.write(" %s --> State %d\n" % (key, state['number'])) 2325f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 2335f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def chars_to_ranges(self, char_list): 2345f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) char_list.sort() 2355f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) i = 0 2365f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) n = len(char_list) 2375f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) result = [] 2385f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) while i < n: 2395f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) c1 = ord(char_list[i]) 2405f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) c2 = c1 2415f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) i = i + 1 2425f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) while i < n and ord(char_list[i]) == c2 + 1: 2435f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) i = i + 1 2445f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) c2 = c2 + 1 2455f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) result.append((chr(c1), chr(c2))) 2465f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return tuple(result) 2475f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 2485f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def ranges_to_string(self, range_list): 2495f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return ','.join(map(self.range_to_string, range_list)) 2505f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 2515f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) def range_to_string(self, range_tuple): 2525f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) (c1, c2) = range_tuple 2535f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if c1 == c2: 2545f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return repr(c1) 2555f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) else: 2565f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return "%s..%s" % (repr(c1), repr(c2)) 257