Report Number: CS-TR-83-972
Institution: Stanford University, Department of Computer Science
Title: Experience with a regular expression compiler
Author: Karlin, Anna R.
Author: Trickey, Howard W.
Author: Ullman, Jeffrey D.
Date: June 1983
Abstract: The language of regular expressions is a useful one for specifying certain sequebtial processes at a very high level. They allow easy modification of designs for circuits, like controllers, that are described by patterns of events they must recognize and the responses they must make to those patterns. This paper discusses the compilation of such expressions into reasonably compact layouts. The translation of regular expressions into nondeterministic automata by two different methods is discussed, along with the advantages of each method. A major part of the compilation problem is selection of good state codes for the nondeterministic automata; one successful strategy is explained in the paper.
http://i.stanford.edu/pub/cstr/reports/cs/tr/83/972/CS-TR-83-972.pdf