123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349 |
- #!/usr/bin/env python
- """This module implements a Finite State Machine (FSM). In addition to state
- this FSM also maintains a user defined "memory". So this FSM can be used as a
- Push-down Automata (PDA) since a PDA is a FSM + memory.
- The following describes how the FSM works, but you will probably also need to
- see the example function to understand how the FSM is used in practice.
- You define an FSM by building tables of transitions. For a given input symbol
- the process() method uses these tables to decide what action to call and what
- the next state will be. The FSM has a table of transitions that associate:
- (input_symbol, current_state) --> (action, next_state)
- Where "action" is a function you define. The symbols and states can be any
- objects. You use the add_transition() and add_transition_list() methods to add
- to the transition table. The FSM also has a table of transitions that
- associate:
- (current_state) --> (action, next_state)
- You use the add_transition_any() method to add to this transition table. The
- FSM also has one default transition that is not associated with any specific
- input_symbol or state. You use the set_default_transition() method to set the
- default transition.
- When an action function is called it is passed a reference to the FSM. The
- action function may then access attributes of the FSM such as input_symbol,
- current_state, or "memory". The "memory" attribute can be any object that you
- want to pass along to the action functions. It is not used by the FSM itself.
- For parsing you would typically pass a list to be used as a stack.
- The processing sequence is as follows. The process() method is given an
- input_symbol to process. The FSM will search the table of transitions that
- associate:
- (input_symbol, current_state) --> (action, next_state)
- If the pair (input_symbol, current_state) is found then process() will call the
- associated action function and then set the current state to the next_state.
- If the FSM cannot find a match for (input_symbol, current_state) it will then
- search the table of transitions that associate:
- (current_state) --> (action, next_state)
- If the current_state is found then the process() method will call the
- associated action function and then set the current state to the next_state.
- Notice that this table lacks an input_symbol. It lets you define transitions
- for a current_state and ANY input_symbol. Hence, it is called the "any" table.
- Remember, it is always checked after first searching the table for a specific
- (input_symbol, current_state).
- For the case where the FSM did not match either of the previous two cases the
- FSM will try to use the default transition. If the default transition is
- defined then the process() method will call the associated action function and
- then set the current state to the next_state. This lets you define a default
- transition as a catch-all case. You can think of it as an exception handler.
- There can be only one default transition.
- Finally, if none of the previous cases are defined for an input_symbol and
- current_state then the FSM will raise an exception. This may be desirable, but
- you can always prevent this just by defining a default transition.
- Noah Spurrier 20020822
- PEXPECT LICENSE
- This license is approved by the OSI and FSF as GPL-compatible.
- http://opensource.org/licenses/isc-license.txt
- Copyright (c) 2012, Noah Spurrier <noah@noah.org>
- PERMISSION TO USE, COPY, MODIFY, AND/OR DISTRIBUTE THIS SOFTWARE FOR ANY
- PURPOSE WITH OR WITHOUT FEE IS HEREBY GRANTED, PROVIDED THAT THE ABOVE
- COPYRIGHT NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES.
- THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
- """
- class ExceptionFSM(Exception):
- """This is the FSM Exception class."""
- def __init__(self, value):
- self.value = value
- def __str__(self):
- return `self.value`
- class FSM:
- """This is a Finite State Machine (FSM).
- """
- def __init__(self, initial_state, memory=None):
- """This creates the FSM. You set the initial state here. The "memory"
- attribute is any object that you want to pass along to the action
- functions. It is not used by the FSM. For parsing you would typically
- pass a list to be used as a stack. """
- # Map (input_symbol, current_state) --> (action, next_state).
- self.state_transitions = {}
- # Map (current_state) --> (action, next_state).
- self.state_transitions_any = {}
- self.default_transition = None
- self.input_symbol = None
- self.initial_state = initial_state
- self.current_state = self.initial_state
- self.next_state = None
- self.action = None
- self.memory = memory
- def reset (self):
- """This sets the current_state to the initial_state and sets
- input_symbol to None. The initial state was set by the constructor
- __init__(). """
- self.current_state = self.initial_state
- self.input_symbol = None
- def add_transition (self, input_symbol, state, action=None, next_state=None):
- """This adds a transition that associates:
- (input_symbol, current_state) --> (action, next_state)
- The action may be set to None in which case the process() method will
- ignore the action and only set the next_state. The next_state may be
- set to None in which case the current state will be unchanged.
- You can also set transitions for a list of symbols by using
- add_transition_list(). """
- if next_state is None:
- next_state = state
- self.state_transitions[(input_symbol, state)] = (action, next_state)
- def add_transition_list (self, list_input_symbols, state, action=None, next_state=None):
- """This adds the same transition for a list of input symbols.
- You can pass a list or a string. Note that it is handy to use
- string.digits, string.whitespace, string.letters, etc. to add
- transitions that match character classes.
- The action may be set to None in which case the process() method will
- ignore the action and only set the next_state. The next_state may be
- set to None in which case the current state will be unchanged. """
- if next_state is None:
- next_state = state
- for input_symbol in list_input_symbols:
- self.add_transition (input_symbol, state, action, next_state)
- def add_transition_any (self, state, action=None, next_state=None):
- """This adds a transition that associates:
- (current_state) --> (action, next_state)
- That is, any input symbol will match the current state.
- The process() method checks the "any" state associations after it first
- checks for an exact match of (input_symbol, current_state).
- The action may be set to None in which case the process() method will
- ignore the action and only set the next_state. The next_state may be
- set to None in which case the current state will be unchanged. """
- if next_state is None:
- next_state = state
- self.state_transitions_any [state] = (action, next_state)
- def set_default_transition (self, action, next_state):
- """This sets the default transition. This defines an action and
- next_state if the FSM cannot find the input symbol and the current
- state in the transition list and if the FSM cannot find the
- current_state in the transition_any list. This is useful as a final
- fall-through state for catching errors and undefined states.
- The default transition can be removed by setting the attribute
- default_transition to None. """
- self.default_transition = (action, next_state)
- def get_transition (self, input_symbol, state):
- """This returns (action, next state) given an input_symbol and state.
- This does not modify the FSM state, so calling this method has no side
- effects. Normally you do not call this method directly. It is called by
- process().
- The sequence of steps to check for a defined transition goes from the
- most specific to the least specific.
- 1. Check state_transitions[] that match exactly the tuple,
- (input_symbol, state)
- 2. Check state_transitions_any[] that match (state)
- In other words, match a specific state and ANY input_symbol.
- 3. Check if the default_transition is defined.
- This catches any input_symbol and any state.
- This is a handler for errors, undefined states, or defaults.
- 4. No transition was defined. If we get here then raise an exception.
- """
- if self.state_transitions.has_key((input_symbol, state)):
- return self.state_transitions[(input_symbol, state)]
- elif self.state_transitions_any.has_key (state):
- return self.state_transitions_any[state]
- elif self.default_transition is not None:
- return self.default_transition
- else:
- raise ExceptionFSM ('Transition is undefined: (%s, %s).' %
- (str(input_symbol), str(state)) )
- def process (self, input_symbol):
- """This is the main method that you call to process input. This may
- cause the FSM to change state and call an action. This method calls
- get_transition() to find the action and next_state associated with the
- input_symbol and current_state. If the action is None then the action
- is not called and only the current state is changed. This method
- processes one complete input symbol. You can process a list of symbols
- (or a string) by calling process_list(). """
- self.input_symbol = input_symbol
- (self.action, self.next_state) = self.get_transition (self.input_symbol, self.current_state)
- if self.action is not None:
- self.action (self)
- self.current_state = self.next_state
- self.next_state = None
- def process_list (self, input_symbols):
- """This takes a list and sends each element to process(). The list may
- be a string or any iterable object. """
- for s in input_symbols:
- self.process (s)
- ##############################################################################
- # The following is an example that demonstrates the use of the FSM class to
- # process an RPN expression. Run this module from the command line. You will
- # get a prompt > for input. Enter an RPN Expression. Numbers may be integers.
- # Operators are * / + - Use the = sign to evaluate and print the expression.
- # For example:
- #
- # 167 3 2 2 * * * 1 - =
- #
- # will print:
- #
- # 2003
- ##############################################################################
- import sys, os, traceback, optparse, time, string
- #
- # These define the actions.
- # Note that "memory" is a list being used as a stack.
- #
- def BeginBuildNumber (fsm):
- fsm.memory.append (fsm.input_symbol)
- def BuildNumber (fsm):
- s = fsm.memory.pop ()
- s = s + fsm.input_symbol
- fsm.memory.append (s)
- def EndBuildNumber (fsm):
- s = fsm.memory.pop ()
- fsm.memory.append (int(s))
- def DoOperator (fsm):
- ar = fsm.memory.pop()
- al = fsm.memory.pop()
- if fsm.input_symbol == '+':
- fsm.memory.append (al + ar)
- elif fsm.input_symbol == '-':
- fsm.memory.append (al - ar)
- elif fsm.input_symbol == '*':
- fsm.memory.append (al * ar)
- elif fsm.input_symbol == '/':
- fsm.memory.append (al / ar)
- def DoEqual (fsm):
- print str(fsm.memory.pop())
- def Error (fsm):
- print 'That does not compute.'
- print str(fsm.input_symbol)
- def main():
- """This is where the example starts and the FSM state transitions are
- defined. Note that states are strings (such as 'INIT'). This is not
- necessary, but it makes the example easier to read. """
- f = FSM ('INIT', []) # "memory" will be used as a stack.
- f.set_default_transition (Error, 'INIT')
- f.add_transition_any ('INIT', None, 'INIT')
- f.add_transition ('=', 'INIT', DoEqual, 'INIT')
- f.add_transition_list (string.digits, 'INIT', BeginBuildNumber, 'BUILDING_NUMBER')
- f.add_transition_list (string.digits, 'BUILDING_NUMBER', BuildNumber, 'BUILDING_NUMBER')
- f.add_transition_list (string.whitespace, 'BUILDING_NUMBER', EndBuildNumber, 'INIT')
- f.add_transition_list ('+-*/', 'INIT', DoOperator, 'INIT')
- print
- print 'Enter an RPN Expression.'
- print 'Numbers may be integers. Operators are * / + -'
- print 'Use the = sign to evaluate and print the expression.'
- print 'For example: '
- print ' 167 3 2 2 * * * 1 - ='
- inputstr = raw_input ('> ')
- f.process_list(inputstr)
- if __name__ == '__main__':
- try:
- start_time = time.time()
- parser = optparse.OptionParser(formatter=optparse.TitledHelpFormatter(), usage=globals()['__doc__'], version='$Id: FSM.py 533 2012-10-20 02:19:33Z noah $')
- parser.add_option ('-v', '--verbose', action='store_true', default=False, help='verbose output')
- (options, args) = parser.parse_args()
- if options.verbose: print time.asctime()
- main()
- if options.verbose: print time.asctime()
- if options.verbose: print 'TOTAL TIME IN MINUTES:',
- if options.verbose: print (time.time() - start_time) / 60.0
- sys.exit(0)
- except KeyboardInterrupt, e: # Ctrl-C
- raise e
- except SystemExit, e: # sys.exit()
- raise e
- except Exception, e:
- print 'ERROR, UNEXPECTED EXCEPTION'
- print str(e)
- traceback.print_exc()
- os._exit(1)
|