I need help building a data structure for a state diagram

[Kay Schluehr]

On 25 Mai, 01:46, Matthew Wilson <m... at tplus1.com> wrote:
> On Sun 24 May 2009 03:42:01 PM EDT, Kay Schluehr wrote:
>
>
>
> > General answer: you can encode finite state machines as grammars.
> > States as non-terminals and transition labels as terminals:
>
> > UNSTARTED: 'start' STARTED
> > STARTED: 'ok' FINISHED | 'cancel' ABANDONED
> > ABANDONED: 'done'
> > FINISHED: 'done'
>
> > In some sense each state-machine is also a little language.
>
> I've never formally studied grammars, but I've worked through trivial
> stuff that uses BNF to express ideas like
>
>     <postal-address> ::= <name-part> <street-address> <zip-part>
>
> I don't really understand how to apply that notion to this statement:
>
>     UNSTARTED: 'start' STARTED
>
> That doesn't seem to be BNF, and that's all I know about grammar stuff.

Some comments

1) The separator is arbitrary. You can use ':' or '->' or '::=' etc.
2) A full EBNF grammar can be described in itself:

   GRAMMAR: RULE+
   RULE: NAME ':' RHS
   RHS: ALT ( '|' ALT )*
   ALT: ITEM+
   ITEM: '[' RHS ']' | ATOM [ '*' | '+' ]
   ATOM: '(' RHS ')' | NAME | STRING
   STRING: '"' any* '"'
   NAME: char (digit | char)*

   [A]   zero or one repetition
   A*    zero or more repetitions
   A+    one or more repetitions
   A|B   A or B
   A B   first A next B
  (A ..) parentheses for separation
   "A"   keyword A


In some sense all the words 'start', 'done', 'ok' etc. are keywords of
the language. If I actually attempted to use the grammar for parsing
it could parse a few sentences like:

'start ok done' or 'start cancel done'

and create parse trees [UNSTARTED, start, [STARTED, ok, [FINSIHED,
done]]] etc.

One can however use the Finite State Machine generated from the
grammar for totally different purposes: interpret each rule as a state
and the keywords as events that cause state transitions.

UNSTARTED -- start --> STARTED
STARTED -- ok --> FINISHED
STARTED -- cancel --> ABANDONED
FINISHED -- done --> .
ABANDONED -- done --> .

That's basically the same formal language with a different, more
intuitive notation.