FSM-type tools under UNIX

der Mouse <mouse@shamash.McRCIM.McGill.EDU>
Thu, 09 Aug 90 18:07:29 GMT

          From comp.compilers

Related articles
FSM-type tools under UNIX mouse@shamash.McRCIM.McGill.EDU (der Mouse) (1990-08-09)
| List of all articles for this month |

Newsgroups: comp.compilers
From: der Mouse <mouse@shamash.McRCIM.McGill.EDU>
Keywords: DFA
Organization: Compilers Central
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.

$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
$tran "junk"
$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

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.