Using Finite State Machines

BYTE magazine Oct 1979

David E Cortesi, 2340 Tasso St, Palo Alto CA 94301

I was pleased to see a good introductory article on the use of finite state machines appear in BYTE (see "Designing a Command Language" by G A Van den Bout, BYTE, June 1979, page 176). I have found the finite state machine (or finite state automaton, or just FSA) to be a valuable tool in my programmer's toolkit. The finite state machine is an aid to organizing one's thoughts while designing, a good way of producing a really unam- biguous specification document, and as an implemented program it can yield very efficient and reliable code. The finite state machine has long been a plaything of the theoreticians of computer science; you can find it described and analyzed in any textbook on compiler design (it is a good textbook if you can understand the description!). Unfortunately the finite state machine rarely moves out of the textbook and into practical programs. I would like to extend Van den Bout's article with 2 examples from my own experience as a professional programmer that show how the finite state machine solved difficult programming problems in the real world. The first case arose during the design of a timesharing system that was to have a large number of commands. The syntax of the command language was laid down ear- ly in the project, but the specification of the commands themselves kept changing. If I and my colleagues had tried to write detailed code to parse each of the many commands and operands, especially in the face of chang- ing specifications, we would have been swamped. We had to do something to systematize the command-parsing code. We hit on the idea of using finite state machines represented as directed graphs (like the figures in the previous BYTE article). Since we were using a macro-assembler, we created NODE and ARC macroinstructions so that we could "draw" the graph of a command by writing a series of macro calls. Listing 1 shows how some of the chess game commands in the prior article might look in such a macrolanguage. Each macroinstruction assembled to a small group of constants. We thought of these groups as the machine language of an imaginary finite state computer. We then wrote a finite state interpreter which could process these machine instructions. This interpreter program took as its input: (1) the top node of a graph; (2) the tokenized command line from the user; and (3) a small working storage area where semantic routines could leave their Listing 1: A graph representation of a finite state machine as it might look drawn with a macroassembler. The macroinstructions would assemble to machine language for a hypothetical finite state computer; that in turn would be simulated by an interpreter.

```Sl	ANODE		; TOP NODE, ARCS SELECT VERB-TOKENS
ARC TOKEN=KWD.VALUE='MOVE',NEXT=S2M
ARC TOKEN=KWD.VALUE='CAP',NEXT=S2C
ARC TOKEN=KWD.VALUE='TAKE',NEXT-Sll
ZNODE 'MOVE, CAP, OR TAKE?'
S2M 	ANODE VERB=1	; SET VERB-CODE OF MOVE
ARC TOKEN=ANY,NEXT=S2
S2C	ANODE VERB=E	; SET VER3-CODE OF CAP
; COMMON GRAPH F0R MOVE AND CAP
S2 	ANODE
ARC TOKEN=KWD,VALUE='FROM',NEXT=S3
ARC TOKEN=KWD,VALUE='TO',NEXT=58
ZNODE '?? PLEASE SAY TO OR FROM'
; GRAPH OF 'FROM XX TO YY' PART
S3	ANODE
ARC TOKEN=POS,SEMACT=FRPOS,NEXT=S4
ZNODE 'A POSITION MUST FOLLOW FROM'
S4	ANODE
ARC TOKEN=KWD.VALUE='TO',NEXT=S5
ZNODE 'FROM XX -- EXPECTING TO'
S5	ANODE
ARC TOKEN=POS,SEMACT=TOPOS,NEXT=S6
ZNODE 'A POSITION MUST FOLLOW TO'
; GRAPH OF 'TO XX FROM YY' VARIANT
S8	ANODE ARC TOKEN=POS,SEMACT=TOPOS,NEXT=S9
ZNODE 'A POSITION MUST FOLLOW TO'
S9	ANODE ARC TOKEN=KWD.VALUE='FROM',NEXT=Sl0
ZNODE 'TO XX -- EXPECTING FROM'
S10	ANODE ARC TOKEN=POS,SEMACT=FRPOS,NEXT=S6
ZNODE 'A POSITION MUST FOLLOW FROM'
; END-CHECK FOR MOVE AND CAP
ARC TOKEN=END 	; OMITTED tlEXT- MEANS 'ALL DONE'
ZNODE 'EXTRA OPERAND'
Sll	ANODE VERB=3	; SET VERB-CODE OF TAKE
... etc, etc, etc.
```

Table 1: A finite state machine for processing numeric constants, represented as an array. Each row is a state of the machine; a column is selected by the next input token. At the intersection is the row number for the next step, and the name of an action to be done.

```A0: do nothing
Al: note negitive
A2: collect intrger digit
A3: note rational
A4: note exponential
A5: collect fraction digit
A6: note negitive exponent
A7: collect exponent digit

El: number(?) is <E>..
E2: number is null
E3: <sign><sign>...
E4: <sign><E>..
E5: <sign><end>
E6: 0..<sign>..
E7: <digit>..<sign>..
E8: ..<decimal><sign>..
E9: ..<decimal><decimal>..
E10: ..<E><decimal>..
Ell: ..<E><E>..
E12: ..<e><end>
E13: ..<E><sign><sign>..

Zl: exit, value is zero
ZZ: exit, value is integral
Z3: exit for rational
Z4: exit for exponential

row
Input token
"+"
"-"
"0"
"1...9"
"."
"E"
<end>
1
2/A0
2/A1
3/A0
4/A2
5/A3
0/E1
0/E2
2
0/E3
0/E3
3/A0
4/A2
5/A3
0/E4
0/E5
3
0/E6
0/E6
3/A0
4/A2
5/A3
6/A4
0/Z1
4
0/E7
0/E7
4/A2
4/A2
5/A3
6/A4
0/Z2
5
0/E8
0/E8
5/A5
5/A5
0/E9
6/A4
0/Z3
6
7/A0
7/A6
7/A0
7/A7
0/E10
0/E11
0/E12
7
0/E13
0/E13
7/A7
7/A7
0/E10
0/E11
0/Z4

```

 file: /Techref/language/meta-l/stmech2.htm, 6KB, , updated: 1999/2/20 11:29, local time: 2024/5/28 06:45, TOP NEW HELP FIND:  34.239.158.223:LOG IN

 ©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?Please DO link to this page! Digg it! / MAKE! Using Finite State Machines

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type a nice message (short messages are blocked as spam) in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.

Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
 Did you find what you needed? "No. I'm looking for: " "No. Take me to the search page." "No. Take me to the top so I can drill down by catagory" "No. I'm willing to pay for help, please refer me to a qualified consultant"

.