[Tutor] what's a state machine?

[Sean 'Shaleh' Perry]

On Tuesday 05 August 2003 17:30, Kirk Bailey wrote:
> oy vey...
>
> A STATE MACHINE is in effect a computer. It is simulated in code. It is
> customized for the task at hand. A simple state machine would be a
> turing machine if it was 'turing complete'. A turing machine is the
> minimal machine which may be properly called 'a computer'.
>
> I may run off screaming... I  hope someone, ANYONE, can provide some
> advice.
>

And here you make the most common of programmer errors -- you make the 
solution too generic.

State machines can be quite simple and need not be something ultra-scary.

Basically you define states your parsing/program might take and what will 
cause the transition from state to state.  The advantage gained is that you 
now have context when you read the next piece of text to parse so you know 
what you expect to find.

let's pretend I am in state WANT_R_PARENS and the input stream looks like 
'blah)'.

does b get me out of WANT_R_PARENS? nope, let's store it instead.
does l? ...
a? ...
h? ...
)? ah, yes it does.  So now we have 'blah' and are ready to leave state 
WANT_R_PARENS.  Maybe this is a math app and instead of a string we would 
have expressions.

2 + (2+(3*2))

each time we hit the found R paren state we would compute the expression we 
just finished.

That's all a state machine is.

"Start in state BEGIN.  When the next token (aka character, symbol, etc) is a 
left paren enter state WANT_R_PARENT.  When a right paren is found compute 
the expression and return to the BEGIN state."

Now if we find some other state trigger before we satisfy WANT_R_PAREN then we 
have a parse error and need to handle it.

If the input was 2 + (2+(3*2()) for instance, we can only satisfy 
WANT_R_PARENT twice and will trigger an error.