Request pointers to compilers for `finite state machines'

tfd!kent@uunet.UU.NET (Kent Hauser)
Sun, 05 Aug 90 22:55:06 GMT

          From comp.compilers

Related articles
Request pointers to compilers for `finite state machines' tfd!kent@uunet.UU.NET (1990-08-05)
Re: Request pointers to compilers for `finite state machines' carroll@udel.edu (Mark Carroll) (1990-08-06)
| List of all articles for this month |

Newsgroups: comp.compilers
From: tfd!kent@uunet.UU.NET (Kent Hauser)
Keywords: lex, DFA, question
Organization: Twenty-First Designs, Wash, DC
Date: Sun, 05 Aug 90 22:55:06 GMT

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]
--


Post a followup to this message

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