leftmost longest match (of disjunctions)

[Joerg Schuster]

Hello,

The program given below returns the lines:

a
ab

Is there a way to use python regular expressions such that the program
would return the following lines?

ab
ab

############### ############### ############### ############### ############

import re

rx1 = re.compile("(a| ab)")
rx2 = re.compile("(ab |a)")

out1 = rx1.search("ab" )
out2 = rx2.search("ab" )

print out1.group(1)
print out2.group(1)

############### ############### ############### ############### ############

Jörg

[Peter Hansen]

Joerg Schuster wrote:

The program given below returns the lines:

a
ab

Is there a way to use python regular expressions such that the program
would return the following lines?

ab
ab

############### ############### ############### ############### ############

import re

rx1 = re.compile("(a| ab)")
rx2 = re.compile("(ab |a)")

Have you checked the documentation for "re"?

It reads:
"|" A|B, where A and B can be arbitrary REs, creates a regular expression
that will match either A or B. An arbitrary number of REs can be separated
by the "|" in this way. This can be used inside groups (see below) as well.
As the target string is scanned, REs separated by "|" are tried from left to
right. When one pattern completely matches, that branch is accepted. This
means that once A matches, B will not be tested further, even if it would
produce a longer overall match. In other words, the "|" operator is never
greedy.

------

Seems pretty clear and explicit to me. Your example is basically a working
proof of the above code, so I'm not sure what you were expecting differently.

-Peter

[Joerg Schuster]

Peter Hansen <pe***@engcorp. com> writes:

produce a longer overall match. In other words, the "|" operator is never
greedy.

O.k. Thanks for pointing this out. Maybe I should have formulated my
question differently: Is there a trick (be it dirty or not) to make
"|" greedy in python?
Jörg

[Joerg Schuster]

Peter Hansen <pe***@engcorp. com> writes:

produce a longer overall match. In other words, the "|" operator is never
greedy.

O.k. Thanks for pointing this out. Maybe I should have formulated my
question differently: Is there a trick (be it dirty or not) to make
"|" greedy in python?
Jörg

[Padraig]

Joerg Schuster wrote:

Peter Hansen <pe***@engcorp. com> writes:

produce a longer overall match. In other words, the "|" operator is never
greedy.

O.k. Thanks for pointing this out. Maybe I should have formulated my
question differently: Is there a trick (be it dirty or not) to make
"|" greedy in python?

sort the re by size first?

Pádraig.

[Joerg Schuster]

Pa*****@Linux.i e writes:

Joerg Schuster wrote:

Peter Hansen <pe***@engcorp. com> writes:

produce a longer overall match. In other words, the "|" operator
is never greedy.

O.k. Thanks for pointing this out. Maybe I should have formulated my
question differently: Is there a trick (be it dirty or not) to make
"|" greedy in python?

sort the re by size first?

The point is not to get the match of the longest part of the
disjunction, but to get the match of that part of the disjunction
which is the longest one. (The match of ".*" may be much longer than
the match of "abc", although the latter regex contains more
characters.)

Jörg

[Joerg Schuster]

Joerg Schuster <[e-mail]> writes:

Pa*****@Linux.i e writes:

Joerg Schuster wrote:

Peter Hansen <pe***@engcorp. com> writes:

> produce a longer overall match. In other words, the "|" operator
> is never greedy.
O.k. Thanks for pointing this out. Maybe I should have formulated my
question differently: Is there a trick (be it dirty or not) to make
"|" greedy in python?

sort the re by size first?

The point is not to get the match of the longest part of the
disjunction, but to get the match of that part of the disjunction
which is the longest one. (The match of ".*" may be much longer than
the match of "abc", although the latter regex contains more
characters.)

Jörg

I should have read your mail more carefully. You wrote about sorting
the *re*, not about sorting the regex. Sorry.

Jörg

[Diez B. Roggisch]

Joerg Schuster wrote:

Peter Hansen <pe***@engcorp. com> writes:

produce a longer overall match. In other words, the "|" operator is
never greedy.

O.k. Thanks for pointing this out. Maybe I should have formulated my
question differently: Is there a trick (be it dirty or not) to make
"|" greedy in python?

I don't think so - as regexps are finite state automata, their capabilities
are limited to what these machines can do. So they can't backtrack to a
part of the disjunction that was a shorter match if the longer match
suddenly will fail. Consider this example:

rex: a|abc

string: abd

If the state-machine was greedy, it would follow the second path and fail.

The only thing you can do to avoid is is to split your disjunctions and
search separately, and afterwards takt the longest part. That could be done
using a small grammar, that allows you to detect the disjunctions and
create separate rexes for it.

Diez

[Fredrik Lundh]

Joerg Schuster wrote:

I should have read your mail more carefully. You wrote about sorting
the *re*, not about sorting the regex. Sorry.

what's the difference?

</F>

[Fredrik Lundh]

Joerg Schuster wrote:

O.k. Thanks for pointing this out. Maybe I should have formulated my
question differently: Is there a trick (be it dirty or not) to make
"|" greedy in python?

sort the re by size first?

The point is not to get the match of the longest part of the
disjunction, but to get the match of that part of the disjunction
which is the longest one. (The match of ".*" may be much longer
than the match of "abc", although the latter regex contains more
characters.)

you can use "sre_parse.pars e(x).getwidth() " on a subexpression, to
get the shortest/longest possible match.

from sre_parse import parse
parse("a?").get width() (0, 1) parse("ab").get width() (2, 2) parse(".+").get width()

(1, 65535)

(where >=65535 should be interpreted as "any number")

</F>