Greedy versus Non-Greedy matching in Python re
Question: Please help me to discover whether this is a bug in Python (2.6.5), in my
competence at writing regexes, or in my understanding of pattern matching.

(I accept that a possible answer is "Upgrade your Python".)

I'm trying to parse a Yubikey token, allowing for the optional extras.

When I use this regex to match a token without any optional extras (that is,
containing only the stuff that matches the two capture groups), the match
fails:

    
    
    r'^\t?[^a-z0-9]?([cbdefghijklnrtuv1-8]{0,32})\t?([cbdefghijklnrtuv1-8]{32})\t?\r?\n?$'
    

However, if I make the first group non-greedy:

    
    
    r'^\t?[^a-z0-9]?([cbdefghijklnrtuv1-8]{0,32}?)\t?([cbdefghijklnrtuv1-8]{32})\t?\r?\n?$'
    

it succeeds.

So, OK, it's working, but I would have thought that the only difference in end
result between these two regexes would be performance.

Both Expresso and Regex Coach like both patterns.

What have I missed?

* * *

Here are two of the strings I'm testing with.

No optional extras (the ones that can fail):

    
    
    "vvbrentlnccnhgfgrtetilbvckjcegblehfvbihrdcui"
    

With optional extras (haven't failed so far; actual tabs are shown here as
"_"):

    
    
    "_!_8R5Gkruvfgheufhcnhllchgrfiutujfh_"
    "_!1U4Knivdgvkfthrd_brvejhudrdnbunellrjjkkccfnggbdng_"
    

* * *

I've tried to reproduce it using the suggestion from Alex Martelli, and it
doesn't fail in the raw Python environment, so I'm going to revisit my code
(I'm actually hacking on yubikey-python); I'll report back in a day or so.

* * *

My apologies to everyone. I cannot reproduce the problem. When it occurred, I
was reading input via `getpass`; I suspect that an accidental foreign
keystroke got in the way.

I am going to close the question. If whoever upvoted the question wishes to
remove their vote, that is fair.

Very sorry.


Answer: I'd recommend using [yubikey-python](http://code.google.com/p/yubikey-python/)
for Python interfacing to yubikey -- but, that's a side (and strictly
pragmatical) issue;-).

In theory, there should be no cases where a choice between greedy and non-
greedy causes a RE to match in one case and fail in another -- it should only
affects what gets matched (and as you mention performance), not whether the
match succeeds at all, since REs are supposed to backtrack for the purpose.

Problem is, I cannot reproduce the problem -- I don't have a yubikey at hand
and the tests in [this file](http://code.google.com/p/yubikey-
python/source/browse/trunk/test.py) show no differences between the two REs'
match/no-match behavior.

Could you please post a couple of failing examples (where one matches and the
other one doesn't), ideally by editing your question, so I can reproduce the
problem and try to cut it down to its minimum? Sounds like there may be a RE
bug, but without reproducible cases I can't check if and when it's been fixed,
already reported, or what. Thanks!

**Edit** the OP has now posted one failing example but I still can't
reproduce:

    
    
    $ py26
    Python 2.6.5 (r265:79359, Mar 24 2010, 01:32:55) 
    [GCC 4.0.1 (Apple Inc. build 5493)] on darwin
    Type "help", "copyright", "credits" or "license" for more information.
    >>> import re
    >>> r1 = re.compile(r'^\t?[^a-z0-9]?([cbdefghijklnrtuv1-8]{0,32})\t?([cbdefghijklnrtuv1-8]{32})\t?\r?\n?$')
    >>> r2 = re.compile(r'^\t?[^a-z0-9]?([cbdefghijklnrtuv1-8]{0,32}?)\t?([cbdefghijklnrtuv1-8]{32})\t?\r?\n?$'
    ... )
    >>> nox="vvbrentlnccnhgfgrtetilbvckjcegblehfvbihrdcui"
    >>> r1.match(nox)
    <_sre.SRE_Match object at 0xcc458>
    >>> r2.match(nox)
    <_sre.SRE_Match object at 0xcc920>
    >>> 
    

i.e., match succeeds in both cases, as it should -- and that's exactly the
same 2.6.5 Python version as the OP is using. OP, pls, show the results of
this simple sequence of commands on your platform and tell us exactly what the
platform is, since it looks like a weird platform-dependent bug... thanks!

