Package ZenRRD :: Module rpn
[hide private]
[frames] | no frames]

Source Code for Module ZenRRD.rpn

  1  ########################################################################### 
  2  # 
  3  # This program is part of Zenoss Core, an open source monitoring platform. 
  4  # Copyright (C) 2007, Zenoss Inc. 
  5  # 
  6  # This program is free software; you can redistribute it and/or modify it 
  7  # under the terms of the GNU General Public License version 2 as published by 
  8  # the Free Software Foundation. 
  9  # 
 10  # For complete information please visit: http://www.zenoss.com/oss/ 
 11  # 
 12  ########################################################################### 
 13  #!/usr/bin/env python 
 14  '''This module implements a Finite State Machine (FSM). 
 15  In addition to state this FSM also maintains a user defined "something". 
 16  This "something" is effectively memory, so this FSM could be considered 
 17  a Push-down Automata (PDA) since a PDA is a FSM + memory. 
 18   
 19  The following describes how the FSM works, but you will probably also need 
 20  to see the example function to understand how the FSM is used in practice. 
 21   
 22  You define an FSM by building tables of transitions. 
 23  For a given input symbol the process() method uses these tables  
 24  to decide what action to call and what the next state will be.  
 25  The FSM has a table of transitions that associate: 
 26          (input_symbol, current_state) --> (action, next_state) 
 27  where "action" is a function you define. The symbols and states  
 28  can be any objects. You use the add_transition() and add_transition_list()  
 29  methods to add to the transition table. The FSM also has a table 
 30  of transitions that associate: 
 31          (current_state) --> (action, next_state) 
 32  You use the add_transition_any() method to add to this transition table. 
 33  The FSM also has one default transition that is not associated 
 34  with any specific input_symbol or state. You use the  
 35  set_default_transition() method to set the default transition. 
 36   
 37  When an action function is called it is passed a reference to the FSM. 
 38  The action function may then access attributes of the FSM such as 
 39  input_symbol, current_state, or "something". The "something" attribute  
 40  can be any object that you want to pass along to the action functions. 
 41  It is not used by the FSM. For parsing you would typically pass a list  
 42  to be used as a stack. 
 43   
 44  The processing sequence is as follows. 
 45  The process() method is given an input_symbol to process. 
 46  The FSM will search the table of transitions that associate: 
 47          (input_symbol, current_state) --> (action, next_state)  
 48  If the pair (input_symbol, current_state) is found then  
 49  process() will call the associated action function and then set the  
 50  current state to the next_state. 
 51   
 52  If the FSM cannot find a match for (input_symbol, current_state) 
 53  it will then search the table of transitions that associate: 
 54          (current_state) --> (action, next_state) 
 55  If the current_state is found then the process() method will call  
 56  the associated action function and then set the current state to  
 57  the next_state. Notice that this table lacks an input_symbol.  
 58  It lets you define transitions for a current_state and ANY input_symbol. 
 59  Hence, it is called the "any" table. Remember, it is always checked 
 60  after first searching the table for a specific (input_symbol, current_state). 
 61   
 62  For the case where the FSM did not match either of the previous two cases 
 63  the FSM will try to use the default transition. If the default transition 
 64  is defined then the process() method will call the associated action function 
 65  and then set the current state to the next_state. This lets you define  
 66  a default transition as a catch-all case. You can think of it as an  
 67  exception handler. There can be only one default transition. 
 68   
 69  Finally, if none of the previous cases are defined for an input_symbol  
 70  and current_state then the FSM will raise an exception.  
 71  This may be desirable, but you can always prevent this just by  
 72  defining a default transition. 
 73   
 74  Noah Spurrier 20020822 
 75  ''' 
 76   
77 -class ExceptionFSM(Exception):
78 '''This is the FSM Exception class.'''
79 - def __init__(self, value):
80 self.value = value
81 - def __str__(self):
82 return `self.value`
83
84 -class FSM:
85 '''This is a Finite State Machine (FSM). 86 ''' 87
88 - def __init__(self, initial_state, something):
89 '''This creates the FSM. 90 You set the initial state here. The "something" attribute is any 91 object that you want to pass along to the action functions. 92 It is not used by the FSM. For parsing you would typically pass 93 a list to be used as a stack. 94 ''' 95 # Map (input_symbol, current_state) --> (action, next_state). 96 self.state_transitions = {} 97 # Map (current_state) --> (action, next_state). 98 self.state_transitions_any = {} 99 self.default_transition = None 100 101 self.input_symbol = None 102 self.initial_state = initial_state 103 self.current_state = self.initial_state 104 self.something = something
105
106 - def reset (self):
107 '''This sets the current_state to the initial_state and 108 sets input_symbol to None. 109 The initial state was set by the constructor __init__(). 110 ''' 111 self.current_state = self.initial_state 112 self.input_symbol = None
113
114 - def add_transition (self, input_symbol, state, action, next_state):
115 '''This adds a transition that associates 116 (input_symbol, current_state) --> (action, next_state) 117 The action may be set to None in which case the process() method 118 will ignore the action and only set the next_state. 119 120 You can also set transitions for a list of symbols by using 121 add_transition_list(). 122 ''' 123 self.state_transitions[(input_symbol, state)] = (action, next_state)
124
125 - def add_transition_list (self, list_input_symbols, state, action, next_state):
126 '''This adds the same transition for lots of different input symbols. 127 You can pass a list or a string. Note that it is handy to use 128 string.digits, string.whitespace, string.letters, etc. to add 129 transitions that match character classes. 130 ''' 131 for input_symbol in list_input_symbols: 132 self.add_transition (input_symbol, state, action, next_state)
133
134 - def add_transition_any (self, state, action, next_state):
135 '''This adds a transition that associates 136 (current_state) --> (action, next_state) 137 The process() method checks these associations if it cannot 138 first find a match of an (input_symbol, current_state). 139 ''' 140 self.state_transitions_any [state] = (action, next_state)
141
142 - def set_default_transition (self, action, next_state):
143 '''This sets the default transition. 144 This defines an action and next_state if the FSM cannot find the 145 input symbol and the current state in the transition list and 146 if the FSM cannot find the current_state in the transition_any list. 147 This is useful for catching errors and undefined states. 148 149 The default transition can be removed by setting the attribute 150 default_transition to None. 151 ''' 152 self.default_transition = (action, next_state)
153
154 - def get_transition (self, input_symbol, state):
155 '''This returns (action, next state) given an input_symbol and state. 156 This leaves the FSM unchanged. This does not update the current state 157 nor does it trigger the output action. Normally you do not call 158 this method. It is called by process(). 159 160 The sequence of steps to check for a defined transition goes from 161 the most specific to the least specific. 162 1. Check state_transitions[] that match (input_symbol, state) 163 2. Check state_transitions_any[] that match (state) 164 In other words, match a specific state and ANY input_symbol. 165 3. Check if the default_transition is defined. 166 This catches any input_symbol and any state. 167 This is a handler for errors, undefined states, or defaults. 168 4. No transition was defined. If we get here then raise an exception. 169 ''' 170 if self.state_transitions.has_key((input_symbol, self.current_state)): 171 return self.state_transitions[(input_symbol, self.current_state)] 172 elif self.state_transitions_any.has_key (self.current_state): 173 return self.state_transitions_any[self.current_state] 174 elif self.default_transition != None: 175 return self.default_transition 176 else: 177 raise ExceptionFSM ('Transition is undefined: (%s, %s).' % 178 (str(input_symbol), str(self.current_state)) )
179
180 - def process (self, input_symbol):
181 '''This is the main method that you call to process input. 182 This may cause the FSM to change state and call an action. 183 This method calls get_transition() to find the action and next_state 184 associated with the input_symbol and current_state. 185 If the action is None then the action is not called and 186 only the current state is changed. 187 This method processes one input symbol. You can process a list of 188 symbols (or a string) by calling process_list(). 189 ''' 190 self.input_symbol = input_symbol 191 (action, next_state) = self.get_transition (self.input_symbol, self.current_state) 192 if action != None: 193 action (self) 194 self.current_state = next_state
195
196 - def process_list (self, s):
197 '''This takes a list and sends each element to process(). 198 The list may be a string. 199 ''' 200 for c in s: 201 self.process (c)
202 203 ########################################################################## 204 # The following example demonstrates the use of the FSM class in 205 # processing RPN expressions. Run this module from the command line. 206 # You will get a prompt > for input. 207 # Enter an RPN Expression. 208 # Numbers may be integers. Operators are * / + - 209 # Use the = sign to evaluate and print the expression. 210 # For example: 211 # 167 3 2 2 * * * 1 - = 212 # will print: 213 # 2003 214 ########################################################################## 215 216 import string 217 218 # 219 # These define the actions. 220 # Note that "something" is a list being used as a stack. 221 #
222 -def BeginBuildNumber (fsm):
223 fsm.something.append (fsm.input_symbol)
224 -def BuildNumber (fsm):
225 s = fsm.something.pop () 226 s = s + fsm.input_symbol 227 fsm.something.append (s)
228 -def EndBuildNumber (fsm):
229 s = fsm.something.pop () 230 fsm.something.append (int(s))
231 -def DoOperator (fsm):
232 ar = fsm.something.pop() 233 al = fsm.something.pop() 234 if fsm.input_symbol == '+': 235 fsm.something.append (al + ar) 236 elif fsm.input_symbol == '-': 237 fsm.something.append (al - ar) 238 elif fsm.input_symbol == '*': 239 fsm.something.append (al * ar) 240 elif fsm.input_symbol == '/': 241 fsm.something.append (al / ar)
242 -def DoEqual (fsm):
243 print str(fsm.something.pop())
244 -def Error (fsm):
245 print 'That does not compute.' 246 print str(fsm.input_symbol)
247 248 # 249 # This is where the example starts and the FSM state transitions are defined. 250 # Note that states (such as 'INIT') are strings. This is not necessary, but 251 # it makes the example easier to read. 252 #
253 -def example ():
254 f = FSM ('INIT', []) # "something" will be used as a stack. 255 f.set_default_transition (Error, 'INIT') 256 f.add_transition_any ('INIT', None, 'INIT') 257 f.add_transition ('=', 'INIT', DoEqual, 'INIT') 258 f.add_transition_list (string.digits, 'INIT', BeginBuildNumber, 'BUILDING_NUMBER') 259 f.add_transition_list (string.digits, 'BUILDING_NUMBER', BuildNumber, 'BUILDING_NUMBER') 260 f.add_transition_list (string.whitespace, 'BUILDING_NUMBER', EndBuildNumber, 'INIT') 261 f.add_transition_list ('+-*/', 'INIT', DoOperator, 'INIT') 262 263 print 264 print 'Enter an RPN Expression.' 265 print 'Numbers may be integers. Operators are * / + -' 266 print 'Use the = sign to evaluate and print the expression.' 267 print 'For example: ' 268 print ' 167 3 2 2 * * * 1 - =' 269 inputs = raw_input ('>') 270 for s in inputs: 271 f.process (s)
272 273 if __name__ == '__main__': 274 example () 275