|FSM-type tools under UNIX mouse@shamash.McRCIM.McGill.EDU (der Mouse) (1990-08-09)|
|From:||der Mouse <mouse@shamash.McRCIM.McGill.EDU>|
|Date:||Thu, 09 Aug 90 18:07:29 GMT|
> I'm looking for reference material (and of course examples) for
> compilers used to implement `finite state machines'.
It doesn't sound like quite what you want, but I have something at
least somewhat related. My program takes a description of a somewhat
extended FSM-like machine and generates C code that implements it.
How does it differ from what I think you want?
The major way is that transitions are driven off of objects found in a
string (which is passed as an argument to the main entry point). A
minor way is that the input language describes a considerably richer
sort of machine than strict FSMs. Action routines can be specified and
are inserted into the generated C code as appropriate.
I use it primarily for writing simple parsers. The machine
descriptions are powerful enough that recursive-descent parsers are
fairly straightforward, though perhaps not as efficient as one might
wish for "serious" applications. (To be honest, I have done no
performance analysis at all. I use it only for small pieces of larger
programs, in places where I've never cared about performace.) For
small applications, I find it much faster to develop, test, and debug
parsers written this way than those written with lex/yacc. My code can
also handle some things that are difficult or impossible with lex/yacc
(of course the converse is also true). And, there's nothing the least
bit difficult about using more than one of my machines in a single
Here is a sample of the input, a piece of an input file from a real
application. The things off at the right are the action routines.
/* $trace jf_trace */
$tran "keep"->keep setup_keep
$tran "default"->default setup_default
$tran "for"->for setup_for
$tran !pattern for_pat1
$tran !pattern for_pat2
$tran $lambda initpattern
$tran $eos->$exit endpattern
$tran ' '->$exit endpattern
$tran '\t'->$exit endpattern
$tran $any->patchar pattern_char(0)
Users of VMS's LIB$TPARSE facility will find this very familiar.
If anyone wants more information, feel free to write to me. I do not
normally read compilers (the note to which I am replying was forwarded
to me), so I probably won't see posted replies.
Return to the
Search the comp.compilers archives again.