Re: Fast NFA engine anyone?

reeuwijk@few.vu.nl (Kees van Reeuwijk)
23 Apr 2006 10:04:28 -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: reeuwijk@few.vu.nl (Kees van Reeuwijk)
Newsgroups: comp.compilers
Date: 23 Apr 2006 10:04:28 -0400
Organization: Vrije Universiteit Amsterdam
References: 06-04-121 06-04-129
Keywords: lex
Posted-Date: 23 Apr 2006 10:04:28 EDT

Remo D. <rd3ntat0@hotmail.com> wrote:


> I think Laurikari's master thesis "Efficient submatch addressing for
> regular expression" (http://citeseer.ist.psu.edu/480392.html) gives a
> good summary of this point of view. He's also author of the TRE matching
> ilbrary (http://laurikari.net/tre/).


(snip)


> [Oh, you want backrefs. Yes, NFAs are the way to go. -John]


Actually, what Laurikari describes is a generalization of the standard
NFA->DFA algorithm that DOES allow tagging of positions in the regular
expression. In other words, his algorithm allows you to construct an
automaton that always looks at most once at each input character, and
that records relevant positions in the matched expressions. As far as I
can tell, his algorithm is exactly what you are looking for.

Post a followup to this message

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