Re: Fast NFA engine anyone?

"Russ Cox" <rsc@swtch.com>
22 Apr 2006 03:10:24 -0400

          From comp.compilers
Related articles
Fast NFA engine anyone? rd3ntat0@hotmail.com (Remo D.) (2006-04-21)
Re: Fast NFA engine anyone? rsc@swtch.com (Russ Cox) (2006-04-22)
Re: Fast NFA engine anyone? rd3ntat0@hotmail.com (Remo D.) (2006-04-22)
Re: Fast NFA engine anyone? cfc@shell01.TheWorld.com (Chris F Clark) (2006-04-23)
Re: Fast NFA engine anyone? reeuwijk@few.vu.nl (2006-04-23)
Re: Fast NFA engine anyone? Danny.Dube@ift.ulaval.ca (2006-05-11)
Re: Fast NFA engine anyone? rd3ntat0@hotmail.com (Remo D.) (2006-05-12)
| List of all articles for this month |
From: "Russ Cox" <rsc@swtch.com>
Newsgroups: comp.compilers
Date: 22 Apr 2006 03:10:24 -0400
Organization: Compilers Central
References: 06-04-121
Keywords: lex, available
Posted-Date: 22 Apr 2006 03:10:24 EDT

> Consider that I would even sacrifice some of the expressiveness of
> regexp. I already dropped the operator | without any impact on the final
> application.


Since all your patterns are anchored, it's trivial to figure out where
the DFA entered a matching state, as John pointed out. Also, there
is no need to drop the | operator.


I posted a simple, fast DFA-based regular expression engine at
http://swtch.com/~rsc/dfagrep.tgz. The NFA code is about 1000
lines (includes parsing regular expressions), and the DFA code,
which builds the DFA on-demand while running it, is only about 250 lines.


There is a program filegrep.c that does essentially what you were
asking - read a list of regexps from one file and then match them
against lines from a second.


Russ

Post a followup to this message

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