Matching Nested Structures With Regular Expressions in Python

Question

I seem to remember that Regular Expressions in DotNet have a special mechanism that allows for the correct matching of nested structures, like the grouping in "( (a ( ( c ) b ) ) ( d ) e )".

What is the python equivalent of this feature? Can this be achieved using regular expressions with some workaround? (Though it seems to be the sort of problem that current implementations of regex aren't designed for)

Answer 1

I'd recommend removing the nesting from the regex itself, looping through the results and performing regexes on that.

Answer 2

Python doesn't support recursion in regular expressions. So equivalents to .NET's balancing groups or PCRE regex in Perl are not immediately possible in Python.

Like you said yourself: this is NOT a problem you should really be solving with a single regex.

Answer 3

Are you talking about recursion? It's not clear from your question. An example:

ActivePython 2.6.1.1 (ActiveState Software Inc.) based on
Python 2.6.1 (r261:67515, Dec  5 2008, 13:58:38) [MSC v.1500 32 bit (Intel)] on
win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import re
>>> p = re.compile(r"((\w+((\d+)[.;]))(\s+)\d)")
>>> m = p.match("Fred99. \t9")
>>> m
<_sre.SRE_Match object at 0x00454F80>
>>> m.groups()
('Fred99. \t9', 'Fred99.', '9.', '9', ' \t')

This shows matching of nested groups. The numbering of groups depends on the order in which their opening parenthesis occurs in the pattern.

Answer 4

Regular expressions cannot parse nested structures. Nested structures are not regular, by definition. They cannot be constructed by a regular grammar, and they cannot be parsed by a finite state automaton (a regular expression can be seen as a shorthand notation for an FSA).

Today's "regex" engines sometimes support some limited "nesting" constructs, but from a technical standpoint, they shouldn't be called "regular" anymore.

Answer 5

You can't do this generally using Python regular expressions. (.NET regular expressions have been extended with "balancing groups" which is what allows nested matches.)

However, PyParsing is a very nice package for this type of thing:

from pyparsing import nestedExpr

data = "( (a ( ( c ) b ) ) ( d ) e )"
print nestedExpr().parseString(data).asList()

The output is:

[[['a', [['c'], 'b']], ['d'], 'e']]

More on PyParsing:

• http://pyparsing.wikispaces.com/Documentation