What kind of formal languages can modern regex engines parse?

by

I recently wrote a rather long article on this topic: The true power of regular expressions.

To summarize:

  • Regular expressions with support for recursive subpattern references can match all context-free languages (e.g a^n b^n).
  • Regular expressions with lookaround assertions and subpattern references can match at least some context-sensitive languages (e.g. ww and a^n b^n c^n).
  • If the assertions have unlimited width (as you say), then all context-sensitive grammars can be matched. I don’t know any regex flavor though that does not have fixed-width restrictions on lookbehind (and at the same time supports subpattern references).
  • Regular expressions with backreferences are NP-complete, so any other NP problem can be solved using regular expressions (after applying a polynomial-time transformation).

Some examples:

  • Matching the context-free language {a^n b^n, n>0}:

    /^(a(?1)?b)$/
# or
/^ (?: a (?= a* (\1?+ b) ) )+ \1 $/x

  • Matching the context-sensitive language {a^n b^n c^n, n>0}:

    /^
    (?=(a(?-1)?b)c)
    a+(b(?-1)?c)
$/x
# or
/^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $/x

More Related Contents:

  1. Regular Expressions with repeated characters
  2. Phone number regular expressions exact format
  3. Regex to match string containing two names in any order
  4. Validating IPv4 addresses with regexp
  5. How to match numbers between X and Y with regexp?
  6. Does a dot have to be escaped in a character class (square brackets) of a regular expression?
  7. What’s the regular expression that matches a square bracket?
  8. What flavor of Regex does Visual Studio Code use?
  9. Jmeter extracting fields/parsing JSON response
  10. How to back reference “inner” selections ( () ) in a regular expression?
  11. Regular expression – PCRE does not support \L, \l, \N, \P,
  12. Negative look-ahead in Go regular expressions
  13. R – gsub replacing backslashes
  14. How to match all text between two strings multiline
  15. Regular expression to count number of commas in a string
  16. How to validate a user name with regex?
  17. Unicode Regex; Invalid XML characters
  18. Match at every second occurrence
  19. What does ‘\K’ mean in this regex?
  20. regex for preserving case pattern, capitalization
  21. RegEx No more than 2 identical consecutive characters and a-Z and 0-9
  22. Regex to find text between second and third slashes
  23. htaccess force https and redirect www to non-www, but no other subdomains
  24. How to escape dollar sign ($) in a string using perl regex
  25. Checking for diacritics with a regular expression
  26. Design DFA accepting binary strings divisible by a number ‘n’
  27. Regex matching beginning AND end strings
  28. hgignore: help ignoring all files but certain ones
  29. Regex return file name, remove path and file extension
  30. Guide on how to use regex in Nginx location block section?

Leave a Comment