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
68PEXPECT 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
87class 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 'ExceptionFSM: ' + str(self.value)
96
97class 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 (input_symbol, state) in self.state_transitions:
219            return self.state_transitions[(input_symbol, state)]
220        elif state in self.state_transitions_any:
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
267import sys
268import string
269
270PY3 = (sys.version_info[0] >= 3)
271
272#
273# These define the actions.
274# Note that "memory" is a list being used as a stack.
275#
276
277def BeginBuildNumber (fsm):
278    fsm.memory.append (fsm.input_symbol)
279
280def BuildNumber (fsm):
281    s = fsm.memory.pop ()
282    s = s + fsm.input_symbol
283    fsm.memory.append (s)
284
285def EndBuildNumber (fsm):
286    s = fsm.memory.pop ()
287    fsm.memory.append (int(s))
288
289def DoOperator (fsm):
290    ar = fsm.memory.pop()
291    al = fsm.memory.pop()
292    if fsm.input_symbol == '+':
293        fsm.memory.append (al + ar)
294    elif fsm.input_symbol == '-':
295        fsm.memory.append (al - ar)
296    elif fsm.input_symbol == '*':
297        fsm.memory.append (al * ar)
298    elif fsm.input_symbol == '/':
299        fsm.memory.append (al / ar)
300
301def DoEqual (fsm):
302    print(str(fsm.memory.pop()))
303
304def Error (fsm):
305    print('That does not compute.')
306    print(str(fsm.input_symbol))
307
308def main():
309
310    '''This is where the example starts and the FSM state transitions are
311    defined. Note that states are strings (such as 'INIT'). This is not
312    necessary, but it makes the example easier to read. '''
313
314    f = FSM ('INIT', [])
315    f.set_default_transition (Error, 'INIT')
316    f.add_transition_any  ('INIT', None, 'INIT')
317    f.add_transition      ('=',               'INIT',            DoEqual,          'INIT')
318    f.add_transition_list (string.digits,     'INIT',            BeginBuildNumber, 'BUILDING_NUMBER')
319    f.add_transition_list (string.digits,     'BUILDING_NUMBER', BuildNumber,      'BUILDING_NUMBER')
320    f.add_transition_list (string.whitespace, 'BUILDING_NUMBER', EndBuildNumber,   'INIT')
321    f.add_transition_list ('+-*/',            'INIT',            DoOperator,       'INIT')
322
323    print()
324    print('Enter an RPN Expression.')
325    print('Numbers may be integers. Operators are * / + -')
326    print('Use the = sign to evaluate and print the expression.')
327    print('For example: ')
328    print('    167 3 2 2 * * * 1 - =')
329    inputstr = (input if PY3 else raw_input)('> ')  # analysis:ignore
330    f.process_list(inputstr)
331
332
333if __name__ == '__main__':
334    main()
335