Re: DotStar regex package

Chris F Clark <>
Tue, 11 May 2010 13:44:20 -0400

          From comp.compilers

Related articles
DotStar regex package (John R. Levine) (2010-05-11)
Re: DotStar regex package (Tony Finch) (2010-05-11)
Re: DotStar regex package (Chris F Clark) (2010-05-11)
Re: DotStar regex package (Chris F Clark) (2010-05-11)
Re: DotStar regex package (russell kym horsell) (2010-05-12)
Re: DotStar regex package (Chris F Clark) (2010-05-12)
| List of all articles for this month |

From: Chris F Clark <>
Newsgroups: comp.compilers
Date: Tue, 11 May 2010 13:44:20 -0400
Organization: The World Public Access UNIX, Brookline, MA
References: 10-05-054
Keywords: lex, performance
Posted-Date: 12 May 2010 00:57:21 EDT

"John R. Levine" <> writes:

> The March issue of IEEE Computer has an article called "Tools for Very
> Fast Regular Expression Matching" which describes a regex package
> called DotStar, written by three guys at IBM.
> I don't know enough about the nitty-gritty of current DFA pattern matchers
> to know if this really is a signficant improvement. Anyone else have
> opinions?

I've read the article and although a few details are a little
fragmentary, the work is sound and is part of a new trend in trying to
develop better (i.e. faster) regular expression processors. Similar
results can be seen in the work of Michella Becchi, who worked with
Patrick Crowley at Washington University (and interned with me here at
Intel). The underlying trick is converting the NFA into a DFA (and
the obvious generalization of the Aho-Corasik algorithm is a good way
to do this) except where doing so causes a state explosion and using
"other techniques" for dealing with the transitions that would cause
the explosion.

Hope this helps,

Chris Clark email:
Compiler Resources, Inc. Web Site:
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.