src/third_party/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 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@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)