Re: Leftmost longest match with DFA search

Stefan Monnier <monnier@iro.umontreal.ca>
Tue, 13 May 2008 05:02:56 -0400

          From comp.compilers

Related articles
Leftmost longest match with DFA search monnier@iro.umontreal.ca (Stefan Monnier) (2008-05-10)
Re: Leftmost longest match with DFA search daniel2villeneuve@videotron.ca (Daniel Villeneuve) (2008-05-11)
Re: Leftmost longest match with DFA search rsc@swtch.com (Russ Cox) (2008-05-12)
Re: Leftmost longest match with DFA search monnier@iro.umontreal.ca (Stefan Monnier) (2008-05-13)
Re: Leftmost longest match with DFA search monnier@iro.umontreal.ca (Stefan Monnier) (2008-05-13)
Re: Leftmost longest match with DFA search Danny.Dube@ift.ulaval.ca (2008-05-13)
Re: Leftmost longest match with DFA search rsc@swtch.com (Russ Cox) (2008-05-14)
Re: Leftmost longest match with DFA search Danny.Dube@ift.remove.ulaval.remove.ca (2008-05-15)
| List of all articles for this month |

From: Stefan Monnier <monnier@iro.umontreal.ca>
Newsgroups: comp.compilers
Date: Tue, 13 May 2008 05:02:56 -0400
Organization: UseNetServer.com
References: 08-05-026 08-05-040
Keywords: lex, DFA
Posted-Date: 14 May 2008 11:55:25 EDT

>> Can someone point me to articles that discuss various ways to get the
>> leftmost longest match when implementing regexp search using a DFA?
>> The "obvious" solution ...


> Actually, the "obvious" solution is to implement unanchored search
> using repeated anchored searches. Running an anchored DFA search and


Yes, that's the method used in Tcl, as mentioned in your article that
I referred to. But it's O(N^2), which is disappointing. The methods
used in TRE or Plan9's regexp lib are O(N), tho using an NFA.


> Tradtionally, when you ask for all matches for a RE in a text, you get
> a set of leftmost-longest non-overlapping matches.


Right. I'm not looking to find all the matches, just the first one.
I'd even be content with the first leftmost match (not necessarily
longest).


In any case, thank you both for proposing to match backwards. It seems
to open up new ways to attack the problem.


In any case, I do know some good-enough solutions, but I'm really
looking for literature about the problem and discussions comparing the
various solutions.




                Stefan


Post a followup to this message

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