How can a recursive regexp be implemented in python?

Question

I'm interested how can be implemented recursive regexp matching in Python (I've not found any examples :( ). For example how would one write expression which matches "bracket balanced" string like "foo(bar(bar(foo)))(foo1)bar1"

@Tempus, indeed, or Tony will come. http://stackoverflow.com/a/1732454/193892 — Prof. Falken, Aug 24 '12 at 13:42

score 15 · Answer 1 · answered Nov 01 '09 at 12:37

You could use pyparsing

#!/usr/bin/env python
from pyparsing import nestedExpr
import sys
astring=sys.argv[1]
if not astring.startswith('('):
    astring='('+astring+')'

expr = nestedExpr('(', ')')
result=expr.parseString(astring).asList()[0]
print(result)

Running it yields:

% test.py "foo(bar(bar(foo)))(foo1)bar1"
['foo', ['bar', ['bar', ['foo']]], ['foo1'], 'bar1']

score 11 · Answer 2 · edited May 14 '17 at 14:43

11

This is an old question, but for the people who come here through searches:

There's an alternative regex module for python that does support recursive patterns: https://pypi.python.org/pypi/regex

And it has a lot of more nice improvements on re.

edited May 14 '17 at 14:43

Nico Schlömer

46,467
24
178
218

answered Jul 01 '13 at 14:55

gitaarik

36,986
11
91
97

1

Awesome new engine! Decent recursion at last :) Thanks. – chtenb Jan 18 '14 at 09:01
2

Is this engine going to be merged into python's stdlib at some point? I can't seem to find any recent conversation about this. – chtenb Jan 18 '14 at 09:22
2

This answer would really benefit from an example! :) – Andy Hayden Oct 14 '14 at 22:59

score 4 · Answer 3 · answered Nov 01 '09 at 11:35

4

You can't do it with a regexp. Python doesn't support recursive regexp

answered Nov 01 '09 at 11:35

John La Rooy

281,034
50
354
495

score 3 · Answer 4 · edited Dec 21 '20 at 19:09

3

Unfortunately I don't think Python's regexps support recursive patterns.

You can probably parse it with something like pyparsing: https://github.com/pyparsing/pyparsing

edited Dec 21 '20 at 19:09

wim

302,178
90
548
690

answered Nov 01 '09 at 11:34

reko_t

53,784
10
85
77

score 2 · Answer 5 · answered Mar 04 '20 at 22:20

With PyPi regex, that you can easily install using pip install regex, you may use

import regex

pattern = r'[^()]*+(\((?>[^()]|(?1))*+\)[^()]*+)++'
text = 'foo(bar(bar(foo)))(foo1)bar1'
print(bool(regex.fullmatch(pattern, text)))
# => True

See the Python demo, see the regex pattern demo (note the \A and \z anchors are added in the demo because regex.fullmatch requires a full string match).

Pattern details

\A - implicit in regex.fullmatch - start of string
[^()]*+ - 0 or more chars other than ( and ) (possessive match, no backtracking into the pattern allowed)
(\((?>[^()]|(?1))*+\)[^()]*+)++ - 1+ occurrences of Group 1 pattern:
- \( - a ( char
- (?>[^()]|(?1))*+ - 1+ repetitions (possessive match) of
  - [^()] - any char but ( and )
  - | - or
  - (?1) - a regex subroutine that recurses Group 1 pattern
- \) - a ) char
- [^()]*+ - 0 or more chars other than ( and ) (possessive match)
\z - implicit in regex.fullmatch - end of string.

See the pattern and more information on regex subroutines at regular-expressions.info.

How can a recursive regexp be implemented in python?

5 Answers5

Linked

Related