For now, when capturing groups are used within repetitions, it is impossible to capure what they match 
individually within the list of matched repetitions.

E.g. the following regular expression:

(0|1[0-9]{0,2}|2(?:[0-4][0-9]?|5[0-5]?)?)(?:\.(0|1[0-9]{0,2}|2(?:[0-4][0-9]?|5[0-5]?)?)){3}

is a regexp that contains two capturing groups (\1 and \2), but whose the second one is repeated (3 times) to 
match an IPv4 address in dotted decimal format. We'd like to be able to get the individual multiple matchs 
for the second group.

For now, capturing groups don't record the full list of matches, but just override the last occurence of the 
capturing group (or just the first if the repetition is not greedy, which is not the case here because the 
repetition "{3}" is not followed by a "?"). So \1 will effectively return the first decimal component of the 
IPv4 address, but \2 will just return the last (fourth) decimal component.


I'd like to have the possibility to have a compilation flag "R" that would indicate that capturing groups 
will not just return a single occurence, but all occurences of the same group. If this "R" flag is enabled, 
then:

- the Match.group(index) will not just return a single string but a list of strings, with as many occurences 
as the number of effective repetitions of the same capturing group. The last element in that list will be the 
one equal to the current behavior

- the Match.start(index) and Match.end(index) will also both return a list of positions, those lists having 
the same length as the list returned by Match.group(index).

- for consistency, the returned values as lists of strings (instead of just single strings) will apply to all 
capturing groups, even if they are not repeated.


Effectively, with the same regexp above, we will be able to retreive (and possibily substitute):

- the first decimal component of the IPv4 address with "{\1:1}" (or "{\1:}" or "{\1}" or "\1" as before), 
i.e. the 1st (and last) occurence of capturing group 1, or in Match.group(1)[1], or between string positions Match.start(1)[1] and Match.end(1)[1] ;

- the second decimal component of the IPv4 address with "{\2:1}", i.e. the 1st occurence of capturing group 
2, or in Match.group(2)[1], or between string positions Match.start(2)[1] and Match.end(2)[1] ;

- the third decimal component of the IPv4 address with "{\2:2}", i.e. the 2nd occurence of capturing group 2, 
or in Match.group(2)[2], or between string positions Match.start(2)[2] and Match.end(2)[2] ;

- the fourth decimal component of the IPv4 address with "{\2:3}" (or "{\2:}" or "{\2}" or "\2"), i.e. the 3rd 
(and last) occurence of capturing group 2, or in Match.group(2)[2], or between string positions 
Match.start(2)[3] and Match.end(2)[3] ;


This should work with all repetition patterns (both greedy and not greedy, atomic or not, or possessive), in 
which the repeated pattern contains any capturing group.


This idea should also be submitted to the developers of the PCRE library (and Perl from which they originate, 
and PHP where PCRE is also used), so that they adopt a similar behavior in their regular expressions.

If there's already a candidate syntax or compilation flag in those libraries, this syntax should be used for 
repeated capturing groups.

I'd like to add that the same behavior should also affect the span(index) 
method of MatchObject, that should also not just return a single (start, 
end) pair, but that should in this case return a list of pairs, one for 
each occurence, when the "R" compilation flag is specified.

This also means that the regular expression compilation flag R should be 
supported as these constants:
Regexp.R, or Regexp.REPETITIONS

Rationale for the compilation flag:

You could think that the compilation flag should not be needed. However, 
not using it would mean that a LOT of existing regular expressions that 
already contain capturing groups in repetitions, and for which the 
caputiring group is effectively not used and should have been better 
encoded as a non-capuring group like (?:X) instead of (X), will suffer a 
negative performance impact and a higher memory usage.

The reason is that the MatchObject will have to store lists of 
(start,end) pairs instead of just a single pair: using a list will not 
be the default, so MatchObject.group(groupIndex), 
MatchObject.start(groupIndex), MatchObject.end(groupIndex), and 
MatchObject.span(groupIndex) will continue to return a single value or 
single pair, when the R compilation flag is not set (these values will 
continue to return only the last occurence, that will be overriden after 
each matched occurence of the capturing group.

The MatchObject.groups() will also continue to return a list of single 
strings without that flag set (i.e. a list of the last occurence of each 
capturing group). But when the R flag will be specified, it will return, 
instead, a list of lists, each element being for the group with the same 
index and being itself a list of strings, one for each occurence of the 
capturing group.

Implementation details:

Currently, the capturing groups behave quite randomly in the values returned by MachedObject, when backtracking occurs in a repetition. This 
proposal will help fix the behavior, because it will also be much easier 
to backtrack cleanly, occurence by occurence, by just dropping the last 
element in the list of (start,end) pairs stored in the MatchedObject for 
all capturing groups specified WITHIN the repeated sub-expression.

I'm skeptical about what you are proposing for the following reasons:
1) it doesn't exist in any other implementation that I know;
2) if implemented as default behavior:
   * it won't be backward-compatible;
   * it will increase the complexity;
3) it will be a proprietary extension and it will reduce the
compatibility with other implementations;
4) I can't think to any real word situation where this would be really
useful.

Using a flag like re.R to change the behavior might solve the issue 2),
but I'll explain why I don't think this is useful.

Let's take a simpler ipv4 address as example: you may want to use
'^(\d{1,3})(?:\.(\d{1,3})){3}$' to capture the digits (without checking
if they are in range(256)).
This currently only returns:
>>> re.match('^(\d{1,3})(?:\.(\d{1,3})){3}$', '192.168.0.1').groups()
('192', '1')

If I understood correctly what you are proposing, you would like it to
return (['192'], ['168', '0', '1']) instead. This will also require an
additional step to join the two lists to get the list with the 4 values.

In these situations where some part is repeating, it's usually easier to
use re.findall() or re.split() (or just a plain str.split for simple
cases like this):
>>> addr = '192.168.0.1'
>>> re.findall('(?:^|\.)(\d{1,3})', addr)
['192', '168', '0', '1']
>>> re.split('\.', addr) # no need to use re.split here
['192', '168', '0', '1']

In both the examples a single step is enough to get what you want
without changing the existing behavior.

'^(\d{1,3})(?:\.(\d{1,3})){3}$' can still be used to check if the string
has the right "format", before using the other methods to extract the data.

So I'm -1 about the whole idea and -0.8 about an additional flag.
Maybe you should discuss about this on the python-ideas ML.

You're wrong, it WILL be compatible, because it is only conditioned by a 
FLAG. The flag is there specifically for instructing the parser to 
generate lists of values rather than single values.

Without the regular compilation flag set, as I said, there will be NO 
change.

Reopening the proposal, which is perfectly valid !

Note that I used the IPv4 address format only as an example. There are 
plenty of other more complex cases for which we really need to capture the 
multiple occurences of a capturing group within a repetition.

I'm NOT asking you how to parse it using MULTIPLE regexps and functions. 
Of course you can, but this is a distinct problem, but certinaly NOT a 
general solution (your solution using split() will NOT work with really A 
LOT of other regular expressions).

In addition, your suggested regexp for IPv4:

'^(\d{1,3})(?:\.(\d{1,3})){3}$'

is completely WRONG ! It will match INVALID IPv4 address formats like 
"000.000.000.000". Reread the RFCs... because "000.000.000.000" is 
CERTAINLY NOT an IPv4 address (if it is found in an URL) but a domain name 
that must be resolved into an IP address using domain name resolution 
requests.

Summary of your points with my responses :


> 1) it doesn't exist in any other implementation that I know;

That's exactly why I proposed to discuss it with the developers of other 
implementations (I cited PCRE, Perl and PHP developers, there are 
others).


> 2) if implemented as default behavior:
>   * it won't be backward-compatible;

Wrong. This does not even change the syntax of regualr expressions 
themselves.

>   * it will increase the complexity;

Wrong. All the mechanic is already implemented: when the parser will 
store string index positions for a matched group it will just have to 
append a pair in the list stored in MatchObject.group(index) (it will 
create the list if it is not ealready there, but it should be already 
initialized to an empty list by the compiler) when the flag.R is set, 
instead of overwriting the existing pair without wondering if there was 
already another occurence of the same capturing group.


> 3) it will be a proprietary extension and it will reduce the
compatibility with other implementations;

Already suggested above. This will hovever NOT affect the compatibility 
of existing implementation that don't have the R flag.


> 4) I can't think to any real word situation where this would be really
useful.

There are really a lot ! Using multiple split operations and multiple 
parsing on partly parsed regular expressions will not be a solution in 
many situations (think about how you would perform matches and using 
them that in 'vi' or 'ed' with a single "s/regexp/replacement/flag" 
instruction, if there's no extension with a flag and a syntax for 
accesing the individual elements the replacement string).

And anyway, my suggestion is certainly much more useful than atomic groups 
and possessive groups that have much lower use, and which are already 
being tested in Perl but that Python (or PCRE, PHP, and most 
implementations of 'vi'/'ed', or 'sed') still does not support.

If you read what Ezio wrote carefully you will see that he addressed
both of your points: he acknowledged that a flag would solve (2) (but
disagreed that it was worth it), and he said you could use the first
expression to validate the string before using the split to obtain the
data.  Doing it all in one regex might seem more efficient, but at least
in the single use case you have presented it would lead to more
complicated code.

Simple. obvious feature requests can be opened and acted upon directly
in the tracker, but more complicated requests should be made as
proposals on the python-ideas list, and if they are well received there
then an issue can be opened (or in this case you could reopen this one)
in the tracker with a pointer to the python-ideas thread.  In most
cases, such an issue would need to include a proposed patch.

Note that we don't really have a resolution that says 'sent to
python-ideas', thus the use of the 'rejected' status.

Just to clarify, when I said "in most cases such an issue would need to
include a proposed patch", I mean that even if everyone agrees it is a
good idea it isn't likely to happen unless there is a proposed patch :)

I had read carefully ALL what ezio said, this is clear in the fact that 
I have summarized my responses to ALL the 4 points given by ezio.

Capturing groups is a VERY useful feature of regular expressions, but 
they currently DON'T work as expected (in a useful way) when they are 
used within repetitions (unless you don't need any captures at all, for 
example when just using find(), and not performing substitutions on the 
groups.

My proposal woul have absolutely NO performance impact when capturing 
groups are not used (find only, without replacement, so there the R flag 
can be safely ignored).

It would also not affect the case where capturing groups are used in the 
regexp, but these groups are not referenced in the substitution or in 
the code using MatchObject.group(index) : these indexes are already not 
used (or should not, because this is most of the time a bug when it just 
returns the last occurence).

Using multiple parsing operations with multiple regexps is really 
tricky, when all could be done directly from the original regexp, 
without modifying it. In addition, using split() or similar will not 
work as expected, when the splitting operations will not correctly parse 
the context in which the multiple occurences are safely separated (this 
context is only correctly specified in the original regexp where the 
groups, capturing or not, are specified).

This extension will also NOT affect the non-capturing groups like:
 (?:X){m,n}
 (?:X)*
 (?:X)+
It will ONLY affect the CAPTURING groups like:
 (X){m,n}
 (X)*
 (X)+
and only if the R flag is set (in which case this will NOT affect the 
backtracking behavior, or which strings that will be effectively 
matched, but only the values of the returned "\n" indexed group.

If my suggestion to keep the existing MatchObject.function(index) API 
looks too dangerous for you, because it would change the type of the 
returned values when the R flag is set, you can as well rename them to 
get a specific occurence of a group. Such as:

 MatchObject.groupOccurences(index)
 MatchObject.startOccurences(index)
 MatchObject.endOccurences(index)
 MatchObject.spanOccurences(index)
 MatchObject.groupsOccurences(index)

But I don't think this is necessary; it will be already expected that 
they will return lists of values (or lists of pairs), instead of just 
single values (or single pairs) for each group: Python (as well as PHP 
or Perl) can already manage return values with varying datatypes.

May be only PCRE (written for C/C++) would need a new API name to return 
lists of values instead of single values for each group, due to existing 
datatype restrictions.

My proposal is not inconsistant: it returns consistant datatypes when 
the R flag is set, for ALL capturing groups (not just those that are 
repeated.

Anyway I'll submit my idea to other groups, if I can find where to post 
them. Note that I've already implemented it in my own local 
implementation of PCRE, and this works perfectly with effectively very 
few changes (currently I have had to change the datatypes for matching 
objects so that they can return varying types), and I have used it to 
create a modified version of 'sed' to perform massive filtering of data:

It really reduces the number of transformation steps needed to process 
such data correctly, because a single regexp (exactly the same that is 
already used in the first step used to match the substrings we are 
interested in, when using existing 'sed' implementations) can be used to 
perform the substitutions using indexes within captured groups. And I 
would like to have it incoporated in Python (and also Perl or PHP) as 
well.

> You're wrong, it WILL be compatible, because it is only conditioned
> by a FLAG.

Sorry, I missed that you mentioned the flag already in the first
message, but what I said in 1), 3) and 4) is still valid.

> There are plenty of other more complex cases for which we really
> need to capture the multiple occurences of a capturing group within
> a repetition.

Can you provide some example where your solution is better than the
other available way of doing it? During the years lot of extensions have
been added to the regex engines, if no one added this is probably
because these problems can be already solved in other ways.

> I'm NOT asking you how to parse it using MULTIPLE regexps and
> functions. 
> Of course you can, but this is a distinct problem, but certinaly NOT
> a general solution (your solution using split() will NOT work with
> really A LOT of other regular expressions).

Even with your solution, in most of the cases you will need additional
steps to assemble the results (at least in the cases with some kind of
separator, where you have to join the first element with the followings).

I can see a very limited set of hypothetical corner cases where your
proposal may save a few line of codes but I don't think it's worth
implementing all this just for them.
An example could be:
>>> re.match('^([0-9A-F]{2}){4} ([a-z]\d){5}$', '3FB52A0C a2c4g3k9d3',
re.R).groups()
(['3F', 'B5', '2A', '0C'], ['a2', 'c4', 'g3', 'k9', 'd3'])
but it's not really a real-world case, if you have some real-world
example I'd like to see it.

> In addition, your suggested regexp for IPv4:
> '^(\d{1,3})(?:\.(\d{1,3})){3}$'
> is completely WRONG !

That's why I wrote 'without checking if they are in range(256)'; the
fact that this regex matches invalid digits was not relevant in my
example (and it's usually easier to convert the digits to int and check
if 0 <= digits <= 255). :)


>> 1) it doesn't exist in any other implementation that I know;
>
> That's exactly why I proposed to discuss it with the developers of
> other implementations (I cited PCRE, Perl and PHP developers, there
> are others).

So maybe this is not the right place to ask.

>> 3) it will be a proprietary extension and it will reduce the
>> compatibility with other implementations;
>
> Already suggested above. This will hovever NOT affect the
> compatibility of existing implementation that don't have the R flag.

What I meant is that a regex that uses the re.R flag in Python won't
work in other languages/implementations because they don't have it, and
a "general" regex (e.g. for an ipv6 address) will have to be
adapted/rewritten in order to take advantage of re.R.

>> 4) I can't think to any real word situation where this would be 
>> really useful.
>
> There are really a lot ! Using multiple split operations and multiple 
> parsing on partly parsed regular expressions will not be a solution 
> in many situations (think about how you would perform matches and 
> using  them that in 'vi' or 'ed' with a single
> "s/regexp/replacement/flag" instruction, if there's no extension
> with a flag and a syntax for accesing the individual elements the 
> replacement string).

Usually when the text to be parsed starts to be too complex is better to
use another approach, e.g. using a real parser or dividing the text in
smaller units and work on them independently. Even if re.R could make
this easier I would still prefer to have a few more line of code that do
different things that a single big regex that does everything.

> And anyway, my suggestion is certainly much more useful than atomic 
> groups and possessive groups that have much lower use [...]

Then why no one implemented it yet? :)

ezio said:
>>> re.match('^(\d{1,3})(?:\.(\d{1,3})){3}$', '192.168.0.1').groups()
('192', '1')
> If I understood correctly what you are proposing, you would like it to
return (['192'], ['168', '0', '1']) instead.

Yes, exactly ! That's the correct answer that should be returned, when 
the R flag is set.

> This will also require an additional step to join the two lists to get 
the list with the 4 values.

Yes, but this is necessary for full consistency of the group indexes. 
The current return value is clearly inconsistant (generally it returns 
the last occurence of the capturing group, but I've discovered that this 
is not always the case, because of matches that are returned after 
backtracking...)

It is then assumed that when the R flag is set, ALL occurences of 
repeated groups will be returned individually, instead of just a 
'random' one. Note that for full generalization of the concept, there 
should even be lists of lists if a capturing group contains itself 
another inner capturing group (with its own index), in order to 
associate them correctly with each occurence of the outer capturing 
group (however I've still not experimented this in my local 
experimentation, so all occurences are grouped in the same returned 
list, independantly of the occurence of the outer capturing group in 
which they were found).

> That's why I wrote 'without checking if they are in range(256)'; the
fact that this regex matches invalid digits was not relevant in my
example (and it's usually easier to convert the digits to int and check
if 0 <= digits <= 255). :)

NO ! You have to check also the number of digits for values below 100 (2 
digits only) or below 10 (1 digit only)

And when processing web log files for example, or when parsing Wiki 
pages or emails in which you want to autodetect the presence of ONLY 
valid IP addresses within some contexts, where you want to transform 
them to another form (for example when converting them to links or to 
differentiate 'anonymous' users in wiki pages from registered named 
users, you need to correctly match these IP addresses. In addition, 
these files will often contain many other occurences that you don't want 
to transform, but just some of them in specific contexts given by the 
regexp. for this reason, your suggestion will often not work as 
expected.

The real need is to match things exactly, within their context, and 
capturing all occurences of capturing groups.

I gave the IPv4 regexp only as a simple example to show the need, but 
there are of course much more complex cases, and that's exactly for 
those cases that I would like the extension: using alternate code with 
partial matches and extra split() operations give a code that becomes 
tricky, and most often bogous. Only the original regexp is precise 
enough to parse the content correctly, find only the matches we want, 
and capturing all the groups that we really want, in a single operation, 
and with a near-zero cost (and without complication in the rest of the 
code using it).

> Even with your solution, in most of the cases you will need additional
steps to assemble the results (at least in the cases with some kind of
separator, where you have to join the first element with the 
followings).

Yes, but this step is trivial and fully predictable. Much more viable 
than the other solutions proposed which gives tricky and often complex 
and bogous code.

How many bugs have been found in code using split() for example to parse 
URLs ? There are countlesss in many softwares (and it is not terminated 
!)

And in fine, the only solution is to simply rewrite the parser 
completely, without regexps at all, or to reduce the generality of the 
problems that the program was supposed to solve (i.e. asserting in the 
code some implementation limits, to reject some forms that were 
previously considered valid). Think about it, the capturing groups are 
the perfect solution for solving the problem cleanly, provided that they 
work as intended and return all their occurences.

> a "general" regex (e.g. for an ipv6 address)

I know this problem, and I have already written about this. It is not 
possible to parse it in a single regexp if it is written without using 
repetitions. But in that case, the regexp becomes really HUGE, and the 
number of groups in the returned match object is prohibitive. That's why 
CPAN has had to write a specific module for IPv6 addresses in Perl.

Such module can be reduced to just a couple of lines with a single 
regexp, if its capturing groups correctly return ALL their occurences in 
the regexp engine: it requires no further processing and analysis, and 
the data can effectively be reassembled cleanly, just from the returned 
groups (as lists):
- \1 and \2 (for hex components of IPv6 in hex format only, where \1 can 
occur 0 or 1 time, and \2 can occur 0 to 7 times)
- or from \1 to \2 and \3 to \4 (for hex components in \1..\2, where \1 
occurs 0 or 1 time and \2 occurs 0 to 5 times, and for decimal 
components in \3..\4, where \3 occurs 1 time and \4 occurs exactly 3 
times).

>> And anyway, my suggestion is certainly much more useful than atomic 
>> groups and possessive groups that have much lower use [...]
>Then why no one implemented it yet? :)

That's because they had to use something else than regexps to do their 
parsing. All those that had to do that *pested* that the regexps were 
not capturing all occurences.

And then later they regretted it, because they had to fix their 
alternate code (such as those using the bogous split() alternatives...) 
and finally rewrote their own parsers (sometimes with a combination of 
(f)lex+yacc/bison, even if the full expression was given in a single 
regexp which was expressive enough to match only the exact match they 
wanted, but without using the returned captured groups): this means an 
extra parsing for the found substring (in their correct context) in 
order to process it.

>>> re.match('^(\d{1,3})(?:\.(\d{1,3})){3}$', '192.168.0.1').groups()
('192', '1')
> If I understood correctly what you are proposing, you would like it to
return (['192'], ['168', '0', '1']) instead.

In fact it can be assembled in a single array directly in the regexp, by 
naming the destination capturing group (with the same name, it would get 
the same group index, instead of of allocating a new one). E.g., with 
someting like:

>>> re.match('^(?P<parts>=\d{1,3})(?:\.(?P<parts>=\d{1,3})){3}$', 
'192.168.0.1').groups()

would return ("parts": ['192', '168', '0', '1']) in the same first 
group.

This could be used as well in PHP (which supports associative arrays for 
named groups which are also indexed positionnaly).

Instead of a new flag, a '*' could be put after the quantifier, eg:

    (\d+)(?:\.(\d+)){3}*

MatchObject.group(1) would be a string and MatchObject.group(2) would be
a list of strings.

The group references could be \g<1>, \g<2:0>, \g<2:1>, \g<2:2>.

However, I think that it's extending regexes too far; something else
should be used, eg pyparsing or some type of context-free grammar with
optional constraints.

-1 from me

You said that this extension was not implemented anywhere, and you were 
wrong.

I've found that it IS implemented in Perl 6! Look at this discussion:

http://www.perlmonks.org/?node_id=602361

Look at how the matches in quantified capture groups are returned as 
arrayref's (i.e. references to a numbered array).

So my idea is not stupid. Given that Perl rules the world of the Regexp 
language, it will be implemented elsewhere sonner or later, notably in 
PCRE, awk, vi, sed, PHP, .NET library...

Already, this is used in CPAN libraries for Perl v6... (when the X flag 
is set for extensions)

Anyway, there are ways to speedup regexps, even without instructing the 
regexps with anti-backtracking syntaxes.

See http://swtch.com/~rsc/regexp/regexp1.html
(article dated January 2007)
Which discusses how Perl, PCRE (and PHP), Python, Java, Ruby, .NET 
library... are slow because they are using backtracking a single state 
in the NFA, instead of using simultaneously active states (which 
correctly emulates the DFA, without having to actually build the DFA 
transition states table, which could grow combinatorially, as seen in 
yacc and Bison).

Java uses now the Thomson approach in its latest releases, but I wonder 
how Python works: does it use the DFA simulation? Do you use PCRE?

Note that I've been using the DFA simulation since more than 20 years in 
1987, when I built my first regexp matcher (because the existing 
implementation at that time were really damn slow), after I read the 
Aho/Sethi/Ullman book which already demonstrated the algorithm.

This algorithm has been implemented in some tools replacing the old 
yacc/Bison tools, because they generate huge DFA transition tables (and 
this was the reason why Lex and Yacc were maintained as separate tools, 
Lex using the single-state NFA approach with excessive backtracking, and 
Yacc/Bison trying to generate the full DFA transition tables.) : the 
first language to use this approach was the Purdue Univerity Compiler 
Construction Tools Set (PCCTS) which was initially written in C and is 
now fully written and supported in Java.

The Perl 6 extension for quantified capturing groups will have a slow 
adoption, as long as Perl will continue the slow single-state NFA 
approach with excessive backtracking, instead of the Aho/Sethi/Ullman 
(ASU) approach (that some are attributing to Thomson due to the article 
in 2007, but this is false) using simultaneously active states. But 
anyway, it already exists (and Perl developers are already working on 
rewriting the engine using the ASU approach).

But my suggstion is much more general, as it should not just apply to 
quantified capturing groups, but to any capturing group that is part of 
a subexpression which is quantified.

And the way I specified it, it does not depend on the way the engine is 
written (whever it uses a single-state NFA or multi-state NFA or 
generates and uses a DFA transition state with single-state like in 
Yacc/Bison), because capturing groups are just used to store position 
pairs, and regexp engines already have to count them for effectively 
matching the greedy or non-greedy quantifiers, so this immediately 
provides a usable index for storing at successive positions in a 
numbered array for captured groups.

The simple test case is effectively to try to match /(aa?)*a+/ with 
strings longer than a few dozens of 'a'.

Umm.... I saif that the attribution to Thompson was wrong, in fact it 
was correct. Thompson designed and documented the algorithm in 1968, 
long before the Aho/Seti/Ullman green book... so the algorithm is more 
than 40 years old, and still not in Python, Perl and PCRE (but it is 
present in GNU awk...)

The paper published in swtch.com is effectively written in 2007, but its 
conclusions are perfectly valid. The interesting aspect of this paper is 
that it demonstrates that the Thompson's multi-state NFA approach is 
still the best one, and better than what Perl, PCRE (and PHP), Python, 
Ruby and others are using, but that it can be also optimized further by 
caching the DFA construction "on the fly" (see the blue curve on the 
displayed diagram) while parsing the the already precompiled multi-state 
NFA.

The cache for DFA states will fill up while matching the regexp against 
actual strings, so it will be much faster (and much less memory-and-
time-greedy than generating the full DFA transition table at compilation 
time like in Bison/Yacc).

However the paper still does not discusses how to make the DFA states 
cache limited in size. Notably because the longer the input text will 
be, the more the DFA cache will contain DFA states. One simple rule is 
to limit the number of cached DFA states, and then to allow all stored 
transitions to go all multiple-states in the NFA, and optionally to a 
single DFA state in the cache.

Then the DFA cache can be used in a LIFO manner, to purge it 
automatically from unused states, in order to reuse them (for caching 
another new DFA state which is still not present in the cache, when the 
cache has reached its maximum size): if this occurs, the other existing 
DFA states that point to it must be cleaned (their DFA state pointer or 
reference, stored in their NFA or DFA transitions, must be cleared/set 
to null, so that they will only contain the list of pointers to outgoing 
NFA states). The problem is how to look for a multistate in the DFA 
cache: this requires some fast lookup, but this can be implemented in a 
fast way using hash tables (by hashing the list of NFA states 
represented in the DFA state).

Apparently, GNU awk does not use the cached DFA approach: it just uses 
the NFA directly when the input text is lower than two dozens of 
characters, then it builds the full DFA as soon as the input text 
becomes larger (this explains the sudden, but moderate increase of 
time). But I've seen that GNU awk has the defect of this unlimited DFA 
generation approach: its excessive use of memory when the input text 
increases, because the number of DFA states added to the cache is 
contantly growing with the input, and the time to match each characer 
from the input slowly increases too. At some point, it will crash and 
exit due to memory limits exhaustion, when no more DFA states can be 
stored. That's why the DFA cache MUST be maintained under some level.

I'll try to implement this newer approach first in Java (just because I 
better know this language than Python, and beacause I think it is more 
solid in terms of type-safety, so it can reduce the number of bugs to 
correct before getting something stable).

In Java, there's a clean way to automatically cleanup objects from 
collections, when they are no longer needed: you just need to use weak 
references (the garbage collector will automatically cleanup the older 
objects, when needed). But this approach is not easy to port, and in 
fact, if it can effectively solve some problems, it will still not 
forbif the cache to use up to the maximum VM size. for performance 
reasons, I see little interest in storing more than about 1 million DFA 
states in the cache (also because the hash table that would be used 
would be less efficient when looking up for the key of a NFA multi-state 
where the DFA state is stored). So I will probably not use weak 
references, but will first use a maximum size (even if weak references 
could help maintain the cache at even lower bounds than the allowed 
maximum, if VM memory size is more constrained: it is a good idea in all 
Java programs to allow caches introduced only for performance reasons to 
also collaborate with the garbage collector, in order to avoid the 
explosion of all caches used in various programs or libraries). I don't 
know if Python supports the concept of weak references for handling 
performance caches.

May be I'll port it later in Python, but don't expect that I'll port it 
to C/C++ (as a replacement of PCRE), because I now hate these unsafe 
languages despite I have practiced them for many years: others would do 
that for me, when I'll have published my Java implementation.

I would find this functionality very useful. While I agree that it's often simpler to extract the relevant information in several steps, there are situations in which I'd prefer to do it all in one go.

The application I'm writing at the moment needs to extract metadata from text files. This metadata actually appears as text at the top of each file. For example:

title: Example title
tags: Django, Python, regular expressions

Example title
=============

Here is the first paragraph.

I had expected something like this to get the job done:

meta = re.match(r'(?ms)(?:^(\S+):\s*(.*?)$\n)+^\s*$', contents_of_file)

Ideally in this case, meta.groups() would return:

('title', 'Example title', 'tags', 'Django, Python, regular expressions')

Earlier this week I discovered that .Net supports repeated capture and its API suggested a much cleaner approach than what Perl offered, so I'll be adding it to the regex module at:

    http://pypi.python.org/pypi/regex

The new methods will follow the example of .group() & co.

Given a match object m, m.group(i) returns the last match of group i (or None if there's no match), so I'll be adding m.captures(i) to return a tuple of the captures (an empty tuple if there's no match). I'll also be adding m.starts(i), m.ends(i) and m.spans(i).

The issue for this work is #2636.

Units tests are welcome.

Can this be closed as has happened with numerous other issues as a result of work done on the new regex module via #2636?