Regex Match equal amount of two characters
<p>I'ld like to match the parameters of any function as a string using regex. As an example lets assume the following string:</p>

<pre><code>predicate(foo(x.bar, predicate(foo(...), bar)), bar)
</code></pre>

<p>this may be part of a longer sequence</p>

<pre><code>predicate(foo(x.bar, predicate(foo(...), bar)), bar)predicate(foo(x.bar, predicate(foo(...), bar)), bar)predicate(foo(x.bar, predicate(foo(...), bar)), bar)
</code></pre>

<p>I now want to find all substrings that represent a function/predicate and its parameters (i.e. in the first example the whole string as well as the nested <code>predicate(foo(...), bar)</code>). The problem is that I cant simply match like this</p>

<pre><code>predicate\(.*, bar\)
</code></pre>

<p>as i may then match more than the parameters of the predicate if the <code>*</code> is greedy, or less if it is lazy. Which is because such predicates() can be nested.</p>

<p>I need a regex that finds the string <code>predicate(...)</code> where <code>...</code> matches any string that contains an equal amount of <code>(</code>'s and <code>)</code>'s (lazy).</p>

<p>If it matters: I am using regex with the re module in python.</p>



<pre><code>import re

def parse(s):
    pattern = re.compile(r'([^(),]+)|\s*([(),])\s*')
    stack = []
    state = 0 # 0 = before identifier, 1 = after identifier, 2 = after closing paren
    current = None
    args = []
    for match in pattern.finditer(s):
      if match.group(1):
        if state != 0:
          raise SyntaxError("Expected identifier at {0}".format(match.start()))
        current = match.group(1)
        state = 1
      elif match.group(2) == '(':
        if state != 1:
          raise SyntaxError("Unexpected open paren at {0}".format(match.start()))
        stack.append((args, current))
        state = 0
        current = None
        args = []
      elif match.group(2) == ',':
        if state != 0: args.append(current)
        state = 0
        current = None
      elif match.group(2) == ')':
        if state != 0: args.append(current)
        if len(stack) == 0:
          raise SyntaxError("Unmatched paren at {0}".format(match.start()))
        newargs = args
        args, current = stack.pop()
        current = (current, newargs)
        state = 2
    if state != 0: args.append(current)
    if len(stack) &gt; 0: 
      raise SyntaxError("Unclosed paren")
    return args
</code></pre>



<pre><code>&gt;&gt;&gt; from pprint import pprint
&gt;&gt;&gt; pprint(parse('predicate(foo(x.bar, predicate(foo(...), bar)), bar)'), width=1)
[('predicate',
  [('foo',
    ['x.bar',
     ('predicate',
      [('foo',
        ['...']),
       'bar'])]),
   'bar'])]
</code></pre>

<p>It returns a list of all comma-separated top-level expressions. Function calls become a tuple of name and arguments.</p>

python regex first-order-logic