Ttdfjt

According to the Python3 Regex documentation:

m,n?

Causes the resulting RE to match from m to n repetitions of the
preceding RE, attempting to match as few repetitions as possible. This
is the non-greedy version of the previous qualifier. For example, on
the 6-character string 'aaaaaa', a3,5 will match 5 'a' characters,
while a3,5? will only match 3 characters.

However, this seems to be contradicted by the following experiment:

import re
regex = re.compile('(abc|d|abcde)1,2?(e|f)')
regex.match('abcdef')

... which matches 'abcde'. This necessarily involves 2 repetitions of (abc|d|abcde), namely, 'abc' and 'd'. However, there was an alternative match candidate that involved only 1 repetition of (abc|d|abcde), namely 'abcde'.

Am I misreading the documentation, or does m,n? actually minimize the number of characters matched (or some other objective), and not the number of repetitions?

m,n? tries to match as few times as possible, but it's not going to reach into the abc|d|abcde and change the behavior of |. | still tries the left option first.

(abc|d|abcde)1,2? tries to match (abc|d|abcde) once, and succeeds, matching abc. The regex engine then continues on with the rest of the pattern and tries to match (e|f), which fails. It backtracks and tries to match another repetition of abc|d|abcde, and matches d. It continues on to (e|f) again and matches e successfully.

Perhaps you expected the backtracking to try a different option for the first (abc|d|abcde) before trying a second (abc|d|abcde). It doesn't do that. It would try that eventually, if it had to, but trying more matches for the 1,2? comes first.

It doesn't force the minimum number of repetitions, it just allows it to match fewer times.

When you have multiple alternatives that can match, regexp engines handle things differently. Some are "eager" and use the first matching alternatives, others use the "longest match" rule. Apparently Python is eager. So (abc|d|abcde) will match abc rather than abcde, and then the next repetition will match e. It doesn't backtrack to see if theres a result with fewer repetitions.

The solution is to put the longer alternatives first. Change it to

regex = re.compile('(abcde|abc|d)1,2?(e|f)')

Regex does not evaluate all possible options and chooses the smallest one - if delivers the first one it finds:

import re
regex = re.compile('(abc|def|gh|abcde|fghi)2,3?(i|j)')
rex.match('abcdefghij')

The first match for 2,3 is abc|def|gh (left to right).

If you reorder your pattern, you get what you want:

import re
rex = re.compile('(abcde|fghi|abc|def|gh)2,3?(i|j)')
print(rex.match('abcdefghij').group()) 

Output:

abcdefghij

The nongreedy modifier adjusts the preference of the regex engine. Normally, with greedy matching, the engine will prefer the longest leftmost possible match. With stingy (nongreedy) matching, the match governed by the stingy modifier will prefer the shortest leftmost possible match.

Notice that the engine will still do its darndest to find a match. If a longer expression will allow the engine to return a match where a shorter one won't, the engine will pick the one which allows it to return a match.

Perhaps it is helpful to think about this in terms of backtracking. With a greedy match, the engine will start with the hypothesis that a maximal repetition will succeed, then if that fails, backtrack and try successively shorter matches until it finds a match, or the search space is exhausted. With stingy matching, the preferred hypothesis is the shortest possible match, and backtracking will attempt successively increasing the number of repetitions.

What's probably tripping up your (unclear) example is that alternation specifies an explicit order for backtracking. The engine will explore matching starting with the first pattern among the alternatives, and only proceed to try the other alternatives if it runs out of search space before finding a match.

The alternation in the group starts matching from the left and has a non greedy quantifier of 1,2? which matches as few as needed and applies to that group. Python does not try to find the longest match in the alternation, but the first match.

When the matching starts, the engine finds abc first and then tries to match e or f next, which does not match because there is a d following abc.

But because the quantifier is 1,2? there is still one option left to try for the first group and backtracks to try to find a match again. It can not match abc but it can match d. Then it tries to match e or f again, where it can match e