How can I search and replace a term with brackets in Python without catastrophic backtracking?
Question: I am currently trying to find terms like these (LaTeX definitions)

    
    
    \def\fB{\mathfrak{B}}
    

and then remove the complete term `\def\fB{\mathfrak{B}}` as well as replacing
`\fB` by `\mathfrak{B}`.

I came up with the following RegEx to do so:

    
    
    curly = "(?:\{(?:.*)?\})"  # make sure that number of brackets is correct
    target = "([^\{]*?"+curly+"*)"
    search = r"(\\[A-Za-z][A-Za-z0-9]*)"
    defcommand = re.compile(r"\\def" + search + "\{" + target + "+\}")
    

But when I run this there seems to happen [catastrophic
backtracking](http://www.regular-expressions.info/catastrophic.html) as the
following minimal (not) working example shows:

    
    
    #!/usr/bin/env python
    # -*- coding: utf-8 -*-
    
    import re
    
    text = r"""
    \newcommand*{\xindex}[1]{%
      \stepcounter{indexanchor}% make anchor unique
      \def\theindexterm{#1}%
      \edef\doindexentry{\noexpand\index
        {\expandonce\theindexterm|indexanchor{index-\theindexanchor}}}%
      \raisebox{\baselineskip}{\hypertarget{index-\theindexanchor}%
        {\doindexentry}}%
    }
    
    
    \def\fB{\mathfrak{B}}%Für Basis
    \def\calS{\mathcal{S}}%Für Subbasis
    \def\fT{\mathfrak{T}}%Für Topologie
    \def\fU{\mathfrak{U}}%Für Topologie
    
    \newlist{aufgabeenum}{enumerate}{1}
    \setlist[aufgabeenum]{label=(\alph*),ref=\textup{\theaufgabe~(\alph*)}}
    \crefalias{aufgabeenumi}{aufgabe}
    
    % Commands for local abbreviations
    """
    
    
    def print_matched_groups(m):
        print("number of groups: %i" % defcommand.groups)
        for i in range(defcommand.groups):
            print("group %i: %s" % (i, m.group(i)))
        print("done with print_matched_groups")
    
        curly = "(?:\{(?:.*)?\})"
        target = "([^\{]*?"+curly+"*)"
        search = r"(\\[A-Za-z][A-Za-z0-9]*)"
        defcommand = re.compile(r"\\def"+search+"\{"+target+"+\}")
    
    for m in defcommand.finditer(text):
        print_matched_groups(m)
    print("finished")
    

How can I


Answer: I've just found a practical solution. As I know that the nesting will not be
very deep, I can use this information to make the regex faster:

    
    
    curly = "(?:\{(?:.*)?\})"  # make sure that number of brackets is correct
    target = "([^\{]*?"+curly+"{0, 3})"  # here is the change
    search = r"(\\[A-Za-z][A-Za-z0-9]*)"
    defcommand = re.compile(r"\\def" + search + "\{" + target + "+\}")
    

