title: Recursive pattern in regex
body: <p>This is very much related to <a href="https://stackoverflow.com/questions/546433/regular-expression-to-match-outer-brackets">Regular Expression to match outer brackets</a> however, I specifically want to know how or whether it's possible to do this <a href="https://pypi.python.org/pypi/regex" rel="noreferrer"><strong>regex's recursive pattern</strong></a>? <em>I'm yet to find a python example using this strategy so think this ought to be a useful question!</em></p>
  
  <p>I've <a href="http://www.regular-expressions.info/recurse.html" rel="noreferrer">seen</a> <a href="https://stackoverflow.com/a/12455760/1240268">some</a> <a href="https://stackoverflow.com/a/19122223/1240268">claims</a> <a href="http://www.catonmat.net/blog/recursive-regular-expressions/" rel="noreferrer">that</a> recursive patterns can be used to match balanced parenthesis, but no examples using python's <a href="https://pypi.python.org/pypi/regex" rel="noreferrer">regex</a> package (Note: re <strong>does not</strong> support recursive pattern, you need to use regex).</p>
  
  <p>One <a href="http://www.regular-expressions.info/recurse.html" rel="noreferrer">claim</a> is that syntax is <code>b(?:m|(?R))*e</code> where:</p>
  
  <blockquote>
    <p><code>b</code> is what begins the construct, <code>m</code> is what can occur in the middle of the construct, and <code>e</code> is what can occur at the end of the construct</p>
  </blockquote>
  
  <hr>
  
  <p>I want to extract matches for the <em>outer</em> braces in the following:</p>
  
  <pre><code>"{1, {2, 3}} {4, 5}"
  ["1, {2, 3}", "4, 5"]  # desired
  </code></pre>
  
  <p>Note that this is easy to do the same for <em>inner</em> braces:</p>
  
  <pre><code>re.findall(r"{([^{}]*)}", "{1, {2, 3}} {4, 5}")
  ['2, 3', '4, 5']
  </code></pre>
  
  <p><em>(In my example I was using finditer (over match objects), see <a href="https://github.com/hayd/ctox/blob/a0e8a4068c5fae5fc26dbf14d63ca4f42cc84670/ctox/subst.py#L133" rel="noreferrer">here</a>.)</em></p>
  
  <p>So I had hoped that the following, or some variation, would work:</p>
  
  <pre><code>regex.findall(r"{(:[^{}]*|?R)}", "{1, {2, 3}} {4, 5}")
  regex.findall(r"({(:[^{}]*|?R)})", "{1, {2, 3}} {4, 5}")
  regex.findall(r"({(:.*|(?R))*})", "{1, {2, 3}} {4, 5}")
  regex.findall(r"({(:.*)|(?R)*})", "{1, {2, 3}} {4, 5}")
  regex.findall(r"({(:[^{}])|(?R)})", "{1, {2, 3}} {4, 5}")
  </code></pre>
  
  <p>but I'm scuppered by either [] or <code>error: too much backtracking</code>.</p>
  
  <p><strong>Is it possible to extract match objects for the outer parenthesis using regex's recursion?</strong></p>
  
  <hr>
  
  <p>Obviously, I run the risk of being shot down with:</p>
  
  <ul>
  <li><a href="https://stackoverflow.com/a/1732454/1240268">don't parse html with regex</a></li>
  <li>do this with pyparse</li>
  <li>write a proper lexer &amp; parser e.g. using ply</li>
  </ul>
  
  <p>I want to emphasis this is about <strong>how to use the recursive pattern</strong> (which if my understanding is correct, takes us outside of regular language parsing, so may can actually be possible!). If it can be done, this ought to be a cleaner solution.</p>