Does a `state machine generator' exist?

Chris F Clark <cfc@world.std.com>
1 Jun 2000 17:56:32 -0400

          From comp.compilers

Related articles
Does a `state machine generator' exist? imdave@mcs.net (Dave Bodenstab) (2000-05-30)
Re: Does a `state machine generator' exist? eodell@pobox.com (Eric O'Dell) (2000-05-31)
Does a `state machine generator' exist? cfc@world.std.com (Chris F Clark) (2000-06-01)
Re: Does a `state machine generator' exist? sergio@titan.demon.co.uk (sergio) (2000-06-03)
| List of all articles for this month |

From: Chris F Clark <cfc@world.std.com>
Newsgroups: comp.compilers
Date: 1 Jun 2000 17:56:32 -0400
Organization: Compilers Central
References: 00-05-115
Keywords: lex, DFA

> Is there such a beast as a state machine generator on the order of
> lex/yacc?


Yes, there are several. I don't know all the names.


However, some are popular in the real-time community, which is an area
I don't follow. One I recall was named VROOM or something close to
that.


There are also ones used by EDA (chip) designers, but those mostly
output Verilog or VHDL--the languages chips are designed in. Renoir
is an example of this type.


Finally, there is a whole class of them based upon an updated form of
state machines called "State Charts" (invented by David Harel)--State
Mate is the name that I recall. You may also find this kind of state
machine generator integrated into your "UML" modelling tool.


The advantage of most of the above tools is that they works on state
machines in terms of states and transitions. (Some of them, Renoir
for instance, even work from a graphical representation of the state
machine.)


If you follow our moderator's suggestion and use LEX due to the
correspondence between DFA's and regular expressions, you will have to
convert state diagram into a regular expression by hand. There is no
way to input a set of states and transitions into LEX. In fact, the
whole point of LEX is to translate regular expressions into states and
transitions. Of course, if your problem has a natural formulation in
terms of regular expressions, then you can use those regular
expressions as your input to LEX.


BTW, if you do go with the LEX approach and your transitions are on
"named events", I might recommend using a parser that supports regular
expressions over using LEX. If you do so, you can use each named
event as a "token"--that may be simpler and more readable than picking
character representations for the events. (For example, in an ATM
(automated teller machine) state machine, it might make sense to map
"deposit" to "d" and "check" to "c", but then what do you map "cancel"
to?)


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)





Post a followup to this message

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