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