++ed by:
Author image Alexander Becker
and 1 contributors


DFA-Simple-compiler -- A simple automaton compiler with discrete states


This compiles a table of information into a simple automaton. The automaton produced is a Perl module that inherits from DFA::Simple. This is modeled on augmented transition networks (ATN), but is not as sophisticated.

The options include:

--package NAME

This specifies the package name of the compiled automaton.

Description of the simple state machine

A discrete finite automaton is a simple "state" machine that has a limited number of states (or modes). The machine behaves differently depending on which state it is in. The machine usually starts of in an initial state, and may have a special state to "shut it off."

Any time the state is changed, an action may be performed. The next state is determined by performing a number of tests. The first test that passes indicates what the next state should be, and the action that should be performed. The test must be carefully designed to operate correctly; there is built-in method of recovery after transitioning to the wrong state or performing the wrong action. For an automaton that can do this, see ATN section of DFA::Simple.

To define the automaton, you need to create a file that contains your definition. It has three sections, which can be broken down and rearranged to your liking. But first, I need to describe comments. A comment is anything between a # and the end of the line:

   # My comment: hi world!

Production rules

As I mentioned above, there are three sections: flow based transitions, exceptional transitions, and what needs to be done for every transition. If you want to describe some transitions based upon the flow of discourses, you would first start with:


This simply tells the compiler that you will now be defining some production rules. A production rule looks like:


or, think of it as a trip


The production rule is only used if, the Here and Why rules match:

1. The discourse state machine is currently in a state that matches CurrentState
2. The Test passes.

That is it. Test is not simply a pass or fail test. It does report whether or not things pass, but it does something more. Computers process things very quickly when their facts, parameters, etc. are all lined up and properly prepared. And computers can be very fast if they extract this stuff while they are testing patterns. So Test can also grab the minutae if it wants. On the flip side, Test is optional: not specifying a test is the same as specifying at test that always passes.

Assuming the test does pass, the discourse machine sets things for what to do next -- the NextState and the WhatToDo. These aren't hidden in one thing, but are kept separate for very good reasons. They are also optional. The reason is that a more powerful, faster, and (ironically) testable machine can be built if the specific next state is declared separately from the broader WhatToDo declaration. In other words, you will be arranging things a way that compiler clearly (or more clearly than otherwise) understands your goal. But you need a goal to be understood properly!

Exceptional rules

There is second section for rules that do not need any tests. These rules are "rarely" used -- that is, the production rules are used several dozen or several hundred times during normal operation, while the exceptional rules are used once or so.


WhatToDo and <NextState> are the same as mentioned in the previous section. ExceptionName varies -- there are the signals that a program may receive from the operating system:


There is no test, because when the exception is raised, it has been raised. There is no current state test, because the exceptions can happen in any state.

Things to do during a transition


When the state machine is executing a rule, and the next state is different from the current state, the following happens:

1. The stuff for leaving the current state (ToDoWhenLeaving) is done
2. The matching rule is executed
3. The stuff for entering the next state (ToDoWhenEntering) is done.


    perl Makefile.PL
    make install


Randall Maas (randym@acm.org)