From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: comp.programming
Subject: Re: Is a generic finite state machine engine reasonable?
Date: 13 Oct 1992 09:35:23 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
NNTP-Posting-Host: 129.89.7.4

In article <1992Oct12.162439.10014@saifr00.cfsat.honeywell.com> schall@swtech06.cfsat.honeywell.com (Loren Schall) writes:
>Is it possible and reasonable to implement a "generic" finite state
>engine?

You may infer a general code-mapping algorithm that compiles DFA's directly
into code, instead of into an abstract DFA implemented on top of the code
layer, from the pesudo-code example below.

Alphabet: a, b, c, $
Expression: a* (b* c)* b $.

Automaton:

State 0:
   $: error 0
   a -> 0
   b -> 3
   c -> 1
State 1:
   $: error 1
   a: error 2
   b -> 3
   c -> 1
State 2:
   $: error 3
   a: error 4
   b -> 2
   c -> 1
State 3:
   $: accept
   a: error 5
   b -> 2
   c -> 1


Code:
Q0: switch (next) {
       case $: error 0;
       case a: shift; goto Q0;
       case b: shift; goto Q3;
       case c: shift; goto Q1;
    }
Q1: switch (next) {
       case $: error 1;
       case a: error 2;
       case b: shift; goto Q3;
       case c: shift; goto Q1;
    }
Q2: switch (next) {
       case $: error 3;
       case a: error 4;
       case b: shift; goto Q2;
       case c: shift; goto Q1;
    }
Q3: switch (next) {
       case $: return;
       case a: error 5;
       case b: shift; goto Q2;
       case c: shift; goto Q1;
    }

Code adter structure-intruducing and goto-elimination and duplicate-path
elimination:

Q0: while (next == a) shift;
    if (next == $) error 0;
    while (1) {
Q1:    while (next == c) shift;
       if (next == $) error 1;
       if (next == a) error 2;
       shift;
Q3;    if (next == a) error 5;
       if (next == $) break;
Q2:    while (next == b) shift;
       if (next == a) error 4;
       if (next == $) error 3;
    }
    return;

Further optimizations would then result if the error actions 4 and 5, or
actions 0, 1 and 3 were considered identical, for example, to:

Q0: while (next == a) shift;
    while (1) {
Q1:    while (next == c) shift;
       if (next == $) error 0/1/3;
       if (next == a) error 2;
       shift;
Q3;    if (next == $) break;
Q2:    while (next == b) shift;
       if (next == a) error 4/5;
    }
    return;


Essentially, the compilation carries out the following mapping:


Regular Expressions   -  -  -  -  -  -  -  -  - >   Structured Code
       |                                                   ^
       |                                                   |
       |                                                   |
       |                                                   |
       v                                                   |
Finite State Automata ===========================> Goto-Normal Form Code


A theory built around this compilation process will develop tools that will
allow you to go directly from regular expressions (or finite state automata)
to structure code, by-passing the intermediate steps.

Essentially this is part of a method I use to generate parsers and scanners
and other formal-language applications by hand.

It sure beats the excessive layering you see in an interpreted table-driven
automaton, such as lex's automaton.