FSM.py 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349
  1. #!/usr/bin/env python
  2. """This module implements a Finite State Machine (FSM). In addition to state
  3. this FSM also maintains a user defined "memory". So this FSM can be used as a
  4. Push-down Automata (PDA) since a PDA is a FSM + memory.
  5. The following describes how the FSM works, but you will probably also need to
  6. see the example function to understand how the FSM is used in practice.
  7. You define an FSM by building tables of transitions. For a given input symbol
  8. the process() method uses these tables to decide what action to call and what
  9. the next state will be. The FSM has a table of transitions that associate:
  10. (input_symbol, current_state) --> (action, next_state)
  11. Where "action" is a function you define. The symbols and states can be any
  12. objects. You use the add_transition() and add_transition_list() methods to add
  13. to the transition table. The FSM also has a table of transitions that
  14. associate:
  15. (current_state) --> (action, next_state)
  16. You use the add_transition_any() method to add to this transition table. The
  17. FSM also has one default transition that is not associated with any specific
  18. input_symbol or state. You use the set_default_transition() method to set the
  19. default transition.
  20. When an action function is called it is passed a reference to the FSM. The
  21. action function may then access attributes of the FSM such as input_symbol,
  22. current_state, or "memory". The "memory" attribute can be any object that you
  23. want to pass along to the action functions. It is not used by the FSM itself.
  24. For parsing you would typically pass a list to be used as a stack.
  25. The processing sequence is as follows. The process() method is given an
  26. input_symbol to process. The FSM will search the table of transitions that
  27. associate:
  28. (input_symbol, current_state) --> (action, next_state)
  29. If the pair (input_symbol, current_state) is found then process() will call the
  30. associated action function and then set the current state to the next_state.
  31. If the FSM cannot find a match for (input_symbol, current_state) it will then
  32. search the table of transitions that associate:
  33. (current_state) --> (action, next_state)
  34. If the current_state is found then the process() method will call the
  35. associated action function and then set the current state to the next_state.
  36. Notice that this table lacks an input_symbol. It lets you define transitions
  37. for a current_state and ANY input_symbol. Hence, it is called the "any" table.
  38. Remember, it is always checked after first searching the table for a specific
  39. (input_symbol, current_state).
  40. For the case where the FSM did not match either of the previous two cases the
  41. FSM will try to use the default transition. If the default transition is
  42. defined then the process() method will call the associated action function and
  43. then set the current state to the next_state. This lets you define a default
  44. transition as a catch-all case. You can think of it as an exception handler.
  45. There can be only one default transition.
  46. Finally, if none of the previous cases are defined for an input_symbol and
  47. current_state then the FSM will raise an exception. This may be desirable, but
  48. you can always prevent this just by defining a default transition.
  49. Noah Spurrier 20020822
  50. PEXPECT LICENSE
  51. This license is approved by the OSI and FSF as GPL-compatible.
  52. http://opensource.org/licenses/isc-license.txt
  53. Copyright (c) 2012, Noah Spurrier <noah@noah.org>
  54. PERMISSION TO USE, COPY, MODIFY, AND/OR DISTRIBUTE THIS SOFTWARE FOR ANY
  55. PURPOSE WITH OR WITHOUT FEE IS HEREBY GRANTED, PROVIDED THAT THE ABOVE
  56. COPYRIGHT NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES.
  57. THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  58. WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  59. MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  60. ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  61. WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  62. ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  63. OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  64. """
  65. class ExceptionFSM(Exception):
  66. """This is the FSM Exception class."""
  67. def __init__(self, value):
  68. self.value = value
  69. def __str__(self):
  70. return `self.value`
  71. class FSM:
  72. """This is a Finite State Machine (FSM).
  73. """
  74. def __init__(self, initial_state, memory=None):
  75. """This creates the FSM. You set the initial state here. The "memory"
  76. attribute is any object that you want to pass along to the action
  77. functions. It is not used by the FSM. For parsing you would typically
  78. pass a list to be used as a stack. """
  79. # Map (input_symbol, current_state) --> (action, next_state).
  80. self.state_transitions = {}
  81. # Map (current_state) --> (action, next_state).
  82. self.state_transitions_any = {}
  83. self.default_transition = None
  84. self.input_symbol = None
  85. self.initial_state = initial_state
  86. self.current_state = self.initial_state
  87. self.next_state = None
  88. self.action = None
  89. self.memory = memory
  90. def reset (self):
  91. """This sets the current_state to the initial_state and sets
  92. input_symbol to None. The initial state was set by the constructor
  93. __init__(). """
  94. self.current_state = self.initial_state
  95. self.input_symbol = None
  96. def add_transition (self, input_symbol, state, action=None, next_state=None):
  97. """This adds a transition that associates:
  98. (input_symbol, current_state) --> (action, next_state)
  99. The action may be set to None in which case the process() method will
  100. ignore the action and only set the next_state. The next_state may be
  101. set to None in which case the current state will be unchanged.
  102. You can also set transitions for a list of symbols by using
  103. add_transition_list(). """
  104. if next_state is None:
  105. next_state = state
  106. self.state_transitions[(input_symbol, state)] = (action, next_state)
  107. def add_transition_list (self, list_input_symbols, state, action=None, next_state=None):
  108. """This adds the same transition for a list of input symbols.
  109. You can pass a list or a string. Note that it is handy to use
  110. string.digits, string.whitespace, string.letters, etc. to add
  111. transitions that match character classes.
  112. The action may be set to None in which case the process() method will
  113. ignore the action and only set the next_state. The next_state may be
  114. set to None in which case the current state will be unchanged. """
  115. if next_state is None:
  116. next_state = state
  117. for input_symbol in list_input_symbols:
  118. self.add_transition (input_symbol, state, action, next_state)
  119. def add_transition_any (self, state, action=None, next_state=None):
  120. """This adds a transition that associates:
  121. (current_state) --> (action, next_state)
  122. That is, any input symbol will match the current state.
  123. The process() method checks the "any" state associations after it first
  124. checks for an exact match of (input_symbol, current_state).
  125. The action may be set to None in which case the process() method will
  126. ignore the action and only set the next_state. The next_state may be
  127. set to None in which case the current state will be unchanged. """
  128. if next_state is None:
  129. next_state = state
  130. self.state_transitions_any [state] = (action, next_state)
  131. def set_default_transition (self, action, next_state):
  132. """This sets the default transition. This defines an action and
  133. next_state if the FSM cannot find the input symbol and the current
  134. state in the transition list and if the FSM cannot find the
  135. current_state in the transition_any list. This is useful as a final
  136. fall-through state for catching errors and undefined states.
  137. The default transition can be removed by setting the attribute
  138. default_transition to None. """
  139. self.default_transition = (action, next_state)
  140. def get_transition (self, input_symbol, state):
  141. """This returns (action, next state) given an input_symbol and state.
  142. This does not modify the FSM state, so calling this method has no side
  143. effects. Normally you do not call this method directly. It is called by
  144. process().
  145. The sequence of steps to check for a defined transition goes from the
  146. most specific to the least specific.
  147. 1. Check state_transitions[] that match exactly the tuple,
  148. (input_symbol, state)
  149. 2. Check state_transitions_any[] that match (state)
  150. In other words, match a specific state and ANY input_symbol.
  151. 3. Check if the default_transition is defined.
  152. This catches any input_symbol and any state.
  153. This is a handler for errors, undefined states, or defaults.
  154. 4. No transition was defined. If we get here then raise an exception.
  155. """
  156. if self.state_transitions.has_key((input_symbol, state)):
  157. return self.state_transitions[(input_symbol, state)]
  158. elif self.state_transitions_any.has_key (state):
  159. return self.state_transitions_any[state]
  160. elif self.default_transition is not None:
  161. return self.default_transition
  162. else:
  163. raise ExceptionFSM ('Transition is undefined: (%s, %s).' %
  164. (str(input_symbol), str(state)) )
  165. def process (self, input_symbol):
  166. """This is the main method that you call to process input. This may
  167. cause the FSM to change state and call an action. This method calls
  168. get_transition() to find the action and next_state associated with the
  169. input_symbol and current_state. If the action is None then the action
  170. is not called and only the current state is changed. This method
  171. processes one complete input symbol. You can process a list of symbols
  172. (or a string) by calling process_list(). """
  173. self.input_symbol = input_symbol
  174. (self.action, self.next_state) = self.get_transition (self.input_symbol, self.current_state)
  175. if self.action is not None:
  176. self.action (self)
  177. self.current_state = self.next_state
  178. self.next_state = None
  179. def process_list (self, input_symbols):
  180. """This takes a list and sends each element to process(). The list may
  181. be a string or any iterable object. """
  182. for s in input_symbols:
  183. self.process (s)
  184. ##############################################################################
  185. # The following is an example that demonstrates the use of the FSM class to
  186. # process an RPN expression. Run this module from the command line. You will
  187. # get a prompt > for input. Enter an RPN Expression. Numbers may be integers.
  188. # Operators are * / + - Use the = sign to evaluate and print the expression.
  189. # For example:
  190. #
  191. # 167 3 2 2 * * * 1 - =
  192. #
  193. # will print:
  194. #
  195. # 2003
  196. ##############################################################################
  197. import sys, os, traceback, optparse, time, string
  198. #
  199. # These define the actions.
  200. # Note that "memory" is a list being used as a stack.
  201. #
  202. def BeginBuildNumber (fsm):
  203. fsm.memory.append (fsm.input_symbol)
  204. def BuildNumber (fsm):
  205. s = fsm.memory.pop ()
  206. s = s + fsm.input_symbol
  207. fsm.memory.append (s)
  208. def EndBuildNumber (fsm):
  209. s = fsm.memory.pop ()
  210. fsm.memory.append (int(s))
  211. def DoOperator (fsm):
  212. ar = fsm.memory.pop()
  213. al = fsm.memory.pop()
  214. if fsm.input_symbol == '+':
  215. fsm.memory.append (al + ar)
  216. elif fsm.input_symbol == '-':
  217. fsm.memory.append (al - ar)
  218. elif fsm.input_symbol == '*':
  219. fsm.memory.append (al * ar)
  220. elif fsm.input_symbol == '/':
  221. fsm.memory.append (al / ar)
  222. def DoEqual (fsm):
  223. print str(fsm.memory.pop())
  224. def Error (fsm):
  225. print 'That does not compute.'
  226. print str(fsm.input_symbol)
  227. def main():
  228. """This is where the example starts and the FSM state transitions are
  229. defined. Note that states are strings (such as 'INIT'). This is not
  230. necessary, but it makes the example easier to read. """
  231. f = FSM ('INIT', []) # "memory" will be used as a stack.
  232. f.set_default_transition (Error, 'INIT')
  233. f.add_transition_any ('INIT', None, 'INIT')
  234. f.add_transition ('=', 'INIT', DoEqual, 'INIT')
  235. f.add_transition_list (string.digits, 'INIT', BeginBuildNumber, 'BUILDING_NUMBER')
  236. f.add_transition_list (string.digits, 'BUILDING_NUMBER', BuildNumber, 'BUILDING_NUMBER')
  237. f.add_transition_list (string.whitespace, 'BUILDING_NUMBER', EndBuildNumber, 'INIT')
  238. f.add_transition_list ('+-*/', 'INIT', DoOperator, 'INIT')
  239. print
  240. print 'Enter an RPN Expression.'
  241. print 'Numbers may be integers. Operators are * / + -'
  242. print 'Use the = sign to evaluate and print the expression.'
  243. print 'For example: '
  244. print ' 167 3 2 2 * * * 1 - ='
  245. inputstr = raw_input ('> ')
  246. f.process_list(inputstr)
  247. if __name__ == '__main__':
  248. try:
  249. start_time = time.time()
  250. parser = optparse.OptionParser(formatter=optparse.TitledHelpFormatter(), usage=globals()['__doc__'], version='$Id: FSM.py 533 2012-10-20 02:19:33Z noah $')
  251. parser.add_option ('-v', '--verbose', action='store_true', default=False, help='verbose output')
  252. (options, args) = parser.parse_args()
  253. if options.verbose: print time.asctime()
  254. main()
  255. if options.verbose: print time.asctime()
  256. if options.verbose: print 'TOTAL TIME IN MINUTES:',
  257. if options.verbose: print (time.time() - start_time) / 60.0
  258. sys.exit(0)
  259. except KeyboardInterrupt, e: # Ctrl-C
  260. raise e
  261. except SystemExit, e: # sys.exit()
  262. raise e
  263. except Exception, e:
  264. print 'ERROR, UNEXPECTED EXCEPTION'
  265. print str(e)
  266. traceback.print_exc()
  267. os._exit(1)