The following code (run under WinNT):

    sre.search('x.*?z', 'x%sx' % ("y" * 16037,))

raises "RuntimeError: maximum recursion limit exceeded".

sre doesn't seem to be able to do a minimal match across more than ~16K characters. I think pcre can match something like 2**32 characters, so this is an area where the sre behavior deviates radically from pcre. I have lots of code that breaks with this limit. Yikes! Can something be done?

While trying to come up with the magic number of characters that cause a minimal match to fail, I ran this interactive session 
(I'm not sure if this means anything or if it's a quirk of the interactive interpreter.)

C:\>python
Python 2.0b2 (#6, Sep 26 2000, 14:59:21) [MSC 32 bit (Intel)] on win32
Type "copyright", "credits" or "license" for more information.

>>> import sre

>>> sre.search('x.*?x', 'x%sx' % ('@'*16035,))
<SRE_Match object at 009D7FC0>

>>> sre.search('x.*?x', 'x%sx' % ('@'*16036,))
<SRE_Match object at 009D7040>

>>> sre.search('x.*?x', 'x%sx' % ('@'*16037,))      <-- first failure
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "D:\Python20\lib\sre.py", line 47, in search
    return _compile(pattern, flags).search(string)
RuntimeError: maximum recursion limit exceeded

>>> sre.search('x.*?x', 'x%sx' % ('@'*16037,))      <-- now it works (?!)
<SRE_Match object at 009D7630>

>>> sre.search('x.*?x', 'x%sx' % ('@'*16038,))
<SRE_Match object at 009D7040>

>>>

>>> sre.search('x.*?x', 'x%sx' % ('@'*16166,))
<SRE_Match object at 009D7A60>

>>> sre.search('x.*?x', 'x%sx' % ('@'*16167,))  <-- here it fails again
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "D:\Python20\lib\sre.py", line 47, in search
    return _compile(pattern, flags).search(string)
RuntimeError: maximum recursion limit exceeded

>>> sre.search('x.*?x', 'x%sx' % ('@'*16167,))  <-- continues to fail
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "D:\Python20\lib\sre.py", line 47, in search
    return _compile(pattern, flags).search(string)
RuntimeError: maximum recursion limit exceeded

Any comments, Fredrik???

I am getting killed by this same bug!
#!/usr/bin/env python2.0
import re

output = """Using 

== Data Table ==
s	m:d	mb
3.300000	0.000104772187944365	-1.23330767339032e-15
3.200000	0.000103862130408037	-1.23481086168441e-15
3.100000	0.000102831826202984	-1.23643366708223e-15
3.000000	0.000101671354638586	-1.23819069775402e-15
2.900000	0.000100370082245968	-1.24009908383179e-15
2.800000	9.89166376398503e-05	-1.24217904419247e-15
2.700000	9.72988932844521e-05	-1.24445461136295e-15
2.600000	9.55039568198016e-05	-1.24695456774457e-15
2.500000	9.3518175238995e-05	-1.24971366756711e-15
2.400000	9.13271559565959e-05	-1.25277425005882e-15
2.300000	8.89158096852735e-05	-1.25618839559713e-15
2.200000	8.62684210547775e-05	-1.26002084671538e-15
2.100000	8.33687540802062e-05	-1.26435302405962e-15
2.000000	8.02002009414518e-05	-1.26928863786894e-15
1.900000	7.67459841300842e-05	-1.27496167015724e-15
1.800000	7.29894239935539e-05	-1.28154795600633e-15
1.700000	6.89142864097651e-05	-1.28928236065365e-15
1.600000	6.45052296412595e-05	-1.29848488989922e-15
1.500000	5.97483776126083e-05	-1.30960148694006e-15
1.400000	5.46320649249439e-05	-1.32326977154928e-15
1.300000	4.91478435825781e-05	-1.3404286750276e-15
1.200000	4.32919623998454e-05	-1.36250830892367e-15
1.100000	3.70678871330223e-05	-1.39177202537724e-15
1.000000	3.04915786576429e-05	-1.43195494399345e-15
0.900000	2.36052666077545e-05	-1.48947100843164e-15
0.800000	1.65202853321069e-05	-1.57551564136398e-15
0.700000	9.56073716566518e-06	-1.70791288744525e-15
0.600000	3.67125710597e-06	-1.89923336361812e-15
0.500000	6.00021904261974e-07	-2.08381565027337e-15
0.400000	4.27864345038415e-08	-2.14973379503184e-15
0.300000	2.5741570279509e-09	-2.15852923041729e-15
0.200000	1.60325700603365e-10	-2.15762110254924e-15
0.100000	1.10181009347061e-11	-2.15430351925385e-15
0.000000	9.18460199298261e-13	-2.14607756126421e-15
-0.100000	8.2907448480307e-14	-2.13154544128925e-15
-0.200000	9.49291906644266e-15	-2.09562596113738e-15
-0.300000	2.57398712712903e-15	-1.89144055818718e-15
-0.400000	1.23896929747012e-15	-1.18482371296596e-15
-0.500000	4.77088843470797e-16	-4.74259070979461e-16
3.300000	0.000725333230235404	-1.60279744215745e-14
3.200000	0.000698989627849489	-1.57983897758426e-14
3.100000	0.000672395787137216	-1.55721529060957e-14
3.000000	0.000645566845212758	-1.53549883971193e-14
2.900000	0.000618516906916818	-1.51624220311135e-14
2.800000	0.000591259277466284	-1.50347782956977e-14
2.700000	0.000563806714724985	-1.5069525306854e-14
2.600000	0.000536171704020601	-1.54848062262748e-14
2.500000	0.000508366761845922	-1.67334737461837e-14
2.400000	0.000480404778779427	-1.96904798125589e-14
2.300000	0.00045229941701671	-2.59347024715496e-14
2.200000	0.000424065584744255	-3.81354821168744e-14
2.100000	0.000395720019338978	-6.05316531752639e-14
2.000000	0.000367282025836478	-9.9457021513997e-14
1.900000	0.000338774439198852	-1.63825993533288e-13
1.800000	0.000310224913488982	-2.65456611717139e-13
1.700000	0.000281667696431468	-4.19089961445906e-13
1.600000	0.000253146138686846	-6.4197984099406e-13
1.500000	0.000224716340367884	-9.52983499747302e-13
1.400000	0.00019645260393449	-1.37117106753005e-12
1.300000	0.000168455842857815	-1.9140171376089e-12
1.200000	0.000140866992561325	-2.5949957749272e-12
1.100000	0.000113889209694637	-3.419066099784e-12
1.000000	8.78261401150504e-05	-4.36958009251635e-12
0.900000	6.31506490822963e-05	-5.36461118003355e-12
0.800000	4.06312963119592e-05	-6.12577475587495e-12
0.700000	2.15481889941145e-05	-5.92418822150058e-12
0.600000	7.87604367966821e-06	-3.80859906972703e-12
0.500000	1.3904896761789e-06	-9.79870732426348e-13
0.400000	1.06064890626322e-07	-9.39992702457847e-14
0.300000	6.34950130197645e-09	-1.65503941397823e-14
0.200000	3.88292805625561e-10	-1.16204226732226e-14
0.100000	2.57865399432747e-11	-1.11870703136006e-14
0.000000	2.05458930149398e-12	-1.09482596289954e-14
-0.100000	1.85578779234532e-13	-1.06729449780495e-14
-0.200000	2.5577583052963e-14	-1.02232392679007e-14
-0.300000	1.05769385343133e-14	-9.2322860676878e-15
-0.400000	8.00273522170935e-15	-7.88228414475344e-15
-0.500000	6.51965630664677e-15	-6.50815076902941e-15
3.300000	0.000778073989265561	-1.65574096734398e-07
3.200000	0.00074963150963251	-1.92244746339178e-07
3.100000	0.000721015586364691	-2.21197891556889e-07
3.000000	0.000692226507232058	-2.52254070463242e-07
2.900000	0.000663264988754168	-2.85152554002688e-07
2.800000	0.000634132321079485	-3.19546222567145e-07
2.700000	0.000604830546549725	-3.54998299569146e-07
2.600000	0.000575362679604795	-3.90981285317844e-07
2.500000	0.000545732977654778	-4.26878409205096e-07
2.400000	0.000515947275272665	-4.61987879332959e-07
2.300000	0.000486013397947319	-4.95530155074015e-07
2.200000	0.000455941677304999	-5.26658398699649e-07
2.100000	0.000425745598153737	-5.54472176489517e-07
2.000000	0.000395442620520435	-5.78034377120716e-07
1.900000	0.000365055239615154	-5.96391194651538e-07
1.800000	0.000334612377612625	-6.0859488246625e-07
1.700000	0.000304151250425071	-6.13728816719563e-07
1.600000	0.000273719932661724	-6.1093419812057e-07
1.500000	0.000243380977243086	-5.99437433988553e-07
1.400000	0.000213216675616044	-5.78576796961394e-07
1.300000	0.000183336956663227	-5.47826196051382e-07
1.200000	0.000153891700661593	-5.06812695554088e-07
1.100000	0.000125090796710056	-4.55323667088038e-07
1.000000	9.7238530664174e-05	-3.9330616509577e-07
0.900000	7.07959411929754e-05	-3.20910962327376e-07
0.800000	4.64992533700793e-05	-2.38877973057319e-07
0.700000	2.55795422135307e-05	-1.50458199069334e-07
0.600000	1.00314893206752e-05	-6.74343626580743e-08
0.500000	2.00947524041218e-06	-1.48839482947924e-08
0.400000	1.67232105200131e-07	-1.2816627677716e-09
0.300000	1.00809637284154e-08	-7.82708572696571e-11
0.200000	6.12196843592758e-10	-4.83619605089934e-12
0.100000	4.0027953235145e-11	-3.39466185939354e-13
0.000000	3.1163322565507e-12	-4.38427713973686e-14
-0.100000	2.82036148373174e-13	-2.01235539818538e-14
-0.200000	4.04726306794353e-14	-1.75747562532315e-14
-0.300000	1.83397331593843e-14	-1.63366924660679e-14
-0.400000	1.50709750319906e-14	-1.48901998089388e-14
-0.500000	1.34240392889815e-14	-1.34063683071726e-14
3.300000	0.000104772187944365	-1.23330767339032e-15
3.200000	0.000103862130408037	-1.23481086168441e-15
3.100000	0.000102831826202984	-1.23643366708223e-15
3.000000	0.000101671354638586	-1.23819069775402e-15
2.900000	0.000100370082245968	-1.24009908383179e-15
2.800000	9.89166376398503e-05	-1.24217904419247e-15
2.700000	9.72988932844521e-05	-1.24445461136295e-15
2.600000	9.55039568198016e-05	-1.24695456774457e-15
2.500000	9.3518175238995e-05	-1.24971366756711e-15
2.400000	9.13271559565959e-05	-1.25277425005882e-15
2.300000	8.89158096852735e-05	-1.25618839559713e-15
2.200000	8.62684210547775e-05	-1.26002084671538e-15
2.100000	8.33687540802062e-05	-1.26435302405962e-15
2.000000	8.02002009414518e-05	-1.26928863786894e-15
1.900000	7.67459841300842e-05	-1.27496167015724e-15
1.800000	7.29894239935539e-05	-1.28154795600633e-15
1.700000	6.89142864097651e-05	-1.28928236065365e-15
1.600000	6.45052296412595e-05	-1.29848488989922e-15
1.500000	5.97483776126083e-05	-1.30960148694006e-15
1.400000	5.46320649249439e-05	-1.32326977154928e-15
1.300000	4.91478435825781e-05	-1.3404286750276e-15
1.200000	4.32919623998454e-05	-1.36250830892367e-15
1.100000	3.70678871330223e-05	-1.39177202537724e-15
1.000000	3.04915786576429e-05	-1.43195494399345e-15
0.900000	2.36052666077545e-05	-1.48947100843164e-15
0.800000	1.65202853321069e-05	-1.57551564136398e-15
0.700000	9.56073716566518e-06	-1.70791288744525e-15
0.600000	3.67125710597e-06	-1.89923336361812e-15
0.500000	6.00021904261974e-07	-2.08381565027337e-15
0.400000	4.27864345038415e-08	-2.14973379503184e-15
0.300000	2.5741570279509e-09	-2.15852923041729e-15
0.200000	1.60325700603365e-10	-2.15762110254924e-15
0.100000	1.10181009347061e-11	-2.15430351925385e-15
0.000000	9.18460199298261e-13	-2.14607756126421e-15
-0.100000	8.2907448480307e-14	-2.13154544128925e-15
-0.200000	9.49291906644266e-15	-2.09562596113738e-15
-0.300000	2.57398712712903e-15	-1.89144055818718e-15
-0.400000	1.23896929747012e-15	-1.18482371296596e-15
-0.500000	4.77088843470797e-16	-4.74259070979461e-16
3.300000	0.000725333230235404	-1.60279744215745e-14
3.200000	0.000698989627849489	-1.57983897758426e-14
3.100000	0.000672395787137216	-1.55721529060957e-14
3.000000	0.000645566845212758	-1.53549883971193e-14
2.900000	0.000618516906916818	-1.51624220311135e-14
2.800000	0.000591259277466284	-1.50347782956977e-14
2.700000	0.000563806714724985	-1.5069525306854e-14
2.600000	0.000536171704020601	-1.54848062262748e-14
2.500000	0.000508366761845922	-1.67334737461837e-14
2.400000	0.000480404778779427	-1.96904798125589e-14
2.300000	0.00045229941701671	-2.59347024715496e-14
2.200000	0.000424065584744255	-3.81354821168744e-14
2.100000	0.000395720019338978	-6.05316531752639e-14
2.000000	0.000367282025836478	-9.9457021513997e-14
1.900000	0.000338774439198852	-1.63825993533288e-13
1.800000	0.000310224913488982	-2.65456611717139e-13
1.700000	0.000281667696431468	-4.19089961445906e-13
1.600000	0.000253146138686846	-6.4197984099406e-13
1.500000	0.000224716340367884	-9.52983499747302e-13
1.400000	0.00019645260393449	-1.37117106753005e-12
1.300000	0.000168455842857815	-1.9140171376089e-12
1.200000	0.000140866992561325	-2.5949957749272e-12
1.100000	0.000113889209694637	-3.419066099784e-12
1.000000	8.78261401150504e-05	-4.36958009251635e-12
0.900000	6.31506490822963e-05	-5.36461118003355e-12
0.800000	4.06312963119592e-05	-6.12577475587495e-12
0.700000	2.15481889941145e-05	-5.92418822150058e-12
0.600000	7.87604367966821e-06	-3.80859906972703e-12
0.500000	1.3904896761789e-06	-9.79870732426348e-13
0.400000	1.06064890626322e-07	-9.39992702457847e-14
0.300000	6.34950130197645e-09	-1.65503941397823e-14
0.200000	3.88292805625561e-10	-1.16204226732226e-14
0.100000	2.57865399432747e-11	-1.11870703136006e-14
0.000000	2.05458930149398e-12	-1.09482596289954e-14
-0.100000	1.85578779234532e-13	-1.06729449780495e-14
-0.200000	2.5577583052963e-14	-1.02232392679007e-14
-0.300000	1.05769385343133e-14	-9.2322860676878e-15
-0.400000	8.00273522170935e-15	-7.88228414475344e-15
-0.500000	6.51965630664677e-15	-6.50815076902941e-15
"""

re.search("== Data Table ==\n(.*?)\n(.*?)\s*$", output, re.S)