From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,35ee5809875c7607
X-Google-Attributes: gid103376,public
From: eachus@spectre.mitre.org (Robert I. Eachus)
Subject: Re: GoTo in FSM (was Help with Exceptions)
Date: 1996/05/15
Message-ID: <EACHUS.96May15171124@spectre.mitre.org>#1/1
X-Deja-AN: 154986380
references: <9605151336.AA03830@most>
organization: The Mitre Corp., Bedford, MA.
newsgroups: comp.lang.ada
Date: 1996-05-15T00:00:00+00:00
List-Id: <comp.lang.ada>


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...