Finite state machine compiler 
Author Message
 Finite state machine compiler

Bernie Mentink asked for my fsm compiler, that takes a state table
representation and turns it into a fsm. This was essentially the code
(and example) that was posted in connection with the GOTO discussion.
I sent him a copy; his reply (parts deleted) and my response seem
worth posting here for several reasons:

        1. The amended code is more completely documented than the
           original (that I thought was VERY well documented already--
           silly me!), as well as slightly simplified. So it may
           serve as an example of ULTIMATE COMMENTING for newcomers ;-)

        2. I have changed stuff to conform with F83 so it should be
           easy to port to ANS FORTH.

        3. I think it is a useful technique (several people have told
           me this already).

------------------------------- begin --------------------------------
From jvn Fri Apr 29 11:54:23 1994
Subject: Re: State machines

Date: Fri, 29 Apr 1994 11:54:23 -0400 (EDT)

Quote:
> Hi Julian,

> Thanks for the code, however it's double dutch to me as it is not
> very well documented ( sorry! ) and it is written with some un-familiar
> varient of forth ( read non-standard? ).

> I use forth a lot and can work out what most code does, but not in
> this case. Thanks for your time.

\ ================================================ FINITE STATE MACHINE


\ from stack onto rstack; DR> means take top 2 16-bit cells from rstack
\ and put 'em on stack. I think I have changed nomenclature to F83
\ correctly... UNDER means TUCK, PLUCK means NIP. Frankly, I prefer
\ UNDER and PLUCK as names, but the X3J14 Committee did not agree.
\ Finally, I have simplified the run-time action with less stack-
\ juggling--I must have been half-asleep the first time I coded it!

\ create a finite state machine by compiling the state transition
\ table. FSM: is (obviously) a defining word. I have increased the
\ documentation using a vertical format. Hope it helps. If you want
\ to know more, read my book, or my articles in Computers in Physics
\ or Rochester FORTH Conf Proceedings (1990, I think).

: WIDE   0 ;                    \ put 0 on stack

: FSM:   ( width 0 -- )         \ compile-time actions
        CREATE  ( width 0 )     \ make new header
        ,                       \ state variable is first cell of parameter
                                \ field of new word; initialize to 0.
        ,                       \ store width of table
        ]                       \ switch to compile mode

                                \ run-time actions
        DOES>   ( col# -- )  \ expect a column number as input
                ( -- col# pfa)  \ DOES> leaves pfa

               *  +   1+  4*    ( -- pfa offset-to-next action )
               OVER +           ( -- pfa  pfa+offset )


               SWAP !           \ update state
        ;

\ IMPORTANT NOTE:
\ This version of FSM updates the state ***after*** the action.

\ I define these constants so when they are compiled into the FSM, their
\ execution tokens are fetched and executed to get the new state value.

0 CONSTANT >0   3 CONSTANT >3   6 CONSTANT >6
1 CONSTANT >1   4 CONSTANT >4   7 CONSTANT >7
2 CONSTANT >2   5 CONSTANT >5

\ ============================================ END FINITE STATE MACHINE

\ ========================================= Automatic conversion tables
\ This is just a utility for crerating self-acting translation tables.
: TAB:   ( #bytes -- )

\           ( n tab[0] -- n')

: install      ( col# adr char.n char.1 -- )   \ fast fill
               SWAP 1+ SWAP   DO  2DUP I +  C!  LOOP  2DROP ;
\ ===================================== end automatic conversion tables

\ Usage example

VARIABLE id.len         0 id.len !

\


\ By making >1? a conditional state transition, I convert the deterministic
\ fsm to a non-deterministic one. This is the advantage of using CONSTANTs
\ to do the state transitions--when necessary they can be replaced with
\ other words.

3 WIDE FSM: (id)
\ input:     |  other  |  letter   |    digit    |
\ state      -------------------------------------
   ( 0 )       NEXT >2   +id.len >1    NEXT >2
   ( 1 )       NEXT >2   +id.len >1?   +id.len >1?  ;

\ note how the table headers are included as comment lines...

' (id) >BODY  CONSTANT  id.state     \ returns pfa of (id)

\ make an automatic translation table, char -> col#
128 TAB: [id]
1 ' [id] >BODY  ASCII Z  ASCII A  install
1 ' [id] >BODY  ASCII z  ASCII a  install
2 ' [id] >BODY  ASCII 9  ASCII 0  install

\ is $ (text between $beg and $end, inclusive) a proper BNF id?

: <id>   ( $end $beg -- f)   \ f = -1 for id, -2 for null, 0 else
         2DUP  NULL D=  IF  2DROP  -2  EXIT  THEN
         0 id.len !                             \ id.len = 0
         0 id.state !                           \ set state = 0

                 [id]                           ( -- $end $beg col#)
                 (id)                           \ invoke fsm
                 ( $end $beg)  2DUP  >               \ more chars?

                 AND                            \ both must be true
         WHILE   1+                             \ $beg = $beg + 1
         REPEAT                                 \ end of loop
         2DROP                                  \ clean up stack

         ;
\ the line with NULL tests if the text is the predefined string NULL.
--------------------------------- end -------------------------------

I hope I have remembered to fix everything non-standard (i.e. from
HS/FORTH conventions).
--
Julian V. Noble



Wed, 16 Oct 1996 02:14:14 GMT  
 Finite state machine compiler
Well, I can follow your example up to a certain point.  What is the
definition of the word "NEXT"?  It's not part of F83 (or at least on
L&P's dialect nor another F83 dialect that I've got).

Thanks!

--
/ ------------------------------------------------------------------------ \
/ Mark Flacy             "There's a lot to be said for a blow to the head" \

/                        "I guess ya had to be there." - Me                \



Sun, 20 Oct 1996 15:58:14 GMT  
 Finite state machine compiler

Quote:

> Well, I can follow your example up to a certain point.  What is the
> definition of the word "NEXT"?  It's not part of F83 (or at least on
> L&P's dialect nor another F83 dialect that I've got).

> Thanks!

> --
> / ------------------------------------------------------------------------ \
> / Mark Flacy             "There's a lot to be said for a blow to the head" \

> /                        "I guess ya had to be there." - Me                \

NEXT is in some dialects, not in others. If you prefer, define NOP
by  : NOP  ;  and use that.

IN F-PC, hi-level NEXT is used in FOR...NEXT; lo-level is in the ASSEMBLER
vocabulary and installs the code to leave a word. Why it is not made part
of END-CODE is by no means obvious to me.

So do NOT use the versions of NEXT found in F-PC when NOP is what you mean.
--
Julian V. Noble



Tue, 22 Oct 1996 03:38:39 GMT  
 Finite state machine compiler

:
: IN F-PC, hi-level NEXT is used in FOR...NEXT; lo-level is in the ASSEMBLER
: vocabulary and installs the code to leave a word. Why it is not made part
: of END-CODE is by no means obvious to me.

NEXT isn't part of END-CODE because you don't always want to exit a code
definition back to the interpreter.  One instance is when you're writing
an interrupt handler and have to exit with an RTI.  Another is if you're
factoring your assembler routines into subroutines and need an RTS.
--

Intelligent System Sensors and Controls Dept. 2111
Sandia National Laboratories
P.O. Box 5800, Albuquerque, New Mexico 87185-0949



Sun, 27 Oct 1996 21:51:07 GMT  
 Finite state machine compiler

Quote:

>:
>: IN F-PC, hi-level NEXT is used in FOR...NEXT; lo-level is in the ASSEMBLER
>: vocabulary and installs the code to leave a word. Why it is not made part
>: of END-CODE is by no means obvious to me.

>NEXT isn't part of END-CODE because you don't always want to exit a code
>definition back to the interpreter.  One instance is when you're writing
>an interrupt handler and have to exit with an RTI.  Another is if you're
>factoring your assembler routines into subroutines and need an RTS.
>--

>Intelligent System Sensors and Controls Dept. 2111
>Sandia National Laboratories
>P.O. Box 5800, Albuquerque, New Mexico 87185-0949

Hmm. . . Yeah, but. . .

What's the difference between:

RTI END-CODE

and

RTI NEXT END-CODE

??
The NEXT will not be executed, will it?  (I know that it will waste a
cell of storage for the NEXT token which will make most FORTH
programmers' eyes bulge in horror....)

I'm sure there really is one situation where you *really* don't want
to compile the NEXT prior to the END-CODE. (I didn't say that I could
think of it.)  The finer factoring *does* seem more in line with FORTH
philosophy in that you could always re-define END-CODE to include the
NEXT.  It's the other way around that is a real PIA.

--
/ ------------------------------------------------------------------------ \
/ Mark Flacy             "There's a lot to be said for a blow to the head" \

/                        "I guess ya had to be there." - Me                \



Mon, 28 Oct 1996 15:25:01 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. finite state machines, state cad

2. Finite State Machine and Forth

3. Finite State Machines

4. ESTEREL, Forth and finite state machines

5. finite state machines

6. Finite State Machines

7. OO Finite State Machine Language

8. Finite State Machine inherent support

9. cisco_fsm (finite state machine) free tool: pre-announcement

10. Use of a Finite State Machine in testbench code

11. FSMedit - The Finite State Machines Editor - Version 2.0

12. finite-state-machine problems => Synopsys

 

 
Powered by phpBB® Forum Software