== Introduction ==
Validators are objects that are used for checking syntax, often of the fairly short items that users enter by way of edit boxes in dialogs. State machines are an easily understood, easily comprehended way of representing the small grammars that typically describe these items of data. Hence the motivation to use state machines as the basis for validators.
Incidentally, regular expressions, which are equivalent to state machines, can be used to check input. However, in the context of accepting input from a user one character at a time, say in an edit box, one would like to be able to test this input incrementally, that is, as it arrives, to be able to offer immediate feedback.
This recipe is in four parts.
The first part provides state machine code that is derived from that presented by David Mertz' in his
introduction to using state machines, which is available at
http://www-106.ibm.com/developerworks/linux/library/l-python-state.html.
The second part shows how to use the state machine code to test the acceptability of strings against a simple grammar.
The third part exhibits the validator that uses state machines.
The fourth part provides some state machines that work with the validator.
== What Objects are Involved ==
This code imports only one function from the `new` module that is standard Python.
== Process Overview ==
One begins the job of creating a validator that is based on a state machine by creating and verifying the state machine. In this recipe part, though, the aim is not to build a state machine that will be used in a validator, only to exhibit a complete state machine in a simple setting.
A state machine is driven through its various states by a series of tokens. The sequence of tokens sent to the machine is said to be "acceptable" if it drives the machine to an "acceptable" end state. Otherwise, the sequence is deemed to be "unacceptable". In this example, the tokens that drive the machine are numbers that are generated by `math_func`. In a validator the sequence of tokens sent to the state machine is the sequence of characters entered by the user.
The functions called `ones_counter`, `tens_counter`, and so on, in fact all those with formal parameters `self` and `token`, represent the "states" of the machine. It is the responsibility of each of these functions to examine incoming tokens and, in some cases and in come circumstances, to accept further tokens for examination, and to decide which state should be selected next--or to reject the token, possibly by raising an exception.
Enough about details like that. Suffice to say that the `StateMachine` class presented here breathes life into the states, and that I hope to have saved you the need to change this class.
However, you should note that my class differs a little from Mertz':
* Each state function has two parameters, the second being the one for the token that it has been passed either by `StateMachine` directly, or by another state function. This source of tokens has to be written as a generator--like my version of math_func.
* Use the `StateMachine` method called `setTokens` to register the tokens source.
* The `StateMachine` method called 'run' takes no parameters (unlike Mertz' version). Rather, it obtains the first token itself, from the tokens source.
* `addState` does a little more than Mertz' version. It arranges to add the function passed to it to the class instance at run-time. I am indebted to Brett Cannon and Alex Martelli for their recipe entitled "Dynamically added methods to a class" at http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/81732.
* I have added some convenience functions, for passing strings to be tested to the state machine and then exercising it, and also to ease the task of returning results and interpreting them.
== Code Sample ==
{{{
#!python
from new import instancemethod
class EStringTooShort ( Exception ) : pass
class EBadCharacter ( Exception ) : pass
class TestStringResult :
def __init__ ( self, name, value ) :
self . name = name
self . value = value
def rejectCharacter ( self ) :
return self . value in [ 1, 4 ]
def validatedString ( self ) :
return self . value == 3
def __str__ ( self ) :
return self . name
BADCHARACTER = TestStringResult ( 'BADCHARACTER', 1 )
STRINGTOOSHORT = TestStringResult ( 'STRINGTOOSHORT', 2 )
OK = TestStringResult ( 'OK', 3 )
STRINGTOOLONG = TestStringResult ( 'STRINGTOOLONG', 4 )
class StateMachine :
def __init__ ( self ) :
self . handlers = { }
self . startState = None
self . endStates = [ ]
self . allTokens = [ ]
def addState ( self, handler, endState = False ) :
method = instancemethod ( handler, self, StateMachine )
self . __dict__ [ handler . __name__ ] = method
name = handler . __name__
self . handlers [ name ] = method
if endState : self . endStates . append ( name )
def testString ( self, stringToTest ) :
def oneAtATime ( str ) :
for c in str : yield c
raise EStringTooShort ( )
self . allTokens = [ ]
self . setTokens ( oneAtATime ( stringToTest ) )
try : self . run ( )
except EBadCharacter : return BADCHARACTER
except EStringTooShort : return STRINGTOOSHORT
try : self . nextToken ( )
except EStringTooShort : return OK
else : return STRINGTOOLONG
def setTokens ( self, tokens ) :
self . tokens = tokens
def nextToken ( self ) :
if len ( self . pushedTokens ) :
newToken = self . pushedTokens . pop ( -1 )
else :
newToken = self . tokens . next ( )
self . allTokens . append ( newToken )
return newToken
def pushToken ( self ) :
token = self . allTokens . pop ( -1 )
self . pushedTokens . append ( token )
def setStartState ( self, handler ) :
self . startState = handler . __name__
def run ( self ) :
try :
handler = self . handlers [ self . startState ]
except :
raise "InitializationError", "must call .setStartState() before .run()"
self . pushedTokens = [ ]
token = self . nextToken ( )
if not self . endStates :
raise "InitializationError", "at least one state must be an end state"
while 1 :
newState, token = handler ( token )
if newState in self . endStates:
if self . handlers [ newState ] :
self . handlers [ newState ] ( token )
break
else:
handler = self . handlers [ newState ]
if __name__ == "__main__" :
from math import sin
def ones_state ( self, token ) :
print "ONES_STATE: ",
while 1:
if token <= 0 or token >= 30 : newState = "end_state" ; break
elif 20 <= token < 30 : newState = "twenties_state"; break
elif 10 <= token < 20 : newState = "tens_state"; break
else : print " @ %2.1f+" % token,
token = self . nextToken ( )
print " >>"
return newState, token
def tens_state ( self, token ) :
print "TENS_STATE: ",
while 1:
if token <= 0 or token >= 30 : newState = "end_state"; break
elif 1 <= token < 10 : newState = "ones_state"; break
elif 20 <= token < 30 : newState = "twenties_state"; break
else : print " #%2.1f+" % token,
token = self . nextToken ( )
print " >>"
return newState, token
def twenties_state ( self, token ) :
print "TWENTIES_STATE: ",
while 1:
if token <= 0 or token >= 30 : newState = "end_state"; break
elif 1 <= token < 10 : newState = "ones_state"; break
elif 10 <= token < 20 : newState = "tens_state"; break
else : print " *%2.1f+" % token,
token = self . nextToken ( )
print " >>"
return newState, token
def end_state ( self, token ) :
print "END_STATE: %2.1f" % token
def math_func ( n ) :
while 1 :
n = abs ( sin ( n ) ) * 31
yield n
statemachine = StateMachine ( )
statemachine . addState ( ones_state )
statemachine . addState ( tens_state )
statemachine . addState ( twenties_state )
statemachine . addState ( end_state, True )
statemachine . setStartState ( ones_state )
statemachine . setTokens ( math_func ( 1 ) )
statemachine . run ( )
}}}
=== Comments ===
I welcome your comments. - [[Bill Bell]]