$ ./a.out '([ab]{6}|a)*?b' aaaabbbb
regexec() returned 0
rm_so 0, rm_eo 5

$ echo aaaabbbb | grep -E -o '([ab]{6}|a)*?b'
aaaab
b
b
b

The matching process is described in [xref to 9.2].

If the pattern permits a variable number of matching characters and thus there is more than one such sequence starting at that point, the longest such sequence is matched. For example, the BRE "bb*" matches the second to fourth characters of the string "abbbc", and the ERE "(wee|week)(knights|night)" matches all ten characters of the string "weeknights".

Consistent with the whole match being the longest of the leftmost matches, each subpattern, from left to right, shall match the longest possible string.

If the pattern permits a variable number of matching characters and thus there is more than one such sequence starting at that point, the matched sequence shall be the longest such sequence for which any minimal repetitions (see [xref to 9.4.6]) used in the match have the shortest possible match. For example, the BRE "bb*" matches the second to fourth characters of the string "abbbc", and the ERE "(wee|week)(knights|night)" matches all ten characters of the string "weeknights". However, the ERE "(aaa??)*" matches only the first four characters of the string "aaaaa", not all five, because in order to match all five, "a??" would match with length one instead of zero; the ERE "(aaa??)*|(aaa?)*" matches all five because the longest match is one which does not use any minimal repetitions.

Consistent with the match for the entire regular expression being the leftmost and longest for which any minimal repetitions used in the match have the shortest possible match, each BRE or ERE in a concatenated set, from left to right, shall match the longest possible string for which any minimal repetitions used in the match for that BRE or ERE have the shortest possible match.

the subpattern "(.*?)" matches the empty string, since that is the longest possible match for the ERE ".*?"

the subexpression "(.*?)" matches the empty string, since that is the longest possible match for which the minimal repetition ".*?" has the shortest possible match (zero length).

the longest sequence shall be measured

the sequence length shall be measured

<small>Note:The grammar defines syntax only and places no requirements on implementations as to how the parsed BRE or ERE is used for matching. The matching process is described in [xref to 9.2].</small>

Note that the repetition modifier '?' (<question-mark>) is specified as changing the matching behavior for the modified repetition from the leftmost longest possible match to the leftmost shortest possible match. This does not necessarily give the same result as matching with the least repetitions. For example, the ERE "([ab]{6}|a)*?b" matches the first five characters of the string "aaaabbbb" as this is the shortest for the minimal repetition "*?". Matching with the least repetitions would match the first seven characters by using one repetition of "[ab]{6}" instead of four repetitions of "a". This distinction is only possible because the alternatives in an ERE alternation are chosen according to which gives the longest (or shortest) match. Other types of regular expression exist (notably in perl, php, and python) where the alternatives are tried in order; for those there is no difference between longest and most repetitions or between shortest and least repetitions.

Geoff, I tested the `re` module from Python v3.10.15's standard library,
and the PCRE module from PHP v8.3.11, they all match "aaaabbb" with
'([ab]{6}|a)*?b'. It seems that it's the macOS implementation is an
outcast.

#?2|kent:tmp$ ./p-pcre2 '([ab]{6}|a)*?b' aaaabbb
0: 0/7
        <aaaabbb>
1: 0/6
        <aaaabb>
#?0|kent:tmp$ ./p-tre '([ab]{6}|a)*?b' aaaabbb
HA at <6>
HA at <|>
MINIINININI  0 mini=0
MINIINININI 1 mini=1 rest:*
HAHAHAH
0: 0/5
        <aaaab>
1: 3/4
        <a>
#?0|kent:tmp$ ./p-c '([ab]{6}|a)*?b' aaaabbb
0: 0/7
        <aaaabbb>
1: 0/6
        <aaaabb>

- regex:
[0-9](((((([0-9][a-z]*[0-9])*?)*)*?)*)*?)*[0-9]

- string to be matched:
12abc34def56ghi78jkl90mnop12qrst34uvw56xyz78

#?0|kent:tmp$ ./p-c '[0-9](((((([0-9][a-z]*[0-9])*?)*)*?)*)*?)*[0-9]' 12abc34def56ghi78jkl90mnop12qrst34uvw56xyz78
0: 0/44
        <12abc34def56ghi78jkl90mnop12qrst34uvw56xyz78>
1: 1/43
        <2abc34def56ghi78jkl90mnop12qrst34uvw56xyz7>
2: 1/43
        <2abc34def56ghi78jkl90mnop12qrst34uvw56xyz7>
3: 1/43
        <2abc34def56ghi78jkl90mnop12qrst34uvw56xyz7>
4: 1/43
        <2abc34def56ghi78jkl90mnop12qrst34uvw56xyz7>
5: 1/43
        <2abc34def56ghi78jkl90mnop12qrst34uvw56xyz7>
6: 38/43
        <6xyz7>
#?0|kent:tmp$ ./p-pcre2 '[0-9](((((([0-9][a-z]*[0-9])*?)*)*?)*)*?)*[0-9]' 12abc34def56ghi78jkl90mnop12qrst34uvw56xyz78
0: 0/2
        <12>
1: 1/1
        <>
2: -1/-1
3: -1/-1
4: -1/-1
5: -1/-1
6: -1/-1
#?0|kent:tmp$ ./p-tre '[0-9](((((([0-9][a-z]*[0-9])*?)*)*?)*)*?)*[0-9]' 12abc34def56ghi78jkl90mnop12qrst34uvw56xyz78
MINIINININI  0 mini=0
MINIINININI  0 mini=0
MINIINININI 1 mini=1 rest:*
MINIINININI  0 mini=0
MINIINININI  0 mini=0
MINIINININI 1 mini=1 rest:*
MINIINININI  0 mini=0
MINIINININI  0 mini=0
MINIINININI 1 mini=1 rest:*
MINIINININI  0 mini=0
HAHAHAH
0: 0/2
        <12>
1: 1/1
        <>
2: 1/1
        <>
3: 1/1
        <>
4: 1/1
        <>
5: 1/1
        <>
6: -1/-1

$ echo 12abc34def56ghi78jkl90mnop12qr | perl -e '$i=<STDIN>;if($i =~ "[0-9](((((([0-9][a-z]*[0-9])*?)*)*?)*)*?)*[0-9]"){print "i<$i>; 1<$1> 2<$2> 3<$3> &<$&>\n"}else{print "no match\n"}'
i<12abc34def56ghi78jkl90mnop12qr
>; 1<> 2<> 3<> &<12>

When a multi-character collating element in a bracket expression (see Section 9.3.5, on page 182) is involved, the longest sequence shall be measured in characters consumed from the string to be matched; that is, the collating element counts not as one element, but as the number of characters it matches.

#include <regex.h>
#include <stdio.h>

int main()
{
    int ret = 100;
    static regex_t preg;
    static regmatch_t matches[16];

    ret = regcomp(&preg, "[0-9](((((([0-9][a-z]+[0-9])+?)+)+?)+)+?)+[0-9]", REG_EXTENDED|REG_ENHANCED);
    printf("regcomp returned: %d\n", ret);
    ret = regexec(&preg, "12abc34def56ghi78jkl90mnop12qrst34uvw56xyz78", 16, matches, 0);
    printf("regexec returned: %d\n", ret);
    for(int i=0; i<16; i++) printf("%ld\t%ld\n", (long)matches[i].rm_so, (long)matches[i].rm_eo);
    regfree(&preg);

    return 0;
}

regcomp returned: 0
regexec returned: 0
0       7
1       6
-1      -1
-1      -1
-1      -1
-1      -1
-1      -1
-1      -1
-1      -1
-1      -1
-1      -1
-1      -1
-1      -1
-1      -1
-1      -1
-1      -1

The matching process is described in [xref to 9.2].

If the pattern permits a variable number of matching characters and thus there is more than one such sequence starting at that point, the longest such sequence is matched. For example, the BRE "bb*" matches the second to fourth characters of the string "abbbc", and the ERE "(wee|week)(knights|night)" matches all ten characters of the string "weeknights".

Consistent with the whole match being the longest of the leftmost matches, each subpattern, from left to right, shall match the longest possible string.

If the pattern permits a variable number of matching characters and thus there is more than one such sequence starting at that point, the match shall be made according to the following rules:

1. For a BRE, or an ERE that does not use the repetition modifier '?', the match shall be the leftmost longest.

2. If an ERE contains repetitions with and without the repetition modifier '?', the precedence between the repetitions shall be:

a. Each leftmost shortest match shall match the leftmost shortest sequence in the string, in descending priority from left to right.

b. Consistent with rule 2a, the length matched by the entire regular expression shall be the leftmost longest.

c. Consistent with rules 2a and 2b, each leftmost longest match shall match the leftmost longest sequence in the string, in descending priority from left to right.

d. If an attempt is made to match the same sequence of the string using repetitions both with and without the repetition modifier '?', the behavior is unspecified. For example, the ERE ([0-9]+)+? has unspecified behavior.

According to these rules, the BRE "bb*" matches the second to fourth characters of the string "abbbc", and the ERE "(wee|week)(knights|night)" matches all ten characters of the string "weeknights". However, the ERE "(aaa??)*" matches only the first four characters of the string "aaaaa", not all five, because in order to match all five, "a??" would match with length one instead of zero; the ERE "(aaa??)*|(aaa?)*" matches all five because the longest match is one which does not use any minimal repetitions.

Consistent with the match for the entire regular expression being made according to the above rules, each BRE or ERE in a concatenated set, from left to right, shall match according to the above rules, applied to that BRE or ERE.

the subpattern "(.*?)" matches the empty string, since that is the longest possible match for the ERE ".*?"

the subexpression "(.*?)" matches the empty string, since the minimal repetition ".*?" has priority and the empty string is the shortest possible match (zero length) for that repetition.

the longest sequence shall be measured

the sequence length shall be measured

<small>Note:The grammar defines syntax only and places no requirements on implementations as to how the parsed BRE or ERE is used for matching. The matching process is described in [xref to 9.2].</small>

Note that the repetition modifier '?' (<question-mark>) is specified as changing the matching behavior for the modified repetition from the leftmost longest possible match to the leftmost shortest possible match. This does not necessarily give the same result as matching with the least repetitions. For example, the ERE "([ab]{6}|a)*?b" matches the first five characters of the string "aaaabbbb" as this is the shortest for the minimal repetition "*?". Matching with the least repetitions would match the first seven characters by using one repetition of "[ab]{6}" instead of four repetitions of "a". This distinction is only possible because the alternatives in an ERE alternation are chosen according to which gives the longest (or shortest) match. Other types of regular expression exist (notably in perl, php, and python) where the alternatives are tried in order; for those there is no difference between longest and most repetitions or between shortest and least repetitions.