Algorithms for the compilation of regular expressions into PLAs

DOI10.1007/BF01840364MaRDI QIDQ1098299zbMATH OpenFDO

Authors Anna R. Karlin, Howard W. Trickey, Jeffrey D. Ullman

Publication date 1987

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01840364

zbMATH Keywords

language of regular expressionsmicrocode compactionnondeterministic finite automatonsequential processessilicon compilationspecifications for programmable logic arrays

Mathematics Subject Classification ID

Theory of operating systems (68N25) Formal languages and automata (68Q45)

Review text

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 specifications for programmable logic arrays (PLAs) that will implement the required function. A regular expression is converted into a nondeterministic finite automaton, and then the automaton states are encoded as values on wires that are inputs and outputs of a PLA. 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 and its application to microcode compaction is explained in the paper.

Recommendations

• From regular expressions to deterministic automata
• From regular expressions to DFA's using compressed NFA's
• Regular-expression derivatives re-examined
• scientific article; zbMATH DE number 1472276
• A note on optimal parallel transformations of regular expressions to nondeterministic finite automata

Cites work

• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3352742 (Why is no real title available?)
• Microprogram Optimization: A Survey
• The Compilation of Regular Expressions into Integrated Circuits

Cited in

(4)

• scientific article; zbMATH DE number 4045203 (Why is no real title available?)
• scientific article; zbMATH DE number 2102759 (Why is no real title available?)
• Compiling regular patterns
• Embedding finite automata within regular expressions

Describes a project that uses

Uses Software

• ESPRESSO

This page was built for publication: Algorithms for the compilation of regular expressions into PLAs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1098299)