Re: 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?
>> 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

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