1 #!/usr/bin/env python 2 3 """This module implements a Finite State Machine (FSM). In addition to state 4 this FSM also maintains a user defined "memory". So this FSM can be used as a 5 Push-down Automata (PDA) since a PDA is a FSM + memory. 6 7 The following describes how the FSM works, but you will probably also need to 8 see the example function to understand how the FSM is used in practice. 9 10 You define an FSM by building tables of transitions. For a given input symbol 11 the process() method uses these tables to decide what action to call and what 12 the next state will be. The FSM has a table of transitions that associate: 13 14 (input_symbol, current_state) --> (action, next_state) 15 16 Where "action" is a function you define. The symbols and states can be any 17 objects. You use the add_transition() and add_transition_list() methods to add 18 to the transition table. The FSM also has a table of transitions that 19 associate: 20 21 (current_state) --> (action, next_state) 22 23 You use the add_transition_any() method to add to this transition table. The 24 FSM also has one default transition that is not associated with any specific 25 input_symbol or state. You use the set_default_transition() method to set the 26 default transition. 27 28 When an action function is called it is passed a reference to the FSM. The 29 action function may then access attributes of the FSM such as input_symbol, 30 current_state, or "memory". The "memory" attribute can be any object that you 31 want to pass along to the action functions. It is not used by the FSM itself. 32 For parsing you would typically pass a list to be used as a stack. 33 34 The processing sequence is as follows. The process() method is given an 35 input_symbol to process. The FSM will search the table of transitions that 36 associate: 37 38 (input_symbol, current_state) --> (action, next_state) 39 40 If the pair (input_symbol, current_state) is found then process() will call the 41 associated action function and then set the current state to the next_state. 42 43 If the FSM cannot find a match for (input_symbol, current_state) it will then 44 search the table of transitions that associate: 45 46 (current_state) --> (action, next_state) 47 48 If the current_state is found then the process() method will call the 49 associated action function and then set the current state to the next_state. 50 Notice that this table lacks an input_symbol. It lets you define transitions 51 for a current_state and ANY input_symbol. Hence, it is called the "any" table. 52 Remember, it is always checked after first searching the table for a specific 53 (input_symbol, current_state). 54 55 For the case where the FSM did not match either of the previous two cases the 56 FSM will try to use the default transition. If the default transition is 57 defined then the process() method will call the associated action function and 58 then set the current state to the next_state. This lets you define a default 59 transition as a catch-all case. You can think of it as an exception handler. 60 There can be only one default transition. 61 62 Finally, if none of the previous cases are defined for an input_symbol and 63 current_state then the FSM will raise an exception. This may be desirable, but 64 you can always prevent this just by defining a default transition. 65 66 Noah Spurrier 20020822 67 """ 68 69 class ExceptionFSM(Exception): 70 71 """This is the FSM Exception class.""" 72 73 def __init__(self, value): 74 self.value = value 75 76 def __str__(self): 77 return `self.value` 78 79 class FSM: 80 81 """This is a Finite State Machine (FSM). 82 """ 83 84 def __init__(self, initial_state, memory=None): 85 86 """This creates the FSM. You set the initial state here. The "memory" 87 attribute is any object that you want to pass along to the action 88 functions. It is not used by the FSM. For parsing you would typically 89 pass a list to be used as a stack. """ 90 91 # Map (input_symbol, current_state) --> (action, next_state). 92 self.state_transitions = {} 93 # Map (current_state) --> (action, next_state). 94 self.state_transitions_any = {} 95 self.default_transition = None 96 97 self.input_symbol = None 98 self.initial_state = initial_state 99 self.current_state = self.initial_state 100 self.next_state = None 101 self.action = None 102 self.memory = memory 103 104 def reset (self): 105 106 """This sets the current_state to the initial_state and sets 107 input_symbol to None. The initial state was set by the constructor 108 __init__(). """ 109 110 self.current_state = self.initial_state 111 self.input_symbol = None 112 113 def add_transition (self, input_symbol, state, action=None, next_state=None): 114 115 """This adds a transition that associates: 116 117 (input_symbol, current_state) --> (action, next_state) 118 119 The action may be set to None in which case the process() method will 120 ignore the action and only set the next_state. The next_state may be 121 set to None in which case the current state will be unchanged. 122 123 You can also set transitions for a list of symbols by using 124 add_transition_list(). """ 125 126 if next_state is None: 127 next_state = state 128 self.state_transitions[(input_symbol, state)] = (action, next_state) 129 130 def add_transition_list (self, list_input_symbols, state, action=None, next_state=None): 131 132 """This adds the same transition for a list of input symbols. 133 You can pass a list or a string. Note that it is handy to use 134 string.digits, string.whitespace, string.letters, etc. to add 135 transitions that match character classes. 136 137 The action may be set to None in which case the process() method will 138 ignore the action and only set the next_state. The next_state may be 139 set to None in which case the current state will be unchanged. """ 140 141 if next_state is None: 142 next_state = state 143 for input_symbol in list_input_symbols: 144 self.add_transition (input_symbol, state, action, next_state) 145 146 def add_transition_any (self, state, action=None, next_state=None): 147 148 """This adds a transition that associates: 149 150 (current_state) --> (action, next_state) 151 152 That is, any input symbol will match the current state. 153 The process() method checks the "any" state associations after it first 154 checks for an exact match of (input_symbol, current_state). 155 156 The action may be set to None in which case the process() method will 157 ignore the action and only set the next_state. The next_state may be 158 set to None in which case the current state will be unchanged. """ 159 160 if next_state is None: 161 next_state = state 162 self.state_transitions_any [state] = (action, next_state) 163 164 def set_default_transition (self, action, next_state): 165 166 """This sets the default transition. This defines an action and 167 next_state if the FSM cannot find the input symbol and the current 168 state in the transition list and if the FSM cannot find the 169 current_state in the transition_any list. This is useful as a final 170 fall-through state for catching errors and undefined states. 171 172 The default transition can be removed by setting the attribute 173 default_transition to None. """ 174 175 self.default_transition = (action, next_state) 176 177 def get_transition (self, input_symbol, state): 178 179 """This returns (action, next state) given an input_symbol and state. 180 This does not modify the FSM state, so calling this method has no side 181 effects. Normally you do not call this method directly. It is called by 182 process(). 183 184 The sequence of steps to check for a defined transition goes from the 185 most specific to the least specific. 186 187 1. Check state_transitions[] that match exactly the tuple, 188 (input_symbol, state) 189 190 2. Check state_transitions_any[] that match (state) 191 In other words, match a specific state and ANY input_symbol. 192 193 3. Check if the default_transition is defined. 194 This catches any input_symbol and any state. 195 This is a handler for errors, undefined states, or defaults. 196 197 4. No transition was defined. If we get here then raise an exception. 198 """ 199 200 if self.state_transitions.has_key((input_symbol, state)): 201 return self.state_transitions[(input_symbol, state)] 202 elif self.state_transitions_any.has_key (state): 203 return self.state_transitions_any[state] 204 elif self.default_transition is not None: 205 return self.default_transition 206 else: 207 raise ExceptionFSM ('Transition is undefined: (%s, %s).' % 208 (str(input_symbol), str(state)) ) 209 210 def process (self, input_symbol): 211 212 """This is the main method that you call to process input. This may 213 cause the FSM to change state and call an action. This method calls 214 get_transition() to find the action and next_state associated with the 215 input_symbol and current_state. If the action is None then the action 216 is not called and only the current state is changed. This method 217 processes one complete input symbol. You can process a list of symbols 218 (or a string) by calling process_list(). """ 219 220 self.input_symbol = input_symbol 221 (self.action, self.next_state) = self.get_transition (self.input_symbol, self.current_state) 222 if self.action is not None: 223 self.action (self) 224 self.current_state = self.next_state 225 self.next_state = None 226 227 def process_list (self, input_symbols): 228 229 """This takes a list and sends each element to process(). The list may 230 be a string or any iterable object. """ 231 232 for s in input_symbols: 233 self.process (s) 234 235 ############################################################################## 236 # The following is an example that demonstrates the use of the FSM class to 237 # process an RPN expression. Run this module from the command line. You will 238 # get a prompt > for input. Enter an RPN Expression. Numbers may be integers. 239 # Operators are * / + - Use the = sign to evaluate and print the expression. 240 # For example: 241 # 242 # 167 3 2 2 * * * 1 - = 243 # 244 # will print: 245 # 246 # 2003 247 ############################################################################## 248 249 import sys, os, traceback, optparse, time, string 250 251 # 252 # These define the actions. 253 # Note that "memory" is a list being used as a stack. 254 # 255 256 def BeginBuildNumber (fsm): 257 fsm.memory.append (fsm.input_symbol) 258 259 def BuildNumber (fsm): 260 s = fsm.memory.pop () 261 s = s + fsm.input_symbol 262 fsm.memory.append (s) 263 264 def EndBuildNumber (fsm): 265 s = fsm.memory.pop () 266 fsm.memory.append (int(s)) 267 268 def DoOperator (fsm): 269 ar = fsm.memory.pop() 270 al = fsm.memory.pop() 271 if fsm.input_symbol == '+': 272 fsm.memory.append (al + ar) 273 elif fsm.input_symbol == '-': 274 fsm.memory.append (al - ar) 275 elif fsm.input_symbol == '*': 276 fsm.memory.append (al * ar) 277 elif fsm.input_symbol == '/': 278 fsm.memory.append (al / ar) 279 280 def DoEqual (fsm): 281 print str(fsm.memory.pop()) 282 283 def Error (fsm): 284 print 'That does not compute.' 285 print str(fsm.input_symbol) 286 287 def main(): 288 289 """This is where the example starts and the FSM state transitions are 290 defined. Note that states are strings (such as 'INIT'). This is not 291 necessary, but it makes the example easier to read. """ 292 293 f = FSM ('INIT', []) # "memory" will be used as a stack. 294 f.set_default_transition (Error, 'INIT') 295 f.add_transition_any ('INIT', None, 'INIT') 296 f.add_transition ('=', 'INIT', DoEqual, 'INIT') 297 f.add_transition_list (string.digits, 'INIT', BeginBuildNumber, 'BUILDING_NUMBER') 298 f.add_transition_list (string.digits, 'BUILDING_NUMBER', BuildNumber, 'BUILDING_NUMBER') 299 f.add_transition_list (string.whitespace, 'BUILDING_NUMBER', EndBuildNumber, 'INIT') 300 f.add_transition_list ('+-*/', 'INIT', DoOperator, 'INIT') 301 302 print 303 print 'Enter an RPN Expression.' 304 print 'Numbers may be integers. Operators are * / + -' 305 print 'Use the = sign to evaluate and print the expression.' 306 print 'For example: ' 307 print ' 167 3 2 2 * * * 1 - =' 308 inputstr = raw_input ('> ') 309 f.process_list(inputstr) 310 311 if __name__ == '__main__': 312 try: 313 start_time = time.time() 314 parser = optparse.OptionParser(formatter=optparse.TitledHelpFormatter(), usage=globals()['__doc__'], version='$Id: FSM.py 490 2007-12-07 15:46:24Z noah $') 315 parser.add_option ('-v', '--verbose', action='store_true', default=False, help='verbose output') 316 (options, args) = parser.parse_args() 317 if options.verbose: print time.asctime() 318 main() 319 if options.verbose: print time.asctime() 320 if options.verbose: print 'TOTAL TIME IN MINUTES:', 321 if options.verbose: print (time.time() - start_time) / 60.0 322 sys.exit(0) 323 except KeyboardInterrupt, e: # Ctrl-C 324 raise e 325 except SystemExit, e: # sys.exit() 326 raise e 327 except Exception, e: 328 print 'ERROR, UNEXPECTED EXCEPTION' 329 print str(e) 330 traceback.print_exc() 331 os._exit(1) 332
