Re: DotStar regex package

Tony Finch <dot@dotat.at>
11 May 2010 17:48:13 +0100 (BST)

          From comp.compilers

Related articles
DotStar regex package johnl@iecc.com (John R. Levine) (2010-05-11)
Re: DotStar regex package dot@dotat.at (Tony Finch) (2010-05-11)
Re: DotStar regex package cfc@shell01.TheWorld.com (Chris F Clark) (2010-05-11)
Re: DotStar regex package cfc@shell01.TheWorld.com (Chris F Clark) (2010-05-11)
Re: DotStar regex package kym@sdf.lonestar.org (russell kym horsell) (2010-05-12)
Re: DotStar regex package cfc@shell01.TheWorld.com (Chris F Clark) (2010-05-12)
| List of all articles for this month |

From: Tony Finch <dot@dotat.at>
Newsgroups: comp.compilers
Date: 11 May 2010 17:48:13 +0100 (BST)
Organization: dotat labs
References: 10-05-054
Keywords: lex
Posted-Date: 12 May 2010 00:56:34 EDT

"John R. Levine" <johnl@iecc.com> wrote:
>
>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. It turns regular
>expressions into NFAs and then DFAs, but does so in a way that they
>say runs much faster than other packages on modern CPUs. They also
>say they deal with the state explosions that NFA->DFA translations can
>cause.
>
>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 haven't read the article yet, but from your description it sounds
like their work is similar to Russ Cox's:


http://swtch.com/~rsc/regexp/


His re2 library is available as open source via that link.


Tony.
--
f.anthony.n.finch <dot@dotat.at> http://dotat.at/


Post a followup to this message

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