What kind of formal languages can modern regex engines parse?
computer-science, formal-languages, regex
Solution
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
Problem
Here on SO people sometimes say something like "you cannot parse X with regular expressions, because X is not a regular language". From my understanding however, modern regular expressions engines can match more than just regular languages in Chomsky's sense. My questions: given a regular expression engine that supports - backreferences - lookaround assertions of unlimited width - recursion, like `(?R)` what kind of languages can it parse? Can it parse any context-free language, and if not, what would be the counterexample? (To be precise, by "parse" I mean "build a single regular expression that would accept all strings generated by the grammar X and reject all other strings"). Add.: I'm particularly interested to see an example of a context-free language that modern regex engines (Perl, Net, python regex module) would be unable to parse.