Re: Leftmost longest match with DFA search

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

.

Relevant Pages

  • Re: Leftmost longest match with DFA search
    ... leftmost longest match when implementing regexp search using a DFA? ...
    (comp.compilers)
  • Leftmost longest match with DFA search
    ... Can someone point me to articles that discuss various ways to get the ... leftmost longest match when implementing regexp search using a DFA? ...
    (comp.compilers)
  • Re: Leftmost longest match with DFA search
    ... leftmost longest match when implementing regexp search using a DFA? ... first match .*ER on the reverse text to find the leftmost anchor point. ...
    (comp.compilers)
  • Re: Leftmost longest match with DFA search
    ... leftmost longest match when implementing regexp search using a DFA? ... the "obvious" solution is to implement unanchored search ... a set of leftmost-longest non-overlapping matches. ...
    (comp.compilers)
  • Re: Leftmost longest match with DFA search
    ... leftmost longest match when implementing regexp search using a DFA? ... refers to the leftmost of the longest matches while "longest leftmost ... If the set is non-empty, keep only the begin-leftmost matches, ...
    (comp.compilers)