Can regular expressions be used to match nested patterns? [duplicate]

by

No. It’s that easy. A finite automaton (which is the data structure underlying a regular expression) does not have memory apart from the state it’s in, and if you have arbitrarily deep nesting, you need an arbitrarily large automaton, which collides with the notion of a finite automaton.

You can match nested/paired elements up to a fixed depth, where the depth is only limited by your memory, because the automaton gets very large. In practice, however, you should use a push-down automaton, i.e a parser for a context-free grammar, for instance LL (top-down) or LR (bottom-up). You have to take the worse runtime behavior into account: O(n^3) vs. O(n), with n = length(input).

There are many parser generators avialable, for instance ANTLR for Java. Finding an existing grammar for Java (or C) is also not difficult.
For more background: Automata Theory at Wikipedia

More Related Contents:

  1. How can I match nested brackets using regex?
  2. Is it possible to escape regex metacharacters reliably with sed
  3. Regex: match everything but a specific pattern
  4. Regular expression to stop at first match
  5. Regex to validate password strength
  6. How to find patterns across multiple lines using grep?
  7. Simple regular expression for a decimal with a precision of 2
  8. Have trouble understanding capturing groups and back references
  9. RegEx to parse or validate Base64 data
  10. My regular expression matches too much. How can I tell it to match the smallest possible pattern? [duplicate]
  11. RE error: illegal byte sequence on Mac OS X
  12. How do I include negative decimal numbers in this regular expression?
  13. Is there something like a counter variable in regular expression replace?
  14. Regular Expression for extracting text from an RTF string
  15. Why are regular expressions so controversial? [closed]
  16. What’s the Time Complexity of Average Regex algorithms?
  17. Regex to find 3 out of 4 conditions
  18. Escaped Periods In R Regular Expressions
  19. Regex to get the words after matching string [duplicate]
  20. Add slash to the end of every url (need rewrite rule for nginx)
  21. Does lookbehind work in sed?
  22. Lua pattern matching vs. regular expressions
  23. R split on delimiter (split) keep the delimiter (split)
  24. hive regexp_extract weirdness
  25. Google Sheets Formula for Extracting Domain From Website?
  26. Does \w match all alphanumeric characters defined in the Unicode standard?
  27. Matching an optional substring in a regex
  28. Replace string only once with php preg_replace
  29. Bash – Regex for HTML contents
  30. How to validate email id in angularJs using ng-pattern

Leave a Comment