Greedy triple-quoted string literals

Lars Hansen lhansen at adobe.com
Tue Feb 19 02:16:58 PST 2008


> -----Original Message-----
> From: es4-discuss-bounces at mozilla.org 
> [mailto:es4-discuss-bounces at mozilla.org] On Behalf Of liorean
> Sent: 18. februar 2008 22:18
> To: es4-discuss at mozilla.org
> 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



More information about the Es4-discuss mailing list