[Top] [All Lists]

Re: variables draft (draft-homme-sieve-variables-00.txt)

2003-04-09 03:33:56

Kjetil Torgrim Homme writes:
[Tim Showalter]:

I implemented a mostly-linear time glob algorithm by implementing minimal matching left-to-right. I am opposed to any semantic that would result in pattern matching being fairly expensive (specifically, any algorithm that results in * being recursive is bad).

If I had done minimal-matching right-to-left, would the result have been greedy? (This would resolve my objection.)


No. Consider the match for a*a in ababa: A minimal match takes aba no matter whether it's right-to-left or left-to-right, a greedy one takes ababa.


<Prev in Thread] Current Thread [Next in Thread>