Recursive pattern in regex

by

The pattern is:

{((?>[^{}]+|(?R))*)}

You can see this works for your example:

regex.findall("{((?>[^{}]+|(?R))*)}", "{1, {2, 3}} {4, 5}")
# ['1, {2, 3}', '4, 5']

Explanation:

The m part needs to exclude the brackets. The use of an atomic group is needed if you want at the same time to allow a quantifier for [^{}] and to repeat the group without catastropic backtracking problems. To be more clear, if the last closing curly bracket is missing this regex engine will backtrack atomic group by atomic group instead of character by character. To drive home this point, you can make the quantifier possessive like that: {((?>[^{}]+|(?R))*+)} (or {((?:[^{}]+|(?R))*+)} since the atomic group is no more useful).

The atomic group (?>....) and the possessive quantifier ?+, *+, ++ are the two sides of the same feature. This feature forbids the regex engine to backtrack inside the group of characters that becomes an “atom” (something you can’t divide in smaller parts).

The basic examples are the following two patterns that always fail for the string aaaaaaaaaab:

(?>a+)ab
a++ab

that is:

regex.match("a++ab", "aaaaaaaaaab")
regex.match("(?>a+)ab", "aaaaaaaaaab")

When you use (?:a+) or a+ the regex engine (by default) records (in prevision) all backtracking positions for all characters. But when you use an atomic group or a possessive quantifier, theses backtracking positions are no more recorded (except for the begining of the group). So when the backtracking mechanism occurs the last “a” character can’t be given back. Only the entire group can be given back.

[EDIT]: the pattern can be written in a more efficient way if you use an “unrolled” subpattern to describe the content between brackets:

{([^{}]*+(?:(?R)[^{}]*)*+)}

More Related Contents:

  1. Matching Nested Structures With Regular Expressions in Python
  2. Take first some character of string but if particular character will come consider that character also
  3. How to extract numbers from a string in Python?
  4. Is it worth using Python’s re.compile?
  5. Extract part of a regex match
  6. Regular expression matching a multiline block of text
  7. What is the difference between re.search and re.match?
  8. How can I do multiple substitutions using regex?
  9. regex for Twitter username
  10. Find shortest matches between two strings
  11. Python re.sub back reference not back referencing [duplicate]
  12. How to grab number after word in python
  13. Extract a string between double quotes
  14. Reuse part of a Regex pattern
  15. Find the indexes of all regex matches?
  16. RegEx Get string between two strings that has line breaks
  17. Python – re.findall returns unwanted result
  18. Why Does a Repeated Capture Group Return these Strings?
  19. Splitting out the output of ps using Python
  20. How to use regex to find all overlapping matches
  21. How can a recursive regexp be implemented in python?
  22. Python regular expression pattern * is not working as expected
  23. Split string at every position where an upper-case word starts
  24. Why does this take so long to match? Is it a bug?
  25. Regex matching – why does this not match and return None?
  26. How to use str.contains() with multiple expressions in pandas dataframes
  27. match dates using python regular expressions
  28. How to Fix JSON Key Values without double-quotes?
  29. python regular expression across multiple lines
  30. How to use regex with optional characters in python?

Leave a Comment