Python regex problem

Question

I'm trying to match any of the following lines with a regex in python:

RAA RAA

RAA RAA / OOO OOO

RAA RAA / OOO OOO / ROCKY

These strings should always be on their own line so RAA RAA moves over there. wouldn't match.

I came up with this regex using RegExr:

^([A-Z]*([ ]?)*([A-Z]?)*([ \/]?)*)*$

This works fine to match all the different lines however it causes python to hang if it tries to match RAA RAA moves over there.

I've no idea why. Are there any regex experts that might have some insight?

Define "hangs" - how long did you wait? Also note that one-char character classes are redundant and * implies ? (for instance, ([ ]?)* is \ * sans the backslash, which I was forced to include because markdown sometimes tries too hard not to obscure non-mark'd-up text). — user395760
– user395760, Commented Apr 20, 2011 at 16:25
Are you just trying to match lines consisting only of upper case letters, forward slashes and spaces? It's not clear to me what property you are after? — YXD
– YXD, Commented Apr 20, 2011 at 16:26
You've said "match any of these (three) lines", and then given us a regexp which matches much more. Please be more specific about the requirements. — Colin Fine
– Colin Fine, Commented Apr 20, 2011 at 16:30
-1 for again giving us only specific examples and no pattern or description in a question about regex. — user3850
– user3850, Commented Apr 20, 2011 at 18:05

geekosaur · Accepted Answer · 2011-04-20 16:30:00Z

2

That regex is far too general: not only does it match more than you want, but it has so many *s that the regex matcher will constantly be pointlessly backtracking to try some other combination. I haven't tried to work the combinatorial tree, but it's at least several thousand attempts per non-matching line.

Specific is better, and making sure you don't backtrack over what you're committed to is better:

^RAA RAA(?: \/ OOO OOO(?: \/ ROCKY)?)?$

If the substrings aren't constant, you should specify them as completely as possible to avoid unnecessary backtracking.

(The ?: are another small optimization: don't record the parenthesized matches for later extraction. If you do need the substrings, my guess is you don't want the /s with them, so capture just the parts you want.)

answered Apr 20, 2011 at 16:30

geekosaur

61.9k13 gold badges127 silver badges115 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Ahmad Mageed · Accepted Answer · 2011-04-20 16:36:07Z

0

Your entire pattern is full of optional matches, which is likely causing lots of backtracking, and thus the hanging experience. Try using a mandatory match where it makes sense, such as:

^([A-Z]+([ ]?)+([A-Z])*([ /])*)*$

A cleaner pattern, without the unnecessary capturing groups, would be:

^([A-Z]+[ ]?)+([A-Z]+[ /]*)*$

Notice that the use of + instead of * ensures that at least one character must match, rather than making the entire pattern optional and taxing the regex engine.

edited Apr 20, 2011 at 16:36

answered Apr 20, 2011 at 16:25

Ahmad Mageed

96.9k20 gold badges170 silver badges177 bronze badges

1 Comment

Daniel Lloyd-Wood Over a year ago

This is definitely what I need. My regex skills are woefully inadequate so this advice is much appreciated.

Collectives™ on Stack Overflow

Python regex problem

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related