file.pdf (456.42 kB)
A delay insensitive regular expression recognizer
journal contributionposted 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 StatementAll Rights Reserved