Non-greedy substitution

[Bod]

I thought I was OK with basic regular expressions, but the behaviour of this has bamboozled me...

Can you please explain what I am doing wrong?

perl -e "my $test = join ', ', ('A', 'B', 'C');$test =~ s/,(.+?)$/ and
+$1/; print $test;"

The result I want is for the list to have a comma separating each item except the last two items which will be separated by 'and'. So the results should be along these lines:
A -> A
A, B -> A and B
A, B, C -> A, B and C

However, the result of the one liner above is A and B, C

I expected ,(.+?)$ to match a comma followed by the shortest possible text and the end of the string. I expected (.+?) to match ' C' as that is the shortest possible match and ? is used to make the match non-greedy

[choroba]

The frugal quantifier means shortest, but still leftmost. You can use a greedy .* at the beginning to consume as much as it can, keep it, and then replace the comma with "and".

#!/usr/bin/perl
use warnings;
use strict;
use experimental qw( signatures );

sub non_oxford_list($s) {
    $s =~ s/^.*\K,/ and/r
}

use Test::More tests => 3;

is non_oxford_list('A'), 'A';
is non_oxford_list('A, B'), 'A and B';
is non_oxford_list('A, B, C'), 'A, B and C';

[Bod]

The frugal quantifier means shortest, but still leftmost

Thank you...it was the "leftmost" that was missing from my thought process!

I think I've understood now 👍

[LanX]

> I think I've understood now 👍

maybe this helps, you can reproduce it in the debugger started with perl -de0

  DB<22> p $_ = join "," , A..E
A,B,C,D,E
  DB<23> p m/(,.*,)/  # longest possibility from first comma to last c
+omma
,B,C,D,
  DB<24> p m/(,.*?,)/ # shortest possibility from first comma to next 
+comma
,B,
  DB<25> p m/(,.*$)/  # longest possibility from first comma to end of
+ line
,B,C,D,E
  DB<26> p m/(,.*?$)/ # shortest possibility from first comma to end o
+f line
,B,C,D,E
  DB<27>

the regex-engine tries to find a solution step by step:

• first it tries the first pattern, here "," = comma
• then it matches "." = all as many times like quantified ( "*" or "*?" )
• till it matches the next pattern ( "," or "$" = EOL )
• IFF not all criteria can be met, it'll try to start anew from the next comma, and so on
The problem with your regex was, that it was already matching from the leftmost comma.

But all solutions provided by other monks made sure that only the rightmost comma allowed to be a match.

For instance

  DB<27> p m/(,[^,]*)$/ # comma followed by non-commas till EOL
,E

The engine will actually try to first match all other commas to the left but always fail because it encounters other commas before reaching the EOL.

we can actually make the regex display it's intermediate attempts to match while "backtracking"

  DB<32> ; m/(,[^,]*) (?{say $1}) $/x #show all intermediate attempts 
+to match $1 until it doesn't fail
,B
,
,C
,
,D
,
,E
  DB<33>

The difference with non-greedy quantifier *? matching is that the engine goes from shortest to longest attempts while backtracking

  DB<34> ; m/(,[^,]*?) (?{say $1}) $/x #show all intermediate attempts
+ to match $1
,
,B
,
,C
,
,D
,
,E

  DB<35>

Is this clearer now? :)

HTH!

[Bod]

Am I right the \K is Keeping everything upto that point and not substituting that part?
It is everything to the left and not just the 'thing' immediately before /K?

[Corion]

If you're interested in seeing how the Regex engine steps through a string, you can load Regexp::Debugger. Alternatively, the first edition of Mastering Regular Expressions explains in-depth how Perls RE engine matches and compares that to other engines.

[tybalt89]

Just because I've never seen 'reductions' used before :)

#!/usr/bin/perl

use strict; # https://perlmonks.org/?node_id=11162727
use warnings;
use List::Util qw( reductions );
use Data::Dump 'dd';

dd map s/.*\K,/ and/r, reductions { "$a, $b" } 'A'..'Z';

Outputs:

(
  "A",
  "A and B",
  "A, B and C",
  "A, B, C and D",
  "A, B, C, D and E",
  "A, B, C, D, E and F",
  "A, B, C, D, E, F and G",
  "A, B, C, D, E, F, G and H",
  "A, B, C, D, E, F, G, H and I",
  "A, B, C, D, E, F, G, H, I and J",
  "A, B, C, D, E, F, G, H, I, J and K",
  "A, B, C, D, E, F, G, H, I, J, K and L",
  "A, B, C, D, E, F, G, H, I, J, K, L and M",
  "A, B, C, D, E, F, G, H, I, J, K, L, M and N",
  "A, B, C, D, E, F, G, H, I, J, K, L, M, N and O",
  "A, B, C, D, E, F, G, H, I, J, K, L, M, N, O and P",
  "A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P and Q",
  "A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q and R",
  "A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R and S",
  "A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S and T",
  "A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T and U",
  "A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U and V
+",
  "A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V an
+d W",
  "A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W
+ and X",
  "A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W
+, X and Y",
  "A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W
+, X, Y and Z",
)

[ikegami]

«,» matches a comma, then «.+?» matches the least possible, then it matches the end of the string or a LF at the end of the string.

01234567 position
A, B, C

Full:

1. Start matching at position 0.
   1. At position 0, «,» doesn't match. ⇒ Backtrack.
2. Start matching at position 1.
   1. At position 1, «,» matches 1 character.
      1. At position 2, «.+?» matches 1 characters.
         1. At position 3, «$» doesn't match. ⇒ Backtrack.
      2. At position 2, «.+?» matches 2 characters.
         1. At position 4, «$» doesn't match. ⇒ Backtrack.
      3. At position 2, «.+?» matches 3 characters.
         1. At position 5, «$» doesn't match. ⇒ Backtrack.
      4. At position 2, «.+?» matches 4 characters.
         1. At position 6, «$» doesn't match. ⇒ Backtrack.
      5. At position 2, «.+?» matches 5 characters.
         1. At position 7, «$» matches 0 characters. ⇒ Success.

Summary:

1. Starts matching at position 1.
2. At position 1, «,» matches 1 character.
3. At position 2, «.+?» matches 5 characters.
4. At position 7, «$» matches 0 characters.

If «.+?» were to match any less, the «$» wouldn't match.

Solution:

sub join_list {
   return "none" if !@_;  # ???
   my $last = pop;
   return $last if !@_;
   return join( ", ", @_ ) . " and " . $last;
}

[Bod]

Solution:

sub join_list {
   return "none" if !@_;  # ???
   my $last = pop;
   return $last if !@_;
   return join( ", ", @_ ) . " and " . $last;
}

An interesting solution.

However, in my quest to understand what is going on, I tried forcing the match to be non-comma characters and came up with this which produces the desired behaviour.

perl -e "my $test = join ', ', ('A', 'B', 'C');$test =~ s/,([^,]+?)$/ 
+and$1/; print $test;"

I still don't understand why the original doesn't work. Surely ,.+?$ is the shortest possible match within the string that starts with a comma and ends at the end of the line...

[ikegami]

Your mental model of what «.+?» does is severely flawed. For starters, it doesn't permit patterns to have multiple subpatterns that can match substrings of different lengths.

«.+?» does not mean "the shortest possible match within the string that starts with a comma".

«.+» means "one or more non-LF characters, trying in order of decreasing length", and
«.+?» means "one or more non-LF characters, trying in order of increasing length".

Note that lack of mention of comma. «.+?» doesn't do any checks related to commas. The comma is matched independently.

[Bod]

If .+? were to match any less, $ wouldn't match.

I'm sorry, but I don't understand why .+? doesn't match 2 characters at position 5 - the match has to be tied to the end of the string...doesn't it?

[ikegami]

There can't be gaps in what matches. «.+?» must start matching where «,» left off. I added a "full" trace to my post.

[Paladin]

The regex engine prioritizes "leftmost". So it will always find the left most place the entire regex will match.

[LanX]

And here the classical way to catch the last segment.

Reusing choroba's tests.

#!/usr/bin/perl
use warnings;
use strict;
use experimental qw( signatures );

sub non_oxford_list($s) {
    $s =~ s/,([^,]+)$/ and$1/r
}

use Test::More tests => 3;

is non_oxford_list('A'), 'A';
is non_oxford_list('A, B'), 'A and B';
is non_oxford_list('A, B, C'), 'A, B and C';

[LanX]

> the classical way

There are more than one way to go old-school

 
use warnings;
use strict;


sub non_oxford_list {
    my ($s) = @_;
    my $p = rindex $s, ',';
    substr ($s,$p,1) = " and" if $p > -1;
    return $s;
}

use Test::More tests => 3;

is non_oxford_list('A'), 'A';
is non_oxford_list('A, B'), 'A and B';
is non_oxford_list('A, B, C'), 'A, B and C';

FWIW: rindex , substr

[jwkrahn]

$test =~ s/,(.+?)$/ and$1/; ALWAYS goes to the first comma and the rest is anchored to the end of the line so it will always match everything to the end of the line. Without the anchor it would match the next character after the comma (the space character.)

There are a few different ways to match the last comma:

$ perl -le'my @x = ( "A", "A, B", "A, B, C" );
# 1a
for my $test ( @x ) {
    $test =~ s/(.*),/$1 and/s;
    print $test;
    }
'
A
A and B
A, B and C

$ perl -le'my @x = ( "A", "A, B", "A, B, C" );
# 1b
for my $test ( @x ) {
    $test =~ s/.*\K,/ and/s;
    print $test;
    }
'
A
A and B
A, B and C

$ perl -le'my @x = ( "A", "A, B", "A, B, C" );
# 2a
for my $test ( @x ) {
    $test =~ s/,([^,]*)\z/ and$1/;
    print $test;
    }
'
A
A and B
A, B and C

$ perl -le'my @x = ( "A", "A, B", "A, B, C" );
# 2b
for my $test ( @x ) {
    $test =~ s/,(?=[^,]*\z)/ and/;
    print $test;
    }                     
'
A
A and B
A, B and C

$ perl -le'my @x = ( "A", "A, B", "A, B, C" );
# 3
for my $test ( @x ) {
    $test = reverse $test;
    $test =~ s/,/dna /;
    $test = reverse $test;
    print $test;
    }
'
A
A and B
A, B and C

Which one you use will depend on how much data you have to process.

[sleet]

You don't need to use a regex here. Here's a function I use frequently:

sub name_join {
    return '' unless @_;
    return $_[0] if 1 == @_;
    return join ', ', @_[0 .. $#_ - 2], "$_[-2] and $_[-1]";
}