Re: The shortest possible sequence match with Lua regular expressions

[Javier Guerra <javier@...>]

On Fri, Oct 30, 2009 at 3:43 PM, Joshua Jensen
<jjensen@workspacewhiz.com> wrote:
> I ran into this today, and while I tried to explain it away, I have to admit
> I am mildly confused.
>
> Why does the following match the entire string "/dev/myprog/image/xyz/"?
>
> =string.match('/dev/myprog/image/xyz/', '(/.-/)$)
>
> The documentation states that a - (minus) matches the shortest possible
> sequence.
>
> I hadn't given this any thought until today, as I normally would have
> written '.+(/.-/)$'.  That would have yielded the correct result of '/xyz/'.
>   When discussing it with a coworker, though, he raised the point that with
> the final / (slash) anchored at the end of the string, the shortest possible
> matching sequence should be '/xyz/'.
>
> I can buy into that argument.  What are we missing?

i haven't looked at the code; so i guess that backtracking (to 'move'
the first slash of the pattern to another slash of the target string)
happens only when there's no possible match.  if it always tried
backtracking just to see if there's a shorter match, you'd quickly get
exponential time for almost any pattern.


-- 
Javier