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