1#!/usr/bin/env python
2
3"""This module implements a Finite State Machine (FSM). In addition to state
4this FSM also maintains a user defined "memory". So this FSM can be used as a
5Push-down Automata (PDA) since a PDA is a FSM + memory.
6
7The following describes how the FSM works, but you will probably also need to
8see the example function to understand how the FSM is used in practice.
9
10You define an FSM by building tables of transitions. For a given input symbol
11the process() method uses these tables to decide what action to call and what
12the next state will be. The FSM has a table of transitions that associate:
13
14        (input_symbol, current_state) --> (action, next_state)
15
16Where "action" is a function you define. The symbols and states can be any
17objects. You use the add_transition() and add_transition_list() methods to add
18to the transition table. The FSM also has a table of transitions that
19associate:
20
21        (current_state) --> (action, next_state)
22
23You use the add_transition_any() method to add to this transition table. The
24FSM also has one default transition that is not associated with any specific
25input_symbol or state. You use the set_default_transition() method to set the
26default transition.
27
28When an action function is called it is passed a reference to the FSM. The
29action function may then access attributes of the FSM such as input_symbol,
30current_state, or "memory". The "memory" attribute can be any object that you
31want to pass along to the action functions. It is not used by the FSM itself.
32For parsing you would typically pass a list to be used as a stack.
33
34The processing sequence is as follows. The process() method is given an
35input_symbol to process. The FSM will search the table of transitions that
36associate:
37
38        (input_symbol, current_state) --> (action, next_state)
39
40If the pair (input_symbol, current_state) is found then process() will call the
41associated action function and then set the current state to the next_state.
42
43If the FSM cannot find a match for (input_symbol, current_state) it will then
44search the table of transitions that associate:
45
46        (current_state) --> (action, next_state)
47
48If the current_state is found then the process() method will call the
49associated action function and then set the current state to the next_state.
50Notice that this table lacks an input_symbol. It lets you define transitions
51for a current_state and ANY input_symbol. Hence, it is called the "any" table.
52Remember, it is always checked after first searching the table for a specific
53(input_symbol, current_state).
54
55For the case where the FSM did not match either of the previous two cases the
56FSM will try to use the default transition. If the default transition is
57defined then the process() method will call the associated action function and
58then set the current state to the next_state. This lets you define a default
59transition as a catch-all case. You can think of it as an exception handler.
60There can be only one default transition.
61
62Finally, if none of the previous cases are defined for an input_symbol and
63current_state then the FSM will raise an exception. This may be desirable, but
64you can always prevent this just by defining a default transition.
65
66Noah Spurrier 20020822
67"""
68
69class ExceptionFSM(Exception):
70
71    """This is the FSM Exception class."""
72
73    def __init__(self, value):
74        self.value = value
75
76    def __str__(self):
77        return `self.value`
78
79class FSM:
80
81    """This is a Finite State Machine (FSM).
82    """
83
84    def __init__(self, initial_state, memory=None):
85
86        """This creates the FSM. You set the initial state here. The "memory"
87        attribute is any object that you want to pass along to the action
88        functions. It is not used by the FSM. For parsing you would typically
89        pass a list to be used as a stack. """
90
91        # Map (input_symbol, current_state) --> (action, next_state).
92        self.state_transitions = {}
93        # Map (current_state) --> (action, next_state).
94        self.state_transitions_any = {}
95        self.default_transition = None
96
97        self.input_symbol = None
98        self.initial_state = initial_state
99        self.current_state = self.initial_state
100        self.next_state = None
101        self.action = None
102        self.memory = memory
103
104    def reset (self):
105
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 (self, input_symbol, state, action=None, next_state=None):
114
115        """This adds a transition that associates:
116
117                (input_symbol, current_state) --> (action, next_state)
118
119        The action may be set to None in which case the process() method will
120        ignore the action and only set the next_state. The next_state may be
121        set to None in which case the current state will be unchanged.
122
123        You can also set transitions for a list of symbols by using
124        add_transition_list(). """
125
126        if next_state is None:
127            next_state = state
128        self.state_transitions[(input_symbol, state)] = (action, next_state)
129
130    def add_transition_list (self, list_input_symbols, state, action=None, next_state=None):
131
132        """This adds the same transition for a list of input symbols.
133        You can pass a list or a string. Note that it is handy to use
134        string.digits, string.whitespace, string.letters, etc. to add
135        transitions that match character classes.
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        if next_state is None:
142            next_state = state
143        for input_symbol in list_input_symbols:
144            self.add_transition (input_symbol, state, action, next_state)
145
146    def add_transition_any (self, state, action=None, next_state=None):
147
148        """This adds a transition that associates:
149
150                (current_state) --> (action, next_state)
151
152        That is, any input symbol will match the current state.
153        The process() method checks the "any" state associations after it first
154        checks for an exact match of (input_symbol, current_state).
155
156        The action may be set to None in which case the process() method will
157        ignore the action and only set the next_state. The next_state may be
158        set to None in which case the current state will be unchanged. """
159
160        if next_state is None:
161            next_state = state
162        self.state_transitions_any [state] = (action, next_state)
163
164    def set_default_transition (self, action, next_state):
165
166        """This sets the default transition. This defines an action and
167        next_state if the FSM cannot find the input symbol and the current
168        state in the transition list and if the FSM cannot find the
169        current_state in the transition_any list. This is useful as a final
170        fall-through state for catching errors and undefined states.
171
172        The default transition can be removed by setting the attribute
173        default_transition to None. """
174
175        self.default_transition = (action, next_state)
176
177    def get_transition (self, input_symbol, state):
178
179        """This returns (action, next state) given an input_symbol and state.
180        This does not modify the FSM state, so calling this method has no side
181        effects. Normally you do not call this method directly. It is called by
182        process().
183
184        The sequence of steps to check for a defined transition goes from the
185        most specific to the least specific.
186
187        1. Check state_transitions[] that match exactly the tuple,
188            (input_symbol, state)
189
190        2. Check state_transitions_any[] that match (state)
191            In other words, match a specific state and ANY input_symbol.
192
193        3. Check if the default_transition is defined.
194            This catches any input_symbol and any state.
195            This is a handler for errors, undefined states, or defaults.
196
197        4. No transition was defined. If we get here then raise an exception.
198        """
199
200        if self.state_transitions.has_key((input_symbol, state)):
201            return self.state_transitions[(input_symbol, state)]
202        elif self.state_transitions_any.has_key (state):
203            return self.state_transitions_any[state]
204        elif self.default_transition is not None:
205            return self.default_transition
206        else:
207            raise ExceptionFSM ('Transition is undefined: (%s, %s).' %
208                (str(input_symbol), str(state)) )
209
210    def process (self, input_symbol):
211
212        """This is the main method that you call to process input. This may
213        cause the FSM to change state and call an action. This method calls
214        get_transition() to find the action and next_state associated with the
215        input_symbol and current_state. If the action is None then the action
216        is not called and only the current state is changed. This method
217        processes one complete input symbol. You can process a list of symbols
218        (or a string) by calling process_list(). """
219
220        self.input_symbol = input_symbol
221        (self.action, self.next_state) = self.get_transition (self.input_symbol, self.current_state)
222        if self.action is not None:
223            self.action (self)
224        self.current_state = self.next_state
225        self.next_state = None
226
227    def process_list (self, input_symbols):
228
229        """This takes a list and sends each element to process(). The list may
230        be a string or any iterable object. """
231
232        for s in input_symbols:
233            self.process (s)
234
235##############################################################################
236# The following is an example that demonstrates the use of the FSM class to
237# process an RPN expression. Run this module from the command line. You will
238# get a prompt > for input. Enter an RPN Expression. Numbers may be integers.
239# Operators are * / + - Use the = sign to evaluate and print the expression.
240# For example:
241#
242#    167 3 2 2 * * * 1 - =
243#
244# will print:
245#
246#    2003
247##############################################################################
248
249import sys, os, traceback, optparse, time, string
250
251#
252# These define the actions.
253# Note that "memory" is a list being used as a stack.
254#
255
256def BeginBuildNumber (fsm):
257    fsm.memory.append (fsm.input_symbol)
258
259def BuildNumber (fsm):
260    s = fsm.memory.pop ()
261    s = s + fsm.input_symbol
262    fsm.memory.append (s)
263
264def EndBuildNumber (fsm):
265    s = fsm.memory.pop ()
266    fsm.memory.append (int(s))
267
268def DoOperator (fsm):
269    ar = fsm.memory.pop()
270    al = fsm.memory.pop()
271    if fsm.input_symbol == '+':
272        fsm.memory.append (al + ar)
273    elif fsm.input_symbol == '-':
274        fsm.memory.append (al - ar)
275    elif fsm.input_symbol == '*':
276        fsm.memory.append (al * ar)
277    elif fsm.input_symbol == '/':
278        fsm.memory.append (al / ar)
279
280def DoEqual (fsm):
281    print str(fsm.memory.pop())
282
283def Error (fsm):
284    print 'That does not compute.'
285    print str(fsm.input_symbol)
286
287def main():
288
289    """This is where the example starts and the FSM state transitions are
290    defined. Note that states are strings (such as 'INIT'). This is not
291    necessary, but it makes the example easier to read. """
292
293    f = FSM ('INIT', []) # "memory" will be used as a stack.
294    f.set_default_transition (Error, 'INIT')
295    f.add_transition_any  ('INIT', None, 'INIT')
296    f.add_transition      ('=',               'INIT',            DoEqual,          'INIT')
297    f.add_transition_list (string.digits,     'INIT',            BeginBuildNumber, 'BUILDING_NUMBER')
298    f.add_transition_list (string.digits,     'BUILDING_NUMBER', BuildNumber,      'BUILDING_NUMBER')
299    f.add_transition_list (string.whitespace, 'BUILDING_NUMBER', EndBuildNumber,   'INIT')
300    f.add_transition_list ('+-*/',            'INIT',            DoOperator,       'INIT')
301
302    print
303    print 'Enter an RPN Expression.'
304    print 'Numbers may be integers. Operators are * / + -'
305    print 'Use the = sign to evaluate and print the expression.'
306    print 'For example: '
307    print '    167 3 2 2 * * * 1 - ='
308    inputstr = raw_input ('> ')
309    f.process_list(inputstr)
310
311if __name__ == '__main__':
312    try:
313        start_time = time.time()
314        parser = optparse.OptionParser(formatter=optparse.TitledHelpFormatter(), usage=globals()['__doc__'], version='$Id: FSM.py 490 2007-12-07 15:46:24Z noah $')
315        parser.add_option ('-v', '--verbose', action='store_true', default=False, help='verbose output')
316        (options, args) = parser.parse_args()
317        if options.verbose: print time.asctime()
318        main()
319        if options.verbose: print time.asctime()
320        if options.verbose: print 'TOTAL TIME IN MINUTES:',
321        if options.verbose: print (time.time() - start_time) / 60.0
322        sys.exit(0)
323    except KeyboardInterrupt, e: # Ctrl-C
324        raise e
325    except SystemExit, e: # sys.exit()
326        raise e
327    except Exception, e:
328        print 'ERROR, UNEXPECTED EXCEPTION'
329        print str(e)
330        traceback.print_exc()
331        os._exit(1)
332