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 PEXPECT LICENSE 69 70 This license is approved by the OSI and FSF as GPL-compatible. 71 http://opensource.org/licenses/isc-license.txt 72 73 Copyright (c) 2012, Noah Spurrier <noah (at] noah.org> 74 PERMISSION TO USE, COPY, MODIFY, AND/OR DISTRIBUTE THIS SOFTWARE FOR ANY 75 PURPOSE WITH OR WITHOUT FEE IS HEREBY GRANTED, PROVIDED THAT THE ABOVE 76 COPYRIGHT NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES. 77 THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 78 WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 79 MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 80 ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 81 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 82 ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 83 OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 84 85 """ 86 87 class ExceptionFSM(Exception): 88 89 """This is the FSM Exception class.""" 90 91 def __init__(self, value): 92 self.value = value 93 94 def __str__(self): 95 return `self.value` 96 97 class FSM: 98 99 """This is a Finite State Machine (FSM). 100 """ 101 102 def __init__(self, initial_state, memory=None): 103 104 """This creates the FSM. You set the initial state here. The "memory" 105 attribute is any object that you want to pass along to the action 106 functions. It is not used by the FSM. For parsing you would typically 107 pass a list to be used as a stack. """ 108 109 # Map (input_symbol, current_state) --> (action, next_state). 110 self.state_transitions = {} 111 # Map (current_state) --> (action, next_state). 112 self.state_transitions_any = {} 113 self.default_transition = None 114 115 self.input_symbol = None 116 self.initial_state = initial_state 117 self.current_state = self.initial_state 118 self.next_state = None 119 self.action = None 120 self.memory = memory 121 122 def reset (self): 123 124 """This sets the current_state to the initial_state and sets 125 input_symbol to None. The initial state was set by the constructor 126 __init__(). """ 127 128 self.current_state = self.initial_state 129 self.input_symbol = None 130 131 def add_transition (self, input_symbol, state, action=None, next_state=None): 132 133 """This adds a transition that associates: 134 135 (input_symbol, current_state) --> (action, next_state) 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 You can also set transitions for a list of symbols by using 142 add_transition_list(). """ 143 144 if next_state is None: 145 next_state = state 146 self.state_transitions[(input_symbol, state)] = (action, next_state) 147 148 def add_transition_list (self, list_input_symbols, state, action=None, next_state=None): 149 150 """This adds the same transition for a list of input symbols. 151 You can pass a list or a string. Note that it is handy to use 152 string.digits, string.whitespace, string.letters, etc. to add 153 transitions that match character classes. 154 155 The action may be set to None in which case the process() method will 156 ignore the action and only set the next_state. The next_state may be 157 set to None in which case the current state will be unchanged. """ 158 159 if next_state is None: 160 next_state = state 161 for input_symbol in list_input_symbols: 162 self.add_transition (input_symbol, state, action, next_state) 163 164 def add_transition_any (self, state, action=None, next_state=None): 165 166 """This adds a transition that associates: 167 168 (current_state) --> (action, next_state) 169 170 That is, any input symbol will match the current state. 171 The process() method checks the "any" state associations after it first 172 checks for an exact match of (input_symbol, current_state). 173 174 The action may be set to None in which case the process() method will 175 ignore the action and only set the next_state. The next_state may be 176 set to None in which case the current state will be unchanged. """ 177 178 if next_state is None: 179 next_state = state 180 self.state_transitions_any [state] = (action, next_state) 181 182 def set_default_transition (self, action, next_state): 183 184 """This sets the default transition. This defines an action and 185 next_state if the FSM cannot find the input symbol and the current 186 state in the transition list and if the FSM cannot find the 187 current_state in the transition_any list. This is useful as a final 188 fall-through state for catching errors and undefined states. 189 190 The default transition can be removed by setting the attribute 191 default_transition to None. """ 192 193 self.default_transition = (action, next_state) 194 195 def get_transition (self, input_symbol, state): 196 197 """This returns (action, next state) given an input_symbol and state. 198 This does not modify the FSM state, so calling this method has no side 199 effects. Normally you do not call this method directly. It is called by 200 process(). 201 202 The sequence of steps to check for a defined transition goes from the 203 most specific to the least specific. 204 205 1. Check state_transitions[] that match exactly the tuple, 206 (input_symbol, state) 207 208 2. Check state_transitions_any[] that match (state) 209 In other words, match a specific state and ANY input_symbol. 210 211 3. Check if the default_transition is defined. 212 This catches any input_symbol and any state. 213 This is a handler for errors, undefined states, or defaults. 214 215 4. No transition was defined. If we get here then raise an exception. 216 """ 217 218 if self.state_transitions.has_key((input_symbol, state)): 219 return self.state_transitions[(input_symbol, state)] 220 elif self.state_transitions_any.has_key (state): 221 return self.state_transitions_any[state] 222 elif self.default_transition is not None: 223 return self.default_transition 224 else: 225 raise ExceptionFSM ('Transition is undefined: (%s, %s).' % 226 (str(input_symbol), str(state)) ) 227 228 def process (self, input_symbol): 229 230 """This is the main method that you call to process input. This may 231 cause the FSM to change state and call an action. This method calls 232 get_transition() to find the action and next_state associated with the 233 input_symbol and current_state. If the action is None then the action 234 is not called and only the current state is changed. This method 235 processes one complete input symbol. You can process a list of symbols 236 (or a string) by calling process_list(). """ 237 238 self.input_symbol = input_symbol 239 (self.action, self.next_state) = self.get_transition (self.input_symbol, self.current_state) 240 if self.action is not None: 241 self.action (self) 242 self.current_state = self.next_state 243 self.next_state = None 244 245 def process_list (self, input_symbols): 246 247 """This takes a list and sends each element to process(). The list may 248 be a string or any iterable object. """ 249 250 for s in input_symbols: 251 self.process (s) 252 253 ############################################################################## 254 # The following is an example that demonstrates the use of the FSM class to 255 # process an RPN expression. Run this module from the command line. You will 256 # get a prompt > for input. Enter an RPN Expression. Numbers may be integers. 257 # Operators are * / + - Use the = sign to evaluate and print the expression. 258 # For example: 259 # 260 # 167 3 2 2 * * * 1 - = 261 # 262 # will print: 263 # 264 # 2003 265 ############################################################################## 266 267 import sys, os, traceback, optparse, time, string 268 269 # 270 # These define the actions. 271 # Note that "memory" is a list being used as a stack. 272 # 273 274 def BeginBuildNumber (fsm): 275 fsm.memory.append (fsm.input_symbol) 276 277 def BuildNumber (fsm): 278 s = fsm.memory.pop () 279 s = s + fsm.input_symbol 280 fsm.memory.append (s) 281 282 def EndBuildNumber (fsm): 283 s = fsm.memory.pop () 284 fsm.memory.append (int(s)) 285 286 def DoOperator (fsm): 287 ar = fsm.memory.pop() 288 al = fsm.memory.pop() 289 if fsm.input_symbol == '+': 290 fsm.memory.append (al + ar) 291 elif fsm.input_symbol == '-': 292 fsm.memory.append (al - ar) 293 elif fsm.input_symbol == '*': 294 fsm.memory.append (al * ar) 295 elif fsm.input_symbol == '/': 296 fsm.memory.append (al / ar) 297 298 def DoEqual (fsm): 299 print str(fsm.memory.pop()) 300 301 def Error (fsm): 302 print 'That does not compute.' 303 print str(fsm.input_symbol) 304 305 def main(): 306 307 """This is where the example starts and the FSM state transitions are 308 defined. Note that states are strings (such as 'INIT'). This is not 309 necessary, but it makes the example easier to read. """ 310 311 f = FSM ('INIT', []) # "memory" will be used as a stack. 312 f.set_default_transition (Error, 'INIT') 313 f.add_transition_any ('INIT', None, 'INIT') 314 f.add_transition ('=', 'INIT', DoEqual, 'INIT') 315 f.add_transition_list (string.digits, 'INIT', BeginBuildNumber, 'BUILDING_NUMBER') 316 f.add_transition_list (string.digits, 'BUILDING_NUMBER', BuildNumber, 'BUILDING_NUMBER') 317 f.add_transition_list (string.whitespace, 'BUILDING_NUMBER', EndBuildNumber, 'INIT') 318 f.add_transition_list ('+-*/', 'INIT', DoOperator, 'INIT') 319 320 print 321 print 'Enter an RPN Expression.' 322 print 'Numbers may be integers. Operators are * / + -' 323 print 'Use the = sign to evaluate and print the expression.' 324 print 'For example: ' 325 print ' 167 3 2 2 * * * 1 - =' 326 inputstr = raw_input ('> ') 327 f.process_list(inputstr) 328 329 if __name__ == '__main__': 330 try: 331 start_time = time.time() 332 parser = optparse.OptionParser(formatter=optparse.TitledHelpFormatter(), usage=globals()['__doc__'], version='$Id: FSM.py 533 2012-10-20 02:19:33Z noah $') 333 parser.add_option ('-v', '--verbose', action='store_true', default=False, help='verbose output') 334 (options, args) = parser.parse_args() 335 if options.verbose: print time.asctime() 336 main() 337 if options.verbose: print time.asctime() 338 if options.verbose: print 'TOTAL TIME IN MINUTES:', 339 if options.verbose: print (time.time() - start_time) / 60.0 340 sys.exit(0) 341 except KeyboardInterrupt, e: # Ctrl-C 342 raise e 343 except SystemExit, e: # sys.exit() 344 raise e 345 except Exception, e: 346 print 'ERROR, UNEXPECTED EXCEPTION' 347 print str(e) 348 traceback.print_exc() 349 os._exit(1) 350
