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.