Experience with a Regular Expression Compiler,

Abstract

The language of regular expressions is a useful one for specifying certain sequential 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1983
Accession Number
ADA135202

Entities

People

  • A. R. Karlin
  • H. W. Trickey
  • J. D. Ullman

Organizations

  • Stanford University

Tags

Communities of Interest

  • Air Platforms
  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Aspect Ratio
  • Automata
  • Automata Theory
  • Circuits
  • Compilers
  • Computer Programming
  • Computer Science
  • Computer-Aided Design
  • Computers
  • Feedback
  • Integrated Circuits
  • Language
  • Sequences
  • Transitions
  • Transmitters

Readers

  • Computational Linguistics
  • Mathematical Modeling and Probability Theory.
  • Systems Analysis and Design