> -----Original Message----- > From: [EMAIL PROTECTED] > [mailto:[EMAIL PROTECTED] On Behalf Of liorean > Sent: 18. februar 2008 22:18 > To: [email protected] > Subject: Re: Greedy triple-quoted string literals > > > > That is what Comen, Leiserson, and Rivest[*] call greedy in their > > discussion of greedy algorithms: "A //greedy algorithm// always makes > > the choice that looks best at the moment. That is, it makes a locally > > optimal choice in the hope that this choice will lead to a globally > > optimal solution." > > > > Knuth does not include the term in his index, sadly, nor do any of my > > other algorithm books. Can somebody dig up a conflicting definition
> > so that we can get a real discussion going? > > When discussing "greedy" and "lazy" in terms of quantifierrs > in regex, the usual way to talk about them is that out of > multiple valid matches, "greedy" choses the match containing > as many repetitions as possible, and "lazy" choses the match > containing as few repetitions as possible. I don't know of a > text that has a more formal definition than that, really, nor > do I know of any definition of greedy/lazy algorithms as > opposed to greedy/lazy quantifiers in regex or grammars. > I've got no formal CS education though, so I've not read that > much of the literature... Good point! Using triple-quoted strings themselves as the example, the "greedy" regex """.*"""(?!") allows only one triple-quoted string per file, whereas the "non-greedy" regex """.*?"""(?!") is actually the correct one (modulo newlines and escape sequences.) Neither is deterministic, though; something like """(?:(?!"""(?!")).)*""" is probably more like it (haven't tested). Note that that would be a greedy regex (greedy in the regex sense) implementing a greedy algorithm (greedy in the algorithm sense). --lars _______________________________________________ Es4-discuss mailing list [email protected] https://mail.mozilla.org/listinfo/es4-discuss
