Carnegie Mellon University
file.pdf (456.42 kB)
Download file

A delay insensitive regular expression recognizer

Download (456.42 kB)
journal contribution
posted on 2000-09-01, 00:00 authored by T. S. Anantharaman
Abstract: "Several types of synchronous Regular Expression (RE) recognizers have been proposed by several authors. This paper describes a self-timed and delay-independent RE recognizer. The problem is non-trivial because of the [epsilon]-closure operation that is implicitly performed every cycle of the recognition process. The design is based on expression-tree recognizers, and has a self-timed cycle time O(h) where h is the high of the parse tree of the RE. Since it is an expression-tree recognizer it has a compact O(N) layout algorithm, where N is the size of the RE. The design also results in an synchronous RE recognizer with the shortest worst case cycle time O(h) reported for recognizers with area O(N).


Publisher Statement

All Rights Reserved



Usage metrics