From 7829e5661c37fd4986b8fc5ca29f5e95ec5783bc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Martin=20v=2E=20L=C3=B6wis?= Date: Sat, 3 May 2003 10:57:53 +0000 Subject: Patch #731514: Update recursion documentation to mention simple recursion. --- Doc/lib/libre.tex | 25 ++++++++++++++----------- 1 file changed, 14 insertions(+), 11 deletions(-) diff --git a/Doc/lib/libre.tex b/Doc/lib/libre.tex index c2c7a6f..cf05441 100644 --- a/Doc/lib/libre.tex +++ b/Doc/lib/libre.tex @@ -896,15 +896,16 @@ The equivalent regular expression would be (\S+) - (\d+) errors, (\d+) warnings \end{verbatim} -\leftline{\strong{Avoiding backtracking}} +\leftline{\strong{Avoiding recursion}} -If you create regular expressions that require the engine to perform a lot -of backtracking, you may encounter a RuntimeError exception with the message -\code{maximum recursion limit exceeded}. For example, +If you create regular expressions that require the engine to perform a +lot of recursion, you may encounter a RuntimeError exception with +the message \code{maximum recursion limit} exceeded. For example, \begin{verbatim} ->>> s = "<" + "that's a very big string!"*1000 + ">" ->>> re.match('<.*?>', s) +>>> import re +>>> s = 'Begin ' + 1000*'a very long string ' + 'end' +>>> re.match('Begin (\w| )*? end', s).end() Traceback (most recent call last): File "", line 1, in ? File "/usr/local/lib/python2.3/sre.py", line 132, in match @@ -912,8 +913,10 @@ Traceback (most recent call last): RuntimeError: maximum recursion limit exceeded \end{verbatim} -You can often restructure your regular expression to avoid backtracking. -The above regular expression can be recast as -\regexp{\textless[\textasciicircum \textgreater]*\textgreater}. As a -further benefit, such regular expressions will run faster than their -backtracking equivalents. +You can often restructure your regular expression to avoid recursion. + +\versionadded[Simple uses of the \regexp{*?} pattern are now +special-cased to avoid recursion. Thus, the above regular expression +can avoid recursion by being recast as \regexp{Begin [a-zA-Z0-9_ ]*?end}. +As a further benefit, such regular expressions will run faster than +their recursive equivalents.]{2.3} -- cgit v0.12