0

I am wondering if python regular expressions can count. For example, would they have the ability to skip over nested parentheses? I know Java cannot do this so I am wondering if python would be a better option.

jonrsharpe
  • 115,751
  • 26
  • 228
  • 437
loolooo
  • 181
  • 1
  • 7
  • 3
    possible duplicate of [Python: How to match nested parentheses with regex?](http://stackoverflow.com/questions/5454322/python-how-to-match-nested-parentheses-with-regex) – Cory Kramer Aug 14 '14 at 14:01
  • Generally regexes cannot count, but what are you trying to achieve exactly? – Boris Aug 14 '14 at 14:01
  • It is unlikely that regex is the correct approach to what you're trying to do, either in Python or Java. Could you add more details about the task, what you've tried and what the problem is? – jonrsharpe Aug 14 '14 at 14:01
  • 1
    According to the [pumping lemma](http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages), regular expressions are incapable of counting parentheses. You'd need a context-free grammar instead. – chrisaycock Aug 14 '14 at 14:02

1 Answers1

2

Basic regexes are strictly defined as what can be expressed with a finite state automaton. No regex can do this. Thus in general regexes cannot use counters. This is one of the consequences of the Pumping Lemma as @chrisaycock pointed out. Regardless of the programming language (and the language to express Regular expressions), it is impossible...

Regexes are however capable of enumerating over all matches. One can thus count the number of open ( and closing ) brackets. But is not able to verify if they match the guidelines of brackets (no closing bracket where there was no open bracket, etc.)

For purposes like nested brackets, context-free grammars exist, like PLY.

Willem Van Onsem
  • 443,496
  • 30
  • 428
  • 555