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]

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]

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]

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]

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]

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]

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

 

[Fredrik Lundh]

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.parse(x).getwidth()" on a subexpression, to
get the shortest/longest possible match.
(1, 65535)

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

</F>

 

[Fredrik Lundh]

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>

 

[Diez B. Roggisch]

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

 

[Joerg Schuster]

what's the difference?

One could suspect that re.search() first matches with a greedy "|", then
stores all the matches of all parts of the disjunction in the
re-object and then returns the first one.

Jörg

 

[Joerg Schuster]

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

(1, 65535)

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

</F>

Thanks for the tip.

 

[Joerg Schuster]

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

Thanks for the tip.