Re: GoTo in FSM (was Help with Exceptions)

[eachus@spectre.mitre.org (Robert I. Eachus)]

In article <9605151336.AA03830@most> "W. Wesley Groleau (Wes)" <wwgrol@PSESERV3.FW.HAC.COM> writes:

  > I keep hearing about the value of GoTo for a finite state machine.
  > Perhaps my understanding of an FSM is incorrect, but every time
  > I've coded what I THOUGHT was a state machine, I used neither GoTo
  > nor recursion and didn't think the code was exceptionally ugly.
  > With Ada 83 the awkward part was defining (and _maintaining_) an
  > enumerated type with one literal for each action (plus error).
  > Another type enumerated the states.  A record type contains one of
  > each.

   The problem is that you have conceptually a large two dimensional
array indexed by current state and transition.  In a parser with
several hundred tokens and a thousand or so states that array gets big
fast.   So when you get to this line:

  >    case State_Transition ( Current_State, Trigger ).Action is

  What you want to do is to make State_Transition a function which
returns a tuple, and store the array in a compact form.  The usual
form for doing that is to have a large one-dimensional array with
entries (trigger, action, next state), (default, action, next_state),
(error, ..., resume in state), or (continue, ... , state to continue
with).

   In a parser or scanner it is the routine you call State_Transition
that ends up containing the gotos.  You can also implement a (usually
less than a dozen states) state machine by having each state correpond
to a label.  In fact this is usually how the state transition routine
or parser driver is coded.  There are a few states, including panic
mode error recovery, and the parser "walks" between them.

  >  Now I wouldn't call that beautiful, but I wouldn't call it ugly
  > either. 

   Agreed.  I could pretty it up a bit, but if you can afford the
space to implement the state table as an array, there isn't a problem.

--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...