Home | History | Annotate | Download | only in pexpect
      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 (at] 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)
    350