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