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/method/process/stmech2.htm, 6KB, , updated: 2019/1/10 11:40, local time: 2024/6/15 00:46, |

©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?<A HREF="http://www.massmind.org/techref/method/process/stmech2.htm"> Using Finite State Machines </A> |

Did you find what you needed? |

## Welcome to massmind.org! |

## Welcome to www.massmind.org! |

.