--- /dev/null
+#!/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
+"""
+
+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 490 2007-12-07 15:46:24Z 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)
git.ucc.asn.au / progcomp10.git / blobdiff
UCC git Repository :: git.ucc.asn.au