Welcome, guest | Sign In | My Account | Store | Cart
#! /usr/bin/env python

""" Generic finite state machine class
    Initialise the class with a list of tuples - or by adding transitions
"""


class fss(object):
   
def __init__(self, states=[]):
       
self._states=states
       
self.currentState = None

   
def start(self,startState=None):
       
""" Start the finite state machine
        """

       
if not startState or not (startState in [x[0] for x in self._states]):
           
raise ValueError("Not a valid start state")
       
self.currentState = startState

   
def stop(self):
       
""" Stop the finite state machine
        """

       
self.startState = None
   
   
def addTransition(self,fromState, toState, testFunc):
       
""" Add a state transition to the list, order is irellevant, loops are undetected
            Can only add a transition if the state machine isn't started.
        """

       
if not self.currentState:
           
raise ValueError("StateMachine already Started - cannot add new transitions")

       
# add a transition to the state table
       
self._states.append( (fromState, toState,testFunc))

   
def event(self, value):
       
""" Trigger a transition - return a tuple (<new_state>, <changed>)
            Raise an exception if no valid transition exists.
            Callee needs to determine if the value should be consumed or re-used
        """

       
if not self.currentState:
           
raise ValueError("StateMachine not Started - cannot process event")

       
# get a unique list of next states which are valid      
       
self.nextState = list(set( \
                   
[ x[1] for x in self._states\
                   
if x[0] == self.currentState \
                           
and (x[2]==True or (callable(x[2]) and x[2](value))) ] ) )

       
if not self.nextState:
           
raise ValueError("No Transition defined from state {0} with value '{1}'".format(self.currentState, value))
       
elif len(self.nextState) > 1:
           
raise ValueError("Ambiguous transitions from state {0} with value '{1}' ->  New states defined {2}".format(self.currentState, value, self.nextState))
       
else:
           
self.currentState, ret = (self.nextState[0], True) \
                   
if self.currentState != self.nextState[0] else (self.nextState[0], False)
           
return self.currentState, ret

   
def CurrentState(self):
       
""" Return the current State of the finite State machine
        """

       
return self.currentState

# Example code - showing populates of the state machine in the constructor
# the Machine could also be constructed by multiple calls to addTransition method
# Example code is a simple tokeniser
# Machine transitions back to the Start state whenever the end of a token is detected

if __name__ == "__main__":
    fs
= fss( [ ("Start","Start",lambda x: x.isspace() ),
               
("Start","Identifier",str.isalpha),
               
("Identifier","Identifier", str.isalnum),
               
("Identifier","Start",lambda x: not x.isalnum() ),
               
("Start","Operator", lambda x: x in "=+*/-()"),
               
("Operator","Start", True),
               
("Start","Number",str.isdigit),
               
("Number","Number",lambda x: x.isdigit() or x == "." ),
               
("Number","Start",lambda x: not x.isdigit() and x != "." ),
               
("Start","StartQuote",lambda x: x == "\'"),
               
("StartQuote","String", lambda x: x != "\'"),
               
("String","String",lambda x: x != "\'"),
               
("String","EndQuote", lambda x: x == "\'"),
               
("EndQuote","Start", True ) ] )

    fs
.start("Start")

    a
= "    x123=MyString+123.65-'hello'*value"
    c
= 0
   
while c < len(a):
        ret
= fs.event(a[c])
       
print "{0}-> {1}".format(a[c], ret)
       
# Make sure a transition back to start (from something else) does not consume the character.
       
if ret[0] != "Start" or (ret[0] == "Start" and ret[1] == False):
            c
+= 1

History