On 25 Mai, 01:46, Matthew Wilson <m...@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. -- http://mail.python.org/mailman/listinfo/python-list