delphi programming forums mysql charset mget recursive synonimos
free ventrilo servers hosting cs javascript delay python find in list
Back Forum New

Rank: 1
1# Jump to »
Schol-R-LEAPost at 2010-5-29 05:02 | Show This Author's Posts Only
abstract:

        is a final state or not, the recognized result (if any) and the
        amount of pushback (if any).
        next() takes a single character input: it will reject any string not
        of size one, returning the number of extraneous characters in
        'pushback'. The method first tries to match the character to a
        state through a simple lookup, on the assumption that most transitions
        will be based on a single possible input. If this does not succeed,
        it will try to match the characters against keys with multiple
        characters; this allows a given state transition to give a set of
        possible matches (e.g., all alphanumeric characters) rather than
        requiring a separate key for each character. If this does not succeed,
        it then checkes to see if there is a default state set. If none of these
        find a match, the method returns an error state.
        If a successor is found, the method then checks to see if the successor
        is either ACCEPT or ERROR. If it is ACCEPT, it returns the ACCEPT
        constant, a true final value, the type of the recongized token, and
        a pushback amount. If it is ERROR, it returns the ERROR constant, a
        true final value, ERROR as the token type, and the pushback amount.
        Otherwise, it returns the successor and false/None/0 for the remainder.
       "
""
if
len
(
input
)
!=
1
:
# check validity of the input
return
self
.
ERROR
,
False
,
self
.
ERROR
,
len
(
input
)
-
1
# try to match the input to a transition
        successor =
None
if
input
in
self
.__transitions:
# check single-character key match
            successor =
self
.__transitions.
get
(
input
)
else
:
for
s
in
self
.__transitions:
# check multi-char keys
if
input
in
s
and
s !=
self
.
OTHER
:
                    successor =
self
.__transitions.
get
(
s
)
break
if
successor
is
None
:
# use default transition, if any
                successor =
self
.__transitions.
get
(
self
.
OTHER
)
if
successor
is
None
:
return
self
.
ERROR
,
False
,
self
.
ERROR
,
0
# successor found, test if it is either an ACCEPT or ERROR state.
if
successor ==
self
.
ACCEPT
:
# ACCEPT
return
self
.
ACCEPT
,
True
,
self
.__toktype,
self
.__pushback
elif
successor ==
self
.
ERROR
:
# ERROR
return
self
.
ERROR
,
True
,
self
.
ERROR
,
self
.__pushback
else
:
# not a final state, return the successor state
return
successor,
False
,
None
,
0
def
__str__
(
self
)
:
""
" Basic string representation of a State."
""
return
str
(
self
.__transitions
)
class
StateMachine
(
object
)
:
""
" Generalized Finite State Automata class.
    Instance Variables:
        states: a lookup table of state numbers and states
        current_state: the current state of the FSM
        locked: flag whether all of the states are set.
    A FSM consists of a set of States, the current State, and a flag
    indicating if all States have been added to the set of states. Until
    the FSM is locked, new states may be added. The State machine begins
    in the Start state, and accepts input until it either accepts or rejects
    the input string. When it reaches one of these final states, it returns
    the type of the recongized string and resets itself to the Start state.
   "
""
def
__init__
(
self
, start_state
)
:
""
" Constructor - create a FSM object.
        Adds the initial (Start) state, sets the current state to Start,
        and clears the locked flag.
       "
""
self
.__states =
{
State.
START
: start_state
}
self
.__locked =
False
self
.__current_state =
self
.__states
[
State.
START
]
    @takes
(
"StateMachine"
,
int
, State
)
def
add
(
self
, key, state
)
:
""
" Add a new state to the state table.
        The add() method takes a state identifier key and a new State
        object. If the table is not locked, and there is no State
        by that number already, it adds state to the state table
        and returns true. Otherwise, it returns false.
       "
""
if
self
.__locked:
return
False
# do not allow any states to be added
elif
key
in
self
.__states:
# state with that ID already in table
return
False
else
:
self
.__states
[
key
]
= state
return
True
def
lock
(
self
)
:
""
" Locks state table so no new states can be added."
""
        lock =
True
    @returns
(
tuple
)
def
transition
(
self
,
input
)
:
""
" Perform a state transition, and if it is a final
        state, return success or failure and the recognized token type.
       "
""
# get the successor state of the current state, if any
        successor, final,
token
, pb =
self
.__current_state.
next
(
input
)
# see if the state has finalized, reset the current state and
# determine if it accepted or rejected the input string
if
final:
self
.__current_state =
self
.__states
[
State.
START
]
if
successor == State.
ACCEPT
:
# string accepted
return
True
,
token
, pb
else
:
# string rejected
return
True
, State.
ERROR
, pb
# if the state has not finalized, see if it is a 'non-final' error
# state and return an error value if it is. This will only occur if
# the input is not valid.
elif
successor == State.
ERROR
:
self
.__current_state =
self
.__states
[
State.
START
]
return
True
, State.
ERROR
, pb
# if the state is not final and not an error, advance to the next state
else
:
self
.__current_state =
self
.__states
[
successor
]
return
False
,
0
,
0
def
__str__
(
self
)
:
""
"Return a simple string representation of the FSM for debugging. "
""
return
str
(
self
.__states
)
################################
if
__name__ ==
"__main__"
:
pass

I have attached a copy of the actual project it had been part of for anyone who wants a reference point in how I intended it to be used.
Any and all (constructive) comments and critiques would be helpful. At the moment, I have tentatively given the projec the name 'AutonomousCollective', but any other suggestions would be appreciated (though I'd prefer something with either a MP or H2G2 theme - the latter to match th name of the original project). TIA.


Mods: I wasn't certain if it should be in the language-specific forum or one of the discussion forums. If this would be better off in another message board, feel free to move it.
Earlier this year, I took a course an undergraduate course in compiler design, and opted to use Python as my implementation language - the class was to focus on the design aspects, not performance, so I concluded that I would rather use a language which wouldn't fight back so much as Java or C++ would when it came to string handling. While this may have been a mistake in the end - the time I saved not writing a lot of string handling code was lost again by some rather overly ambitious design approaches - in the process of it, I implemented a more or less general string-driven finite automata library.
I am now wondering if this would be something which would be of use to others, so I am considering creating a project on SourceForge for it. I would like to know if others think this would be worth the trouble to share or not, and if so, what changes or refinements should be made to make it a viable open-source library. I am concerned that it is too small and basic to be worth making a library out of. Conversely, it may be too heavyweight to be practical, since FSMs are usually implemented in much simpler manners than the one I used. Also, the design is not especially Pythonic, being rather clumsy and Java-esque in it's initialization specifically. Finally, it may not be suited to a lot of things people might want an FSM for - while the design is
almost
general, it is still designed primarily for tokenizing a stream of characters, which may limit its applicability.
The library consists of two classes, a
State
class and a
StateMachine
class. A
State
object consists of a key, a table of input/state transition pairs, a flag whether the state can be a final state, a type for the type of token it returns (if any), and a pushback number (most likely, I will replace these with some more general sort of completion value, though just how I haven't decided). The class has four class constants: three representing the common transition states (accept, error, and other), one serving a common start state key (used by the
StateMachine
class), and one used to indicate a default transition state for input not otherwise specified (if none is given, it assumes an error state). In addition to a constructor and a string-representation method, t has one instance method,
next()
, which takes an input string and returns a tuple with state to which it would transition, the final-state flag, a token,  (if it is an accept state), and a pushback number (if it is at a final state that ends one or more characters back).
The
StateMachine
object consists of a table of state keys (right now, it only uses numbers, but I think that allowing named states may prove valuable later) and states, State object representing the current state of the FSM, and a flag indicating if the table is 'locked' or not (that is, the table has been completely populated). The
StateMachine
is constructed with a required start state, and new states are added to the table using the
add()
method, and new states can be added until
lock()
is called. There is a
locked()
method to test whtehr it is locked or not. Once the table is locked, the
transition()
method can be used to step through the input stream, taking one character at a time as input. It returns the accept flag, the token, and the pushback number returned by the call to
current_state.next()
; on a error state, it returns
State.ERROR
for the token.
Here is the code as it currently exists:
Python Code:
[url=#top]
[/url]Original
                - Python Code
from typecheck import *

__title__ = 'AutonomousCollective'
__author__ = 'Joseph Osako'
__version__ = '0.1'
__date__ = '2008:08:21'

__credits__ += """Uses Dimitri Dvoinikov's typecheck decorator library"""
__credits__ += """<http://www.targeted.org/python/recipes/typecheck.py>"""
__credits__ += """for method typechecking.\n"""

class State (object):
    """ Class representing the states of a Finite State Automata.
   
    Instance Variables:
        transitions: dictionary (string:integer)
        final: boolean
        toktype: Object
        pushback: integer
   
    State object consist of four properties: an a-list of accepted input
    strings and numeric identifiers for the succeeding states, a flag
    indicating if the state can lead to a final (accept or reject) state,
    the condition returned when accepted, and a number of characters which
    the recognizer should push back by. A State can take an input character
    and return an identifying number for the corresponding successor State.
   
    The State class has five class constants. Four of these represent common
    states for all state machines (START, ACCEPT, ERROR, and DEFAULT). The
    last represents a default input.
    """
    START = 0
    ACCEPT = -1
    ERROR = -2
    DEFAULT = -3
    OTHER = "__OTHER__"

    def __init__(self, transitions, final = False, \
                toktype = ERROR, pushback = 0):
        """ Constructor - create a State object.
        
       @params:
        transitions - lookup table of inputs and states
        final - final/non-final state flag (default false)
        toktype - type of token recognized on accept (default None)
        pushback - number of chars to push back after accept (default 0)
        
        Initializes the instance variables for the new object.
       """
        self.__final, self.__toktype = final, toktype
        self.__transitions = transitions
        self.__pushback = pushback
   
    @takes("State", str)
    @returns(tuple)
    def next(self, input):
        """ Return the successive state based on the input character.
        
         The next() method is the primary behavior of the State object.
        It returns a tuple containing the successor state, whether it
        is a final state or not, the recognized result (if any) and the
        amount of pushback (if any).
        
        next() takes a single character input: it will reject any string not
        of size one, returning the number of extraneous characters in
        'pushback'. The method first tries to match the character to a
        state through a simple lookup, on the assumption that most transitions
        will be based on a single possible input. If this does not succeed,
        it will try to match the characters against keys with multiple
        characters; this allows a given state transition to give a set of
        possible matches (e.g., all alphanumeric characters) rather than
        requiring a separate key for each character. If this does not succeed,
        it then checkes to see if there is a default state set. If none of these
        find a match, the method returns an error state.
        
        If a successor is found, the method then checks to see if the successor
        is either ACCEPT or ERROR. If it is ACCEPT, it returns the ACCEPT
        constant, a true final value, the type of the recongized token, and
        a pushback amount. If it is ERROR, it returns the ERROR constant, a
        true final value, ERROR as the token type, and the pushback amount.
        Otherwise, it returns the successor and false/None/0 for the remainder.
       """
        if len(input) != 1:         # check validity of the input
            return self.ERROR, False, self.ERROR, len(input) - 1
        
        # try to match the input to a transition
        successor = None
        if input in self.__transitions:     # check single-character key match
            successor = self.__transitions.get(input)
        else:
            for s in self.__transitions:    # check multi-char keys
                if input in s and s != self.OTHER:
                    successor = self.__transitions.get(s)
                    break
            if successor is None:           # use default transition, if any
                successor = self.__transitions.get(self.OTHER)
                if successor is None:
                    return self.ERROR, False, self.ERROR, 0
               
        # successor found, test if it is either an ACCEPT or ERROR state.
        if successor == self.ACCEPT:    # ACCEPT
            return self.ACCEPT, True, self.__toktype, self.__pushback
        elif successor == self.ERROR:   # ERROR
            return self.ERROR, True, self.ERROR, self.__pushback
        else:
            # not a final state, return the successor state
            return successor, False, None, 0
        
        def __str__(self):
            """ Basic string representation of a State."""
            return str(self.__transitions)
            


class StateMachine(object):
    """ Generalized Finite State Automata class.
   
    Instance Variables:
        states: a lookup table of state numbers and states
        current_state: the current state of the FSM
        locked: flag whether all of the states are set.
   
    A FSM consists of a set of States, the current State, and a flag
    indicating if all States have been added to the set of states. Until
    the FSM is locked, new states may be added. The State machine begins
    in the Start state, and accepts input until it either accepts or rejects
    the input string. When it reaches one of these final states, it returns
    the type of the recongized string and resets itself to the Start state.
   """
    def __init__(self, start_state):
        """ Constructor - create a FSM object.
        
        Adds the initial (Start) state, sets the current state to Start,
        and clears the locked flag.
       """
        self.__states = {State.START: start_state}
        self.__locked = False
        self.__current_state = self.__states[State.START]
   
   
    @takes("StateMachine", int, State)
    def add(self, key, state):
        """ Add a new state to the state table.
        
        The add() method takes a state identifier key and a new State
        object. If the table is not locked, and there is no State
        by that number already, it adds state to the state table
        and returns true. Otherwise, it returns false.
       """
        if self.__locked:
            return False   # do not allow any states to be added
        elif key in self.__states:  # state with that ID already in table
            return False
        else:
            self.__states[key] = state
            return True
   
    def lock(self):
        """ Locks state table so no new states can be added."""
        lock = True
        
    @returns(tuple)
    def transition(self, input):
        """ Perform a state transition, and if it is a final
        state, return success or failure and the recognized token type.
       """
        # get the successor state of the current state, if any
        successor, final, token, pb = self.__current_state.next(input)
        
        # see if the state has finalized, reset the current state and
        # determine if it accepted or rejected the input string
        if final:
            self.__current_state = self.__states[State.START]
            
            if successor == State.ACCEPT:   # string accepted
                return True, token, pb
            else:                           # string rejected
                return True, State.ERROR, pb
        # if the state has not finalized, see if it is a 'non-final' error
        # state and return an error value if it is. This will only occur if
        # the input is not valid.
        elif successor == State.ERROR:
            self.__current_state = self.__states[State.START]
            return True, State.ERROR, pb
        # if the state is not final and not an error, advance to the next state
        else:
            self.__current_state = self.__states[successor]
            return False, 0, 0
   
    def __str__(self):
        """Return a simple string representation of the FSM for debugging. """
        return str(self.__states)
   
################################
if __name__ == "__main__":
    pass
  1. from
  2. typecheck
  3. import
  4. *
  5. __title__ =
  6. 'AutonomousCollective'
  7. __author__ =
  8. 'Joseph Osako'
  9. __version__ =
  10. '0.1'
  11. __date__ =
  12. '2008:08:21'
  13. __credits__ +=
  14. ""
  15. "Uses Dimitri Dvoinikov's typecheck decorator library"
  16. ""
  17. __credits__ +=
  18. ""
  19. "<http://www.targeted.org/python/recipes/typecheck.py>"
  20. ""
  21. __credits__ +=
  22. ""
  23. "for method typechecking.
  24. \n
  25. "
  26. ""
  27. class
  28. State
  29. &#40;
  30. object
  31. &#41;
  32. :
  33. ""
  34. " Class representing the states of a Finite State Automata.
  35.     Instance Variables:
  36.         transitions: dictionary (string:integer)
  37.         final: boolean
  38.         toktype: Object
  39.         pushback: integer
  40.     State object consist of four properties: an a-list of accepted input
  41.     strings and numeric identifiers for the succeeding states, a flag
  42.     indicating if the state can lead to a final (accept or reject) state,
  43.     the condition returned when accepted, and a number of characters which
  44.     the recognizer should push back by. A State can take an input character
  45.     and return an identifying number for the corresponding successor State.
  46.     The State class has five class constants. Four of these represent common
  47.     states for all state machines (START, ACCEPT, ERROR, and DEFAULT). The
  48.     last represents a default input.
  49.     "
  50. ""
  51.     START =
  52. 0
  53.     ACCEPT = -
  54. 1
  55.     ERROR = -
  56. 2
  57.     DEFAULT = -
  58. 3
  59.     OTHER =
  60. "__OTHER__"
  61. def
  62. __init__
  63. &#40;
  64. self
  65. , transitions, final =
  66. False
  67. , \
  68.                 toktype = ERROR, pushback =
  69. 0
  70. &#41;
  71. :
  72. ""
  73. " Constructor - create a State object.
  74.        @params:
  75.         transitions - lookup table of inputs and states
  76.         final - final/non-final state flag (default false)
  77.         toktype - type of token recognized on accept (default None)
  78.         pushback - number of chars to push back after accept (default 0)
  79.         Initializes the instance variables for the new object.
  80.        "
  81. ""
  82. self
  83. .__final,
  84. self
  85. .__toktype = final, toktype
  86. self
  87. .__transitions = transitions
  88. self
  89. .__pushback = pushback
  90.     @takes
  91. &#40;
  92. "State"
  93. ,
  94. str
  95. &#41;
  96.     @returns
  97. &#40;
  98. tuple
  99. &#41;
  100. def
  101. next
  102. &#40;
  103. self
  104. ,
  105. input
  106. &#41;
  107. :
  108. ""
  109. " Return the successive state based on the input character.
  110.          The next() method is the primary behavior of the State object.
  111.         It returns a tuple containing the successor state, whether it
  112.         is a final state or not, the recognized result (if any) and the
  113.         amount of pushback (if any).
  114.         next() takes a single character input: it will reject any string not
  115.         of size one, returning the number of extraneous characters in
  116.         'pushback'. The method first tries to match the character to a
  117.         state through a simple lookup, on the assumption that most transitions
  118.         will be based on a single possible input. If this does not succeed,
  119.         it will try to match the characters against keys with multiple
  120.         characters; this allows a given state transition to give a set of
  121.         possible matches (e.g., all alphanumeric characters) rather than
  122.         requiring a separate key for each character. If this does not succeed,
  123.         it then checkes to see if there is a default state set. If none of these
  124.         find a match, the method returns an error state.
  125.         If a successor is found, the method then checks to see if the successor
  126.         is either ACCEPT or ERROR. If it is ACCEPT, it returns the ACCEPT
  127.         constant, a true final value, the type of the recongized token, and
  128.         a pushback amount. If it is ERROR, it returns the ERROR constant, a
  129.         true final value, ERROR as the token type, and the pushback amount.
  130.         Otherwise, it returns the successor and false/None/0 for the remainder.
  131.        "
  132. ""
  133. if
  134. len
  135. &#40;
  136. input
  137. &#41;
  138. !=
  139. 1
  140. :
  141. # check validity of the input
  142. return
  143. self
  144. .
  145. ERROR
  146. ,
  147. False
  148. ,
  149. self
  150. .
  151. ERROR
  152. ,
  153. len
  154. &#40;
  155. input
  156. &#41;
  157. -
  158. 1
  159. # try to match the input to a transition
  160.         successor =
  161. None
  162. if
  163. input
  164. in
  165. self
  166. .__transitions:
  167. # check single-character key match
  168.             successor =
  169. self
  170. .__transitions.
  171. get
  172. &#40;
  173. input
  174. &#41;
  175. else
  176. :
  177. for
  178. s
  179. in
  180. self
  181. .__transitions:
  182. # check multi-char keys
  183. if
  184. input
  185. in
  186. s
  187. and
  188. s !=
  189. self
  190. .
  191. OTHER
  192. :
  193.                     successor =
  194. self
  195. .__transitions.
  196. get
  197. &#40;
  198. s
  199. &#41;
  200. break
  201. if
  202. successor
  203. is
  204. None
  205. :
  206. # use default transition, if any
  207.                 successor =
  208. self
  209. .__transitions.
  210. get
  211. &#40;
  212. self
  213. .
  214. OTHER
  215. &#41;
  216. if
  217. successor
  218. is
  219. None
  220. :
  221. return
  222. self
  223. .
  224. ERROR
  225. ,
  226. False
  227. ,
  228. self
  229. .
  230. ERROR
  231. ,
  232. 0
  233. # successor found, test if it is either an ACCEPT or ERROR state.
  234. if
  235. successor ==
  236. self
  237. .
  238. ACCEPT
  239. :
  240. # ACCEPT
  241. return
  242. self
  243. .
  244. ACCEPT
  245. ,
  246. True
  247. ,
  248. self
  249. .__toktype,
  250. self
  251. .__pushback
  252. elif
  253. successor ==
  254. self
  255. .
  256. ERROR
  257. :
  258. # ERROR
  259. return
  260. self
  261. .
  262. ERROR
  263. ,
  264. True
  265. ,
  266. self
  267. .
  268. ERROR
  269. ,
  270. self
  271. .__pushback
  272. else
  273. :
  274. # not a final state, return the successor state
  275. return
  276. successor,
  277. False
  278. ,
  279. None
  280. ,
  281. 0
  282. def
  283. __str__
  284. &#40;
  285. self
  286. &#41;
  287. :
  288. ""
  289. " Basic string representation of a State."
  290. ""
  291. return
  292. str
  293. &#40;
  294. self
  295. .__transitions
  296. &#41;
  297. class
  298. StateMachine
  299. &#40;
  300. object
  301. &#41;
  302. :
  303. ""
  304. " Generalized Finite State Automata class.
  305.     Instance Variables:
  306.         states: a lookup table of state numbers and states
  307.         current_state: the current state of the FSM
  308.         locked: flag whether all of the states are set.
  309.     A FSM consists of a set of States, the current State, and a flag
  310.     indicating if all States have been added to the set of states. Until
  311.     the FSM is locked, new states may be added. The State machine begins
  312.     in the Start state, and accepts input until it either accepts or rejects
  313.     the input string. When it reaches one of these final states, it returns
  314.     the type of the recongized string and resets itself to the Start state.
  315.    "
  316. ""
  317. def
  318. __init__
  319. &#40;
  320. self
  321. , start_state
  322. &#41;
  323. :
  324. ""
  325. " Constructor - create a FSM object.
  326.         Adds the initial (Start) state, sets the current state to Start,
  327.         and clears the locked flag.
  328.        "
  329. ""
  330. self
  331. .__states =
  332. {
  333. State.
  334. START
  335. : start_state
  336. }
  337. self
  338. .__locked =
  339. False
  340. self
  341. .__current_state =
  342. self
  343. .__states
  344. &#91;
  345. State.
  346. START
  347. &#93;
  348.     @takes
  349. &#40;
  350. "StateMachine"
  351. ,
  352. int
  353. , State
  354. &#41;
  355. def
  356. add
  357. &#40;
  358. self
  359. , key, state
  360. &#41;
  361. :
  362. ""
  363. " Add a new state to the state table.
  364.         The add() method takes a state identifier key and a new State
  365.         object. If the table is not locked, and there is no State
  366.         by that number already, it adds state to the state table
  367.         and returns true. Otherwise, it returns false.
  368.        "
  369. ""
  370. if
  371. self
  372. .__locked:
  373. return
  374. False
  375. # do not allow any states to be added
  376. elif
  377. key
  378. in
  379. self
  380. .__states:
  381. # state with that ID already in table
  382. return
  383. False
  384. else
  385. :
  386. self
  387. .__states
  388. &#91;
  389. key
  390. &#93;
  391. = state
  392. return
  393. True
  394. def
  395. lock
  396. &#40;
  397. self
  398. &#41;
  399. :
  400. ""
  401. " Locks state table so no new states can be added."
  402. ""
  403.         lock =
  404. True
  405.     @returns
  406. &#40;
  407. tuple
  408. &#41;
  409. def
  410. transition
  411. &#40;
  412. self
  413. ,
  414. input
  415. &#41;
  416. :
  417. ""
  418. " Perform a state transition, and if it is a final
  419.         state, return success or failure and the recognized token type.
  420.        "
  421. ""
  422. # get the successor state of the current state, if any
  423.         successor, final,
  424. token
  425. , pb =
  426. self
  427. .__current_state.
  428. next
  429. &#40;
  430. input
  431. &#41;
  432. # see if the state has finalized, reset the current state and
  433. # determine if it accepted or rejected the input string
  434. if
  435. final:
  436. self
  437. .__current_state =
  438. self
  439. .__states
  440. &#91;
  441. State.
  442. START
  443. &#93;
  444. if
  445. successor == State.
  446. ACCEPT
  447. :
  448. # string accepted
  449. return
  450. True
  451. ,
  452. token
  453. , pb
  454. else
  455. :
  456. # string rejected
  457. return
  458. True
  459. , State.
  460. ERROR
  461. , pb
  462. # if the state has not finalized, see if it is a 'non-final' error
  463. # state and return an error value if it is. This will only occur if
  464. # the input is not valid.
  465. elif
  466. successor == State.
  467. ERROR
  468. :
  469. self
  470. .__current_state =
  471. self
  472. .__states
  473. &#91;
  474. State.
  475. START
  476. &#93;
  477. return
  478. True
  479. , State.
  480. ERROR
  481. , pb
  482. # if the state is not final and not an error, advance to the next state
  483. else
  484. :
  485. self
  486. .__current_state =
  487. self
  488. .__states
  489. &#91;
  490. successor
  491. &#93;
  492. return
  493. False
  494. ,
  495. 0
  496. ,
  497. 0
  498. def
  499. __str__
  500. &#40;
  501. self
  502. &#41;
  503. :
  504. ""
  505. "Return a simple string representation of the FSM for debugging. "
  506. ""
  507. return
  508. str
  509. &#40;
  510. self
  511. .__states
  512. &#41;
  513. ################################
  514. if
  515. __name__ ==
  516. "__main__"
  517. :
  518. pass
Copy Code
I have attached a copy of the actual project it had been part of for anyone who wants a reference point in how I intended it to be used.
Any and all (constructive) comments and critiques would be helpful. At the moment, I have tentatively given the projec the name 'AutonomousCollective', but any other suggestions would be appreciated (though I'd prefer something with either a MP or H2G2 theme - the latter to match th name of the original project). TIA.

TOP

Rank: 1
2#
NovaXPost at 2010-5-29 05:02 | Show This Author's Posts Only
I think this implementation is pretty good for what its trying to do, but to be a full-fledged library you need to generalize for 3+ different use-cases.  I think you'll find faults and either fix them or decide to limit the scope of the library to target a narrow nitch.  Both are excellent choices, but force drastically different design choices.
As per your private message regarding my assertion that states should not perform work or provide the transition logic, let me explain why.  A very common use-case is for workfow engines: travel booking, ticket tracking (support, bugs, etc), data processing, and so on.  If your task knows where to go next, then this would leak across different workflows.  If you specify it on a per flow basis, you're still making the execution brittle.  You'll find developers making implicit data dependancies across tasks or creating bizaar flows that loop back through states to arrive at the desired final one.  You'll even find workflows being used where they shouldn't be (e.g. routing of an ESB).  When you make states manage the tranitioning, you put them in control of the framework.  In effect, you are inverting the framework's implicit inversion of control.
I think your project works elegantly for a small, discrete set of states.  But what if you have dozens?  Will there be duplicate state logic but with different transitions, or the same state with many transitions (most of which are not acceptable given the flow)?  Overall, it gets messier and messier the bigger the state machine grows.
Your usage makes me think of Turing machines and push-down automata.  Clients of those tend not to have too many states either, and it would fit well with your usage as well.  So it might be useful as a pre-rolled version to allow others to plug into.  Or at least be a fun excersize to simulate different types of FSA designs.  Even a package of those could be useful, given the very special-purpose nature of them.
I think the first thing to do is determine what class of problems you want to solve and then rework the design as needed.



        is a final state or not, the recognized result (if any) and the
        amount of pushback (if any).
        next() takes a single character input: it will reject any string not
        of size one, returning the number of extraneous characters in
        'pushback'. The method first tries to match the character to a
        state through a simple lookup, on the assumption that most transitions
        will be based on a single possible input. If this does not succeed,
        it will try to match the characters against keys with multiple
        characters; this allows a given state transition to give a set of
        possible matches (e.g., all alphanumeric characters) rather than
        requiring a separate key for each character. If this does not succeed,
        it then checkes to see if there is a default state set. If none of these
        find a match, the method returns an error state.
        If a successor is found, the method then checks to see if the successor
        is either ACCEPT or ERROR. If it is ACCEPT, it returns the ACCEPT
        constant, a true final value, the type of the recongized token, and
        a pushback amount. If it is ERROR, it returns the ERROR constant, a
        true final value, ERROR as the token type, and the pushback amount.
        Otherwise, it returns the successor and false/None/0 for the remainder.
       "
""
if
len
&#40;
input
&#41;
!=
1
:
# check validity of the input
return
self
.
ERROR
,
False
,
self
.
ERROR
,
len
&#40;
input
&#41;
-
1
# try to match the input to a transition
        successor =
None
if
input
in
self
.__transitions:
# check single-character key match
            successor =
self
.__transitions.
get
&#40;
input
&#41;
else
:
for
s
in
self
.__transitions:
# check multi-char keys
if
input
in
s
and
s !=
self
.
OTHER
:
                    successor =
self
.__transitions.
get
&#40;
s
&#41;
break
if
successor
is
None
:
# use default transition, if any
                successor =
self
.__transitions.
get
&#40;
self
.
OTHER
&#41;
if
successor
is
None
:
return
self
.
ERROR
,
False
,
self
.
ERROR
,
0
# successor found, test if it is either an ACCEPT or ERROR state.
if
successor ==
self
.
ACCEPT
:
# ACCEPT
return
self
.
ACCEPT
,
True
,
self
.__toktype,
self
.__pushback
elif
successor ==
self
.
ERROR
:
# ERROR
return
self
.
ERROR
,
True
,
self
.
ERROR
,
self
.__pushback
else
:
# not a final state, return the successor state
return
successor,
False
,
None
,
0
def
__str__
&#40;
self
&#41;
:
""
" Basic string representation of a State."
""
return
str
&#40;
self
.__transitions
&#41;
class
StateMachine
&#40;
object
&#41;
:
""
" Generalized Finite State Automata class.
    Instance Variables:
        states: a lookup table of state numbers and states
        current_state: the current state of the FSM
        locked: flag whether all of the states are set.
    A FSM consists of a set of States, the current State, and a flag
    indicating if all States have been added to the set of states. Until
    the FSM is locked, new states may be added. The State machine begins
    in the Start state, and accepts input until it either accepts or rejects
    the input string. When it reaches one of these final states, it returns
    the type of the recongized string and resets itself to the Start state.
   "
""
def
__init__
&#40;
self
, start_state
&#41;
:
""
" Constructor - create a FSM object.
        Adds the initial (Start) state, sets the current state to Start,
        and clears the locked flag.
       "
""
self
.__states =
{
State.
START
: start_state
}
self
.__locked =
False
self
.__current_state =
self
.__states
&#91;
State.
START
&#93;
    @takes
&#40;
"StateMachine"
,
int
, State
&#41;
def
add
&#40;
self
, key, state
&#41;
:
""
" Add a new state to the state table.
        The add() method takes a state identifier key and a new State
        object. If the table is not locked, and there is no State
        by that number already, it adds state to the state table
        and returns true. Otherwise, it returns false.
       "
""
if
self
.__locked:
return
False
# do not allow any states to be added
elif
key
in
self
.__states:
# state with that ID already in table
return
False
else
:
self
.__states
&#91;
key
&#93;
= state
return
True
def
lock
&#40;
self
&#41;
:
""
" Locks state table so no new states can be added."
""
        lock =
True
    @returns
&#40;
tuple
&#41;
def
transition
&#40;
self
,
input
&#41;
:
""
" Perform a state transition, and if it is a final
        state, return success or failure and the recognized token type.
       "
""
# get the successor state of the current state, if any
        successor, final,
token
, pb =
self
.__current_state.
next
&#40;
input
&#41;
# see if the state has finalized, reset the current state and
# determine if it accepted or rejected the input string
if
final:
self
.__current_state =
self
.__states
&#91;
State.
START
&#93;
if
successor == State.
ACCEPT
:
# string accepted
return
True
,
token
, pb
else
:
# string rejected
return
True
, State.
ERROR
, pb
# if the state has not finalized, see if it is a 'non-final' error
# state and return an error value if it is. This will only occur if
# the input is not valid.
elif
successor == State.
ERROR
:
self
.__current_state =
self
.__states
&#91;
State.
START
&#93;
return
True
, State.
ERROR
, pb
# if the state is not final and not an error, advance to the next state
else
:
self
.__current_state =
self
.__states
&#91;
successor
&#93;
return
False
,
0
,
0
def
__str__
&#40;
self
&#41;
:
""
"Return a simple string representation of the FSM for debugging. "
""
return
str
&#40;
self
.__states
&#41;
################################
if
__name__ ==
"__main__"
:
pass

I have attached a copy of the actual project it had been part of for anyone who wants a reference point in how I intended it to be used.
Any and all (constructive) comments and critiques would be helpful. At the moment, I have tentatively given the projec the name 'AutonomousCollective', but any other suggestions would be appreciated (though I'd prefer something with either a MP or H2G2 theme - the latter to match th name of the original project). TIA.

TOP

Back Forum