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
