Finite State Machines in COBOL

Finite State Machines (FSMs)

Synonym: Finite state automaton.

Overview

A finite state machine, or FSM, responds to events by jumping from state to state according to a formal set of rules, which are customized for the problem at hand.

FSMs are often used in real-time systems to control devices such as toaster ovens, elevators, and nuclear power plants. More importantly for JOCKEY, however, FSMs are also widely used to parse text according to the rules of a formal grammar.

Turing machines (a theoretical concept) are a generalization of finite state machines. FSMs are not quite as powerful as Turing machines (partly because they don't have infinite memory). But they're pretty close. They're especially useful for solving complex problems for which conventional techniques tie themselves in knots.

FSMs reflect a rather formal, abstract approach which may seem a bit alien to a programmer in the trenches. Once you catch on, however, you find that FSMs are not only powerful, but also easy to code (at least in simple but still useful cases).

Description

There are many variants of the FSM approach. These pages will describe only the basic principles suitable for hand-coding small FSMs. Larger FSMs may require a more formal and disciplined approach, and perhaps specialized tools.

In particular, we will discuss deterministic FSMs. Non-deterministic FSMs are more concise, but they are harder to translate into code.

An FSM consists of three components:

A set of states. At any given time the machine is in a single state.

A set of events which the machine recognizes. Typically an event represents some kind of external input, but the FSM may also generate events internally. For lexical analysis, most events correspond to an input character.

A mapping from each state-event pair to a corresponding action. An action may be empty; it may include a transition to another state; it may include anything else which the application needs.

One of the states is the initial state. If the FSM is not to fall into an infinite loop, there must also be at least one terminating state. For lexical analysis, there will typically be two kinds of terminating states. One kind represents the recognition of a token, and the other represents a syntax error in the input text.

Transition Diagrams

The simplest way to design an FSM is to draw a picture of it in the form of a transition diagram. Represent each state with a numbered circle. Draw arrows from circle to circle to represent the possible state transitions. Label each arrow with the events which cause the associated state transition.

The diagram may also reflect actions other than state transitions. One approach is to label the arrows not only with events but also with actions, at least in an abbreviated form.

When you're working out the design, doing a lot of scribbling, you needn't be finicky about the notation. Leave things out to save time, or invent your own peculiar notation. As your design approaches completion, a more formal approach helps you make sure that you haven't missed anything.

Debugging the Diagram

Make sure that:

There is an initial state, with no arrows leading into it.
There is at least one terminal state, with no arrows leading out of it.
Your events include blanks, end-of-line (or end-of-file, or end-of-data, or something), and an "other" category for unexpected characters.
You have accounted for all the possible error conditions. You may omit them from the diagram to avoid clutter, but don't forget them.
Each state has exactly one transition for each possible event, even if the transition is back to the same state.
There are no infinite loops. It is okay for the arrows to form loops, but make sure that all loops will eventually terminate. As long as a loop continues to read characters, it will eventually reach the end, so most diagrams satify this condition without much effort.
Each transition makes sense.

Example

Suppose our parser needs to recognize a COBOL data name. A data name contains some combination of letters, digits, and hyphens, but it may not begin or end with a hyphen.

The following transition diagram fits the bill. The initial state is labelled '0'.

[FSM example 1]
This diagram does not reflect the fact that a data name can be no longer than 30 characters. We can apply this limit outside the FSM itself, after collecting all the characters.

Another approach is to devise a larger FSM which checks the length after each character:

[FSM example 2]
This diagram uses a slightly different notation: the initial state is a solid dot instead of a circle. Furthermore the initial state does not read any characters; it leads directly to another state. This change eliminates some duplicated transitions.

The colored states, numbered 3, 4, 5, and 7, do not read characters either. They simply check the length of the character string. The resulting events, reflecting whether the string is too long, are internally generated.

Other Examples

For real-world examples, examine the transition diagrams for parsing ZIP codes and telephone numbers. These FSMs are simple enough to serve as good illustrations, but not complex enough to show the power of FSMs. One might readily have parsed these elements using more conventional techniques.

While there are more complex examples in my own programs, they are highly specific to the JOCKEY application. It would be awkward to explain them to a general audience, and no one would have the patience to read the explanation anyway.

Implementing an FSM

The transition diagram is the fun, creative part of designing an FSM. Once you finish the diagram, the rest is mostly mechanical. Dangerously mechanical. Once you decide on a general coding approach, the actual coding is so tedious that you will probably make mistakes. These mistakes may be perfectly sound COBOL; neither your compiler nor your eyeballs will spot them. Check and double-check your code to make sure it corresponds to the diagram.

Then test and re-test. If you isolate your FSM in a subprogram (hint, hint) you can write a test driver for it, and subject it to test cases that would be hard to find in real data.

At the coding level there are three broad kinds of FSMs:

Table-based FSMs;

Code-based FSMs;

Automated FSMs.

The first two may be combined into a hybrid, when convenient. The third kind is now available for COBOL through a tool called Libero, from iMatix. Libero runs under Unix, MS-DOS, Windows, OS/2, and VMS. An MVS version is not yet available.

The Dark Side of FSMs

A simple FSM is easy to write. In fact it's kind of fun. But what about the poor guy that has to maintain it?

In the first place, most COBOL programmers know nothing about FSMs, and will find the whole thing completely baffling. Comments in the code should explain what is going on, at least briefly. They might contain a reference to this Web page or to other reference material.

In the second place, even for someone who understands FSMs, COBOL is not a very lucid way to represent one. To understand how the program works, you first have to figure out how it implements the FSM; then you have to painstakingly reconstruct the transition diagram. Only then can you even start looking for a way to fix a bug or otherwise change the program's behavior.

In the absence of automated tools, one solution to this problem is to include the transition diagram as part of the documentation. This solution requires that your documentation be based either on paper (where even a crude hand-drawn diagram would be welcome) or on some storage medium that supports graphics (such as Web pages).

A better solution -- when it works -- is to make maintenance unnecessary. Isolate each FSM (or perhaps a collection of related FSMs) in a subroutine that does nothing but implement the FSM. Make sure it works. With any luck, no one will ever have to look at it again.

Parsing techniques [books]