00001
00002
00003
00004
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__ = "2002/11/12 00:00:00"
00010 __updated__ = "$Date: 2005/07/28 01:16:33 $"
00011 __version__ = "$Revision: 1.2 $"
00012 __credits__ = "SLAC"
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
00100 self.state_transitions = {}
00101
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
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224 import string
00225
00226
00227
00228
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
00258
00259
00260
00261 def example ():
00262 f = FSM ('INIT', [])
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 ()