Two-way Stack Automata and Compiling


Dick Grune

Finite-state automata and pushdown automata provide the theoretical foundation for lexical and syntax analysis in a compiler, but there is no obvious automaton for semantic analysis and context checking.

In 1967, Ginsburg, Greibach, and Harrison proposed the 2-way stack automaton as a suitable candidate, and it seemed interesting to have another good look at it. The report presented here does exactly that. It provides a description of the automaton, several techniques of programming it, a simple programming language for it embedded in C (implemented by 4 macros and 1 type definition!), and various small programs, among which a program for sorting strings of arbitrary length, and one for computing the calling graph of a program.

The conclusion is that the 2-way stack automaton is an interesting toy but clumsy device. It is certainly possible to program it, but it feels like building a model of the Notre Dame from match sticks. It is plausible that it could be used for compiler writing, but it would take an inordinate amount of work. It is nowhere near having the same close relationship to semantics as the pushdown automaton has to syntax; but then, no other automaton has. Attribute grammars are far more suitable for semantics and context checking, but they do not come with an automaton.

The sources are available, and contain three runnable progams, and various other info.

Have fun!


[Home Page]
Two-way Stack Automata and Compiling / Dick Grune / dick@dickgrune.com

... and my name is not Richard ...