Re: Leftmost longest match with DFA search

Stefan Monnier <monnier@iro.umontreal.ca> writes:


[snip]
> >> 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.
>
> Interesting. But doesn't it basically force you to scan the complete text?
> That can be impractical.


You don't (always) need to scan the complete text. You can perform
that reversed search on increasingly longer prefixes of the text. If
you increase the lengths of the prefixes by a constant factor, you
work for a time in O(K) to find a leftmost match when the latter
completely lies in the first K characters.


Danny

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