00001 #!/usr/local/bin python 00002 # This was found at http://www.noah.org/python/FSM/ on November 12, 2002. 00003 # RiC slightly modified it 11/13/02. 00004 # __author__ below means responsible party, not author in the usual sense. 00005 00006 __facility__ = "Online" 00007 __abstract__ = "Finite State Machine class" 00008 __author__ = "R. Claus <Claus@SLAC.Stanford.edu> SLAC - GLAST LAT I&T/Online" 00009 __date__ = "11/12/2002" 00010 __version__ = "$Revision: 2.0 $" 00011 __credits__ = "SLAC" 00012 00013 00014 00015 '''This module implements a Finite State Machine (FSM). 00016 In addition to state this FSM also maintains a user defined "something". 00017 This "something" is effectively memory, so this FSM could be considered 00018 a Push-down Automata (PDA) since a PDA is a FSM + memory. 00019 00020 The following describes how the FSM works, but you will probably also need 00021 to see the example function to understand how the FSM is used in practice. 00022 00023 You define an FSM by building tables of transitions. 00024 For a given input symbol the process() method uses these tables 00025 to decide what action to call and what the next state will be. 00026 The FSM has a table of transitions that associate: 00027 (input_symbol, current_state) --> (action, next_state) 00028 where "action" is a function you define. The symbols and states 00029 can be any objects. You use the add_transition() and add_transition_list() 00030 methods to add to the transition table. The FSM also has a table 00031 of transitions that associate: 00032 (current_state) --> (action, next_state) 00033 You use the add_transition_any() method to add to this transition table. 00034 The FSM also has one default transition that is not associated 00035 with any specific input_symbol or state. You use the 00036 set_default_transition() method to set the default transition. 00037 00038 When an action function is called it is passed a reference to the FSM. 00039 The action function may then access attributes of the FSM such as 00040 input_symbol, current_state, or "something". The "something" attribute 00041 can be any object that you want to pass along to the action functions. 00042 It is not used by the FSM. For parsing you would typically pass a list 00043 to be used as a stack. 00044 00045 The processing sequence is as follows. 00046 The process() method is given an input_symbol to process. 00047 The FSM will search the table of transitions that associate: 00048 (input_symbol, current_state) --> (action, next_state) 00049 If the pair (input_symbol, current_state) is found then 00050 process() will call the associated action function and then set the 00051 current state to the next_state. 00052 00053 If the FSM cannot find a match for (input_symbol, current_state) 00054 it will then search the table of transitions that associate: 00055 (current_state) --> (action, next_state) 00056 If the current_state is found then the process() method will call 00057 the associated action function and then set the current state to 00058 the next_state. Notice that this table lacks an input_symbol. 00059 It lets you define transitions for a current_state and ANY input_symbol. 00060 Hence, it is called the "any" table. Remember, it is always checked 00061 after first searching the table for a specific (input_symbol, current_state). 00062 00063 For the case where the FSM did not match either of the previous two cases 00064 the FSM will try to use the default transition. If the default transition 00065 is defined then the process() method will call the associated action function 00066 and then set the current state to the next_state. This lets you define 00067 a default transition as a catch-all case. You can think of it as an 00068 exception handler. There can be only one default transition. 00069 00070 Finally, if none of the previous cases are defined for an input_symbol 00071 and current_state then the FSM will raise an exception. 00072 This may be desirable, but you can always prevent this just by 00073 defining a default transition. 00074 00075 Noah Spurrier 20020822 00076 ''' 00077 00078 import exceptions 00079 00080 00081 class ExceptionFSM(exceptions.Exception): 00082 '''This is the FSM Exception class.''' 00083 def __init__(self, value): 00084 self.value = value 00085 def __str__(self): 00086 return `self.value` 00087 00088 class FSM(object): 00089 '''This is a Finite State Machine (FSM). 00090 ''' 00091 00092 def __init__(self, initial_state, something): 00093 '''This creates the FSM. 00094 You set the initial state here. The "something" attribute is any 00095 object that you want to pass along to the action functions. 00096 It is not used by the FSM. For parsing you would typically pass 00097 a list to be used as a stack. 00098 ''' 00099 # Map (input_symbol, current_state) --> (action, next_state). 00100 self.state_transitions = {} 00101 # Map (current_state) --> (action, next_state). 00102 self.state_transitions_any = {} 00103 self.default_transition = None 00104 00105 self.input_symbol = None 00106 self.initial_state = initial_state 00107 self.current_state = self.initial_state 00108 self.something = something 00109 00110 def reset (self): 00111 '''This sets the current_state to the initial_state and 00112 sets input_symbol to None. 00113 The initial state was set by the constructor __init__(). 00114 ''' 00115 self.current_state = self.initial_state 00116 self.input_symbol = None 00117 00118 def add_transition (self, input_symbol, state, action, next_state): 00119 '''This adds a transition that associates 00120 (input_symbol, current_state) --> (action, next_state) 00121 The action may be set to None in which case the process() method 00122 will ignore the action and only set the next_state. 00123 00124 You can also set transitions for a list of symbols by using 00125 add_transition_list(). 00126 ''' 00127 self.state_transitions[(input_symbol, state)] = (action, next_state) 00128 00129 def add_transition_list (self, list_input_symbols, state, action, next_state): 00130 '''This adds the same transition for lots of different input symbols. 00131 You can pass a list or a string. Note that it is handy to use 00132 string.digits, string.whitespace, string.letters, etc. to add 00133 transitions that match character classes. 00134 ''' 00135 for input_symbol in list_input_symbols: 00136 self.add_transition (input_symbol, state, action, next_state) 00137 00138 def add_transition_any (self, state, action, next_state): 00139 '''This adds a transition that associates 00140 (current_state) --> (action, next_state) 00141 The process() method checks these associations if it cannot 00142 first find a match of an (input_symbol, current_state). 00143 ''' 00144 self.state_transitions_any [state] = (action, next_state) 00145 00146 def set_default_transition (self, action, next_state): 00147 '''This sets the default transition. 00148 This defines an action and next_state if the FSM cannot find the 00149 input symbol and the current state in the transition list and 00150 if the FSM cannot find the current_state in the transition_any list. 00151 This is useful for catching errors and undefined states. 00152 00153 The default transition can be removed by setting the attribute 00154 default_transition to None. 00155 ''' 00156 self.default_transition = (action, next_state) 00157 00158 def get_transition (self, input_symbol, state): 00159 '''This returns (action, next state) given an input_symbol and state. 00160 This leaves the FSM unchanged. This does not update the current state 00161 nor does it trigger the output action. Normally you do not call 00162 this method. It is called by process(). 00163 00164 The sequence of steps to check for a defined transition goes from 00165 the most specific to the least specific. 00166 1. Check state_transitions[] that match (input_symbol, state) 00167 2. Check state_transitions_any[] that match (state) 00168 In other words, match a specific state and ANY input_symbol. 00169 3. Check if the default_transition is defined. 00170 This catches any input_symbol and any state. 00171 This is a handler for errors, undefined states, or defaults. 00172 4. No transition was defined. If we get here then raise an exception. 00173 ''' 00174 if self.state_transitions.has_key((input_symbol, self.current_state)): 00175 return self.state_transitions[(input_symbol, self.current_state)] 00176 elif self.state_transitions_any.has_key (self.current_state): 00177 return self.state_transitions_any[self.current_state] 00178 elif self.default_transition != None: 00179 return self.default_transition 00180 else: 00181 raise ExceptionFSM ('Transition is undefined: (%s, %s).' % 00182 (str(input_symbol), str(self.current_state)) ) 00183 00184 def process (self, input_symbol): 00185 '''This is the main method that you call to process input. 00186 This may cause the FSM to change state and call an action. 00187 This method calls get_transition() to find the action and next_state 00188 associated with the input_symbol and current_state. 00189 If the action is None then the action is not called and 00190 only the current state is changed. 00191 This method processes one input symbol. You can process a list of 00192 symbols (or a string) by calling process_list(). 00193 This method returns an uninterpreted status value used to indicate 00194 whether the state transition completed successfully. 00195 ''' 00196 self.input_symbol = input_symbol 00197 (action, next_state) = self.get_transition (self.input_symbol, self.current_state) 00198 if action != None: 00199 status = action () 00200 if status is None and next_state is not None: 00201 self.current_state = next_state 00202 return status 00203 00204 def process_list (self, s): 00205 '''This takes a list and sends each element to process(). 00206 The list may be a string. 00207 ''' 00208 for c in s: 00209 self.process (c) 00210 00211 ########################################################################## 00212 # The following example demonstrates the use of the FSM class in 00213 # processing RPN expressions. Run this module from the command line. 00214 # You will get a prompt > for input. 00215 # Enter an RPN Expression. 00216 # Numbers may be integers. Operators are * / + - 00217 # Use the = sign to evaluate and print the expression. 00218 # For example: 00219 # 167 3 2 2 * * * 1 - = 00220 # will print: 00221 # 2003 00222 ########################################################################## 00223 00224 import string 00225 00226 # 00227 # These define the actions. 00228 # Note that "something" is a list being used as a stack. 00229 # 00230 def BeginBuildNumber (fsm): 00231 fsm.something.append (fsm.input_symbol) 00232 def BuildNumber (fsm): 00233 s = fsm.something.pop () 00234 s = s + fsm.input_symbol 00235 fsm.something.append (s) 00236 def EndBuildNumber (fsm): 00237 s = fsm.something.pop () 00238 fsm.something.append (int(s)) 00239 def DoOperator (fsm): 00240 ar = fsm.something.pop() 00241 al = fsm.something.pop() 00242 if fsm.input_symbol == '+': 00243 fsm.something.append (al + ar) 00244 elif fsm.input_symbol == '-': 00245 fsm.something.append (al - ar) 00246 elif fsm.input_symbol == '*': 00247 fsm.something.append (al * ar) 00248 elif fsm.input_symbol == '/': 00249 fsm.something.append (al / ar) 00250 def DoEqual (fsm): 00251 print str(fsm.something.pop()) 00252 def Error (fsm): 00253 print 'That does not compute.' 00254 print str(fsm.input_symbol) 00255 00256 # 00257 # This is where the example starts and the FSM state transitions are defined. 00258 # Note that states (such as 'INIT') are strings. This is not necessary, but 00259 # it makes the example easier to read. 00260 # 00261 def example (): 00262 f = FSM ('INIT', []) # "something" will be used as a stack. 00263 f.set_default_transition (Error, 'INIT') 00264 f.add_transition_any ('INIT', None, 'INIT') 00265 f.add_transition ('=', 'INIT', DoEqual, 'INIT') 00266 f.add_transition_list (string.digits, 'INIT', BeginBuildNumber, 'BUILDING_NUMBER') 00267 f.add_transition_list (string.digits, 'BUILDING_NUMBER', BuildNumber, 'BUILDING_NUMBER') 00268 f.add_transition_list (string.whitespace, 'BUILDING_NUMBER', EndBuildNumber, 'INIT') 00269 f.add_transition_list ('+-*/', 'INIT', DoOperator, 'INIT') 00270 00271 print 00272 print 'Enter an RPN Expression.' 00273 print 'Numbers may be integers. Operators are * / + -' 00274 print 'Use the = sign to evaluate and print the expression.' 00275 print 'For example: ' 00276 print ' 167 3 2 2 * * * 1 - =' 00277 inputs = raw_input ('>') 00278 for s in inputs: 00279 f.process (s) 00280 00281 if __name__ == '__main__': 00282 example ()