Report Number: CS-TR-67-57
Institution: Stanford University, Department of Computer Science
Title: The use of transition matrices in compiling
Author: Gries, David
Date: March 1967
Abstract: The construction of efficient parsing algorithms for
programming languages has been the subject of many papers in
the last few years. Techniques for efficient parsing and
algorithms which generate the parser from a grammar or phrase
structure system have been derived. Some of the well-known
methods are the precedence techniques of Floyd, and Wirth and
Weber, and the production langauge of Feldman. Perhaps the
first such discussion was by Samelson and Bauer. There the
concept of the push-down stack was introduced, along with the
idea of a transition matrix. A transition matrix is just a
switching table which lets one determine from the top element
of the stack (denoting a row of the table) and the next
symbol of the program to be processed (represented by a
column of the table) exactly what should be done. Either a
reduction is made in the stack, or the incoming symbol is
pushed onto the stack. Considering its efficiency, the
transition matrix technique does not seem to have achieved
much attention, probably because it was not sufficiently
well-defined. The purpose of this paper is to define the
concept more formally, to illustrate that the technique is
very efficient, and to describe an algorithm which generates
a transition matrix from a suitable grammar. The report also
describes other uses of transition matrices besides the usual
ones of syntax checking and compiling.
http://i.stanford.edu/pub/cstr/reports/cs/tr/67/57/CS-TR-67-57.pdf