Leftmost longest match with DFA search

Stefan Monnier <monnier@iro.umontreal.ca>
Sat, 10 May 2008 04:36:57 -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)
[1 later articles]
| List of all articles for this month |
From: Stefan Monnier <monnier@iro.umontreal.ca>
Newsgroups: comp.compilers
Date: Sat, 10 May 2008 04:36:57 -0400
Organization: UseNetServer.com
Keywords: lex, question, DFA
Posted-Date: 10 May 2008 21:46:53 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 of turning the problem "search for RE" into the
problem "match .*RE" (where I use "match" here to mean "anchored
search") only gives you the leftmost shortest match.


I've already seen http://compilers.iecc.com/comparch/article/07-10-026
where Tcl's approach to the problem is described, which is sadly O(N^2).


I'm also interested in similar approaches using non-backtracking NFAs
(I'm familiar for example with the algorithm used in Plan9's regexp
library).


                Stefan

Post a followup to this message

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