kent@uunet.UU.NET (Kent Hauser) (08/06/90)
I'm looking for reference material (and of course examples) for compilers
used to implement `finite state machines'.
Preferably, the input to the compiler would be a `grammar' which describes
all of the legal constructs (and error recovery), and the output would be a
bunch of tables holding state transition information & function pointers as
appropriate.
There would, of course, be some kind of engine which ran around & did the
state transition as appropriate.
My specific applications are telephone signaling and data communications
protocols. The engines for the two differ in that the former would be
implemented by scanning at a fixed rate & changing state based on signaling
state, etc. The latter is more event driven (with timeout being one type of
event).
Help with either type would be appreciated.
Thanks.
--
Kent Hauser UUCP: {uunet, sun!sundc}!tfd!kent
Twenty-First Designs INET: kent@tfd.uu.net
(202) 408-0841
[Given the well-known equivalence between regular expressions and finite
state machines (albeit not a one-to-one equivalence) there are many programs
that compile regular expressions into FSMs and then run them. Unix users are
most familiar with lex and flex. Aho, Hopcroft, and Ullman discuss the theory
and practice of lex in considerable detail. Holub's new book skims over the
theory, but has lots of sample code for creating and running DFAs. I don't
know if some other way of writing the state tables might be easier for
non-lexical applications, perhaps some reader can comment. -John]
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus| world}!esegue. Meta-mail to compilers-request@esegue.carroll@udel.edu (Mark Carroll) (08/07/90)
In article <1990Aug05.225506.12815@esegue.segue.boston.ma.us> tfd!kent@uunet.UU.NET (Kent Hauser) writes: >I'm looking for reference material (and of course examples) for compilers >used to implement `finite state machines'. ... >My specific applications are telephone signaling and data communications >protocols. The engines for the two differ in that the former would be >implemented by scanning at a fixed rate & changing state based on signaling >state, etc. The latter is more event driven (with timeout being one type of >event). I'd suggest looking at Estelle. Estelle is a language used to specify network protocols. The protocol is specified in terms of communicating modules, where the behavior of each module is described by a FSM. It sounds like exactly what you're looking for. To find out more about Estelle, try: @article{ title="An Introduction to Estelle:\ A Specification Language for Distributed Systems", author=" P. Dembinski and S. Budkowski", journal="Computer Networks and ISDN Systems", volume="14", number="1", month="January", year="1987", pages="3-23" } <MC> -- |Mark Craig Carroll: <MC> |Soon-to-be Grad Student at |University of Delaware |carroll@dewey.udel.edu -- Send compilers articles to compilers@esegue.segue.boston.ma.us {spdcc | ima | lotus| world}!esegue. Meta-mail to compilers-request@esegue.