src/link/pexpect/FSM.py

   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)