[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
**Subject**: **Re: lpeg and terminology**
**From**: Roberto Ierusalimschy <roberto@...>
**Date**: Mon, 8 Sep 2008 12:45:53 -0300

> Specifically, what does a phrase like "blind greedy repetition" mean?
> I understand greedy to mean look for a mach until there are no more,
> but blind is a bit of mystery. Any info appreciated.
Unfortunately, the use of the term "greedy" regarding pattern
matching is not very precise with respect with its common use in
algorithms. Usually "greedy" in that context does not mean "until there
are no more", but "as much as possible". (Whether these two definitions
are equivalent depends on your definition of "possible" :) So, the usual
repetition operators '*' and '+' are frequently called greedy.
I used the term "greedy" with the above meaning, of "as much as
possible". "Blind", in that context, changes the meaning of what
it is "possible". It is explained on page 3 of the paper ("A Text
Pattern-Matching Tool..."):
A blind greedy repetition [...] always matches the maximum possible span
(therefore greedy), disregarding what comes afterwards (therefore blind).
[...]
A non-blind greedy repetition is one that repeats as many times as
possible (therefore greedy), as long as the rest of the pattern
matches (therefore non-blind).
-- Roberto