mouse@shamash.McRCIM.McGill.EDU (der Mouse) (08/10/90)
> 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 program. 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. $prefix jf_parse /* $trace jf_trace */ $state main $tran "keep"->keep setup_keep $tran "default"->default setup_default $tran "for"->for setup_for .... $state for $tran !pattern for_pat1 $state $tran "junk" $state $tran !pattern for_pat2 $state for_opt $tran $eos->$exit $tran !option->for_opt $state pattern $tran $lambda initpattern $state patchar $tran $eos->$exit endpattern $tran ' '->$exit endpattern $tran '\t'->$exit endpattern $tran '\\'->patchar_quote $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. der Mouse old: mcgill-vision!mouse new: mouse@larry.mcrcim.mcgill.edu -- Send compilers articles to compilers@esegue.segue.boston.ma.us {spdcc | ima | lotus| world}!esegue. Meta-mail to compilers-request@esegue.