re module non-greedy matches broken

[lothar]

re:
4.2.1 Regular Expression Syntax
http://docs.python.org/lib/re-syntax.html

*?, +?, ??
Adding "?" after the qualifier makes it perform the match in non-greedy or
minimal fashion; as few characters as possible will be matched.

the regular expression module fails to perform non-greedy matches as
described in the documentation: more than "as few characters as possible"
are matched.

this is a bug and it needs to be fixed.

examples follow.

lothar@erda /ntd/vl
$ cat vwre.py
#! /usr/bin/env python

import re

vwre = re.compile("V.*?W")
vwlre = re.compile("V.*?WL")

if __name__ == "__main__":

newdoc = "V1WVVV2WWW"
vwli = re.findall(vwre, newdoc)
print "vwli[], expect", ['V1W', 'V2W']
print "vwli[], return", vwli

newdoc = "V1WLV2WV3WV4WLV5WV6WL"
vwlli = re.findall(vwlre, newdoc)
print "vwlli[], expect", ['V1WL', 'V4WL', 'V6WL']
print "vwlli[], return", vwlli

lothar@erda /ntd/vl
$ python vwre.py
vwli[], expect ['V1W', 'V2W']
vwli[], return ['V1W', 'VVV2W']
vwlli[], expect ['V1WL', 'V4WL', 'V6WL']
vwlli[], return ['V1WL', 'V2WV3WV4WL', 'V5WV6WL']

lothar@erda /ntd/vl
$ python -V
Python 2.3.3

[André Malo]

* lothar wrote:

re:
4.2.1 Regular Expression Syntax
http://docs.python.org/lib/re-syntax.html

*?, +?, ??
Adding "?" after the qualifier makes it perform the match in non-greedy
or
minimal fashion; as few characters as possible will be matched.

the regular expression module fails to perform non-greedy matches as
described in the documentation: more than "as few characters as possible"
are matched.

this is a bug and it needs to be fixed.

The documentation is just incomplete. Non-greedy regexps still start
matching the leftmost. So instead the longest of the leftmost you get the
shortest of the leftmost. One may consider this as a documentation bug,
yes.

nd
--
# André Malo, <http://www.perlig.de/> #

[lothar]

this response is nothing but a description of the behavior i reported.

as to whether this behaviour was intended, one would have to ask the module
writer about that.
because of the statement in the documentation, which places no qualification
on how the scan for the shortest possible match is to be done, my guess is
that this problem was overlooked.

to produce a non-greedy (minimal length) match it is required that the start
of the non-greedy part of the match repeatedly be moved right with the last
match of the left-hand part of the pattern (preceding the .*?).

why would someone want a non-greedy (minimal length) match that was not
always non-greedy (minimal length)?

"André Malo" <au********@g-kein-spam.com> wrote in message
news:20*****************@news.perlig.de...
* lothar wrote:

re:
4.2.1 Regular Expression Syntax
http://docs.python.org/lib/re-syntax.html

*?, +?, ??
Adding "?" after the qualifier makes it perform the match in non-greedy
or
minimal fashion; as few characters as possible will be matched.

the regular expression module fails to perform non-greedy matches as
described in the documentation: more than "as few characters as possible"
are matched.

this is a bug and it needs to be fixed.

The documentation is just incomplete. Non-greedy regexps still start
matching the leftmost. So instead the longest of the leftmost you get the
shortest of the leftmost. One may consider this as a documentation bug,
yes.

nd
--
# André Malo, <http://www.perlig.de/> #

[André Malo]

* "lothar" <lo****@ultimathule.nul> wrote:

this response is nothing but a description of the behavior i reported.
Then you have not read my response carefully enough.
as to whether this behaviour was intended, one would have to ask the module
writer about that.
No, I've responded with a view on regexes, not on the module. That is the way
_regexes_ work. Non-greedy regexes do not match the minimal-length at all, they
are just ... non-greedy (technically the backtracking just stacks the longest
instead of the shortest). They *may* match the shortest match, but it's a
special case. Therefore I've stated that the documentation is incomplete.

Actually your expectations go a bit beyond the documentation. From a certain
point of view (matches always start most left) the matches you're seeing
*are* the minimal-length matches.
because of the statement in the documentation, which places no qualification ^^^^^^^^^^^^^^^^
that's the point.
on how the scan for the shortest possible match is to be done, my guess is
that this problem was overlooked.

In the docs, yes. But buy yourself a regex book and learn for yourself ;-)
The first thing you should learn about regexes is that the source of pain
of most regex implementations is the documentation, which is very likely
to be wrong.

Finally let me ask a question:

import re
x = re.compile('<.*?>')
print x.search('<title>...</title><body>...</body>').group(0)

What would you expect to be printed out? <title> or <body>? Why?

nd

[Fredrik Lundh]

"lothar" wrote:

this is a bug and it needs to be fixed.

it's not a bug, and it's not going to be "fixed". search, findall, finditer, sub,
etc. all scan the target string from left to right, and process the first location
(or all locations) where the pattern matches.

</F>

[lothar]

how then, do i specify a non-greedy regex
<1st-pat><not-1st-pat>*?<follow-pat>

that is, such that non-greedy part <not-1st-pat>*?
excludes a match of <1st-pat>

in other words, how do i write regexes for my examples?

what book or books on regexes or with a good section on regexes would you
recommend?
Hopcroft and Ullman?
"André Malo" <au********@g-kein-spam.com> wrote in message
news:d2**********@news.web.de...

* "lothar" <lo****@ultimathule.nul> wrote:

this response is nothing but a description of the behavior i reported.
Then you have not read my response carefully enough.

as to whether this behaviour was intended, one would have to ask the module writer about that.

No, I've responded with a view on regexes, not on the module. That is the

way _regexes_ work. Non-greedy regexes do not match the minimal-length at all, they are just ... non-greedy (technically the backtracking just stacks the longest instead of the shortest). They *may* match the shortest match, but it's a
special case. Therefore I've stated that the documentation is incomplete.

Actually your expectations go a bit beyond the documentation. From a certain point of view (matches always start most left) the matches you're seeing
*are* the minimal-length matches.

because of the statement in the documentation, which places no qualification

^^^^^^^^^^^^^^^^ that's the point.

on how the scan for the shortest possible match is to be done, my guess

is that this problem was overlooked.

In the docs, yes. But buy yourself a regex book and learn for yourself ;-)
The first thing you should learn about regexes is that the source of pain
of most regex implementations is the documentation, which is very likely
to be wrong.

Finally let me ask a question:

import re
x = re.compile('<.*?>')
print x.search('<title>...</title><body>...</body>').group(0)

What would you expect to be printed out? <title> or <body>? Why?

nd

[Terry Reedy]

> what book or books on regexes

A standard is Mastering Regular Expressions, 2nd ed, by xxx (sorry, forget)

TJR

[Swaroop C H]

On Apr 4, 2005 10:06 PM, Terry Reedy <tj*****@udel.edu> wrote:

what book or books on regexes

A standard is Mastering Regular Expressions, 2nd ed, by xxx (sorry, forget)

Mastering Regular Expressions, by Jeffrey Friedl
See http://www.regex.info/

Regards,
--
Swaroop C H
Blog: http://www.swaroopch.info
Book: http://www.byteofpython.info

[lothar]

with respect to the documentation, the module is broken.

the module does not necessarily deliver a "minimal length" match for a
non-greedy pattern.
"Fredrik Lundh" <fr*****@pythonware.com> wrote in message
news:ma**************************************@pyth on.org...

"lothar" wrote:

this is a bug and it needs to be fixed.
it's not a bug, and it's not going to be "fixed". search, findall,

finditer, sub, etc. all scan the target string from left to right, and process the first location (or all locations) where the pattern matches.

</F>

[Christopher Weimann]

On 04/04/2005-04:20PM, lothar wrote:

how then, do i specify a non-greedy regex
<1st-pat><not-1st-pat>*?<follow-pat>

that is, such that non-greedy part <not-1st-pat>*?
excludes a match of <1st-pat>

jet% cat vwre2.py
#! /usr/bin/env python

import re

vwre = re.compile("V[^V]W")
vwlre = re.compile("V[^V]WL")

if __name__ == "__main__":

newdoc = "V1WVVV2WWW"
vwli = re.findall(vwre, newdoc)
print "vwli[], expect", ['V1W', 'V2W']
print "vwli[], return", vwli

newdoc = "V1WLV2WV3WV4WLV5WV6WL"
vwlli = re.findall(vwlre, newdoc)
print "vwlli[], expect", ['V1WL', 'V4WL', 'V6WL']
print "vwlli[], return", vwlli

jet% ./vwre2.py
vwli[], expect ['V1W', 'V2W']
vwli[], return ['V1W', 'V2W']
vwlli[], expect ['V1WL', 'V4WL', 'V6WL']
vwlli[], return ['V1WL', 'V4WL', 'V6WL']

[Fredrik Lundh]

"lothar" wrote:

with respect to the documentation, the module is broken.
nope.
the module does not necessarily deliver a "minimal length" match for a
non-greedy pattern.

it isn't supposed to: a regular expression describes a *set* of matching
strings, and the engine is free to return any string from that set. Python's
engine returns the *first* string it finds that belongs to the set. if you use
a non-greedy operator, the engine will return the first non-greedy match
it finds, not the overall shortest non-greedy match.

if you don't want to understand how regular expressions work, don't use
them.

</F>

[lothar]

a non-greedy match is implicitly defined in the documentation to be one such
that there is no proper substring in the return which could also match the
regex.

the documentation implies the module will return a non-greedy match.

the module does not return a non-greedy match.
"Fredrik Lundh" <fr*****@pythonware.com> wrote in message
news:ma**************************************@pyth on.org...

"lothar" wrote:

with respect to the documentation, the module is broken.
nope.

the module does not necessarily deliver a "minimal length" match for a
non-greedy pattern.

it isn't supposed to: a regular expression describes a *set* of matching
strings, and the engine is free to return any string from that set.

Python's engine returns the *first* string it finds that belongs to the set. if you use a non-greedy operator, the engine will return the first non-greedy match
it finds, not the overall shortest non-greedy match.

if you don't want to understand how regular expressions work, don't use
them.

</F>

[Fredrik Lundh]

"lothar" wrote:

a non-greedy match is implicitly defined in the documentation to be one such
that there is no proper substring in the return which could also match the
regex.
no, that's not what it says. this is what is says:

Adding "?" after the qualifier makes it perform the match in non-greedy
or minimal fashion; as few characters as possible will be matched.

note that it says "qualifier" (that is, the preceeding *, +, or ? operator). it
doesn't say that the *entire* regex should be non-greedy. it does not say
that search, findall, sub etc. should look for the shortest possible overall
match. all it says is that the preceeding operator, and that operator only,
should look for the shortest possible match, rather than the longest.
the module does not return a non-greedy match.

it does. the problem is all in your head.

</F>