Re: Leftmost longest match with DFA search

Daniel Villeneuve <daniel2villeneuve@videotron.ca>
Sun, 11 May 2008 11:42:22 -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: Daniel Villeneuve <daniel2villeneuve@videotron.ca>
Newsgroups: comp.compilers
Date: Sun, 11 May 2008 11:42:22 -0400
Organization: Compilers Central
References: 08-05-026
Keywords: lex, DFA
Posted-Date: 11 May 2008 23:28:35 EDT

Stefan Monnier wrote:
> 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.
[snip]
> Stefan


I've used the approach to compile a DFA for the reverse RE, say ER, and
first match .*ER on the reverse text to find the leftmost anchor point.
    Then match RE from that point to find the longest span.
--
Daniel Villeneuve
Kronos


Post a followup to this message

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