in reply to left-non-greedy regex?

You're really not going to find that in a single regex, unless you also include code-blocks as part of your solution, in which case you're back into the realm of full Turing-completeness where it can always be done.

And I don't call it "right non greedy". I think that's where you start thinking that "left non greedy" can exist. I call it "minimal repetitions", which means it doesn't need to really maintain state -- just prefer "match again" over "stop here", or vice versa.

Your hypothetical regex would need a lot of state as it kept searching. It'd also have to search the entire string every time, in a myriad of ways. Can you say slooooooow?

Here's one way you can do it with some extra code: 

my $string = "....";
my $regex = qr/...(...).../; # must have $1 be the thing we're optimiz
+ing to reduce
my @solutions;
while ($string =~ g/(?=$regex)/g) {
  push @solutions, [[@-], [@+]]; # push starts and ends
}
# now walk through the solutions, and pick the one with the minimal sp
+an on $1
# [ code unfinished ]

[download]

-- Randal L. Schwartz, Perl hacker
Be sure to read my standard disclaimer if this is a reply.

Replies are listed 'Best First'.
Re: •Re: left-non-greedy regex?
by zby (Vicar) on Mar 26, 2003 at 09:51 UTC
    How about doing the same thing as the existing minimal match - just starting from the other side. Of course you can do that by reversing the search string and than doing the existing minimal match.

    Update: This was the conclusion of the MarkM post later here - so I was not the first with this idea.

[reply]
      That'll just find the first match, with a minimal span within that match. That's still not going to find the shortest of all possible matches.

      In other words, it won't find the middle "b" in "abbababba", if you're looking for the "shortest run of b's" as in the other node.

      -- Randal L. Schwartz, Perl hacker
      Be sure to read my standard disclaimer if this is a reply.

[reply]
        In his post he proposed two hipothetical maching construct - my answer was concerning the first what he called 'left non greedy', you talk rather about the 'both left and right non greedy'.
[reply]

In Section Seekers of Perl Wisdom