Qual è il numero massimo di ripetizioni consentito in un'espressione regolare di Python?

Question

In Python 2.7 e 3, le seguenti opere:

>>> re.search(r"a{1,9999}", 'aaa') 
<_sre.SRE_Match object at 0x1f5d100> 

ma questo dà un errore:

>>> re.search(r"a{1,99999}", 'aaa') 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    File "/usr/lib/python2.7/re.py", line 142, in search 
    return _compile(pattern, flags).search(string) 
    File "/usr/lib/python2.7/re.py", line 240, in _compile 
    p = sre_compile.compile(pattern, flags) 
    File "/usr/lib/python2.7/sre_compile.py", line 523, in compile 
    groupindex, indexgroup 
RuntimeError: invalid SRE code 

Sembra che ci sia un limite superiore al numero di ripetizioni consentite. Questa parte della specifica dell'espressione regolare o una limitazione specifica di Python? Se specifico di Python, è il numero effettivo documentato da qualche parte e varia tra le implementazioni?

Answer 1

Un manuale rapida ricerca binaria rivelato la risposta, in particolare 65535:

>>> re.search(r"a{1,65535}", 'aaa') 
<_sre.SRE_Match object at 0x2a9a68> 
>>> 
>>> re.search(r"a{1,65536}", 'aaa') 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    File "/Library/Frameworks/Python.framework/Versions/7.3/lib/python2.7/re.py", line 142, in search 
    return _compile(pattern, flags).search(string) 
    File "/Library/Frameworks/Python.framework/Versions/7.3/lib/python2.7/re.py", line 240, in _compile 
    p = sre_compile.compile(pattern, flags) 
    File "/Library/Frameworks/Python.framework/Versions/7.3/lib/python2.7/sre_compile.py", line 523, in compile 
    groupindex, indexgroup 
OverflowError: regular expression code size limit exceeded 

Questo è discusso here:

The limit is an implementation detail. The pattern is compiled into codes which are then interpreted, and it just happens that the codes are (usually) 16 bits, giving a range of 0..65535, but it uses 65535 to represent no limit and doesn't warn if you actually write 65535.

e

The quantifiers use 65535 to represent no upper limit, so ".{0,65535}" is equivalent to ".*".

---

Grazie agli autori di i commenti sottostanti per indicare alcune altre cose:

• CPython implementa questa limitazione in _sre.c. (@LukasGraf)

• C'è una costante MAXREPEAT in sre_constants.py che contiene questo valore ripetizione max:

  >>> import sre_constants 
  >>> 
  >>> sre_constants.MAXREPEAT 
  65535 
  

  (@MarkkuK e @hcwhsa.)