Most modern implementations of regular expressions, such as the ones in perl or .NET, go beyond the classical computer science definition of REGEXes with features like lookahead and lookbehind. Do these features let them parse statements that can't be described with a finite, non-pushdown automaton? How much closer to turing complete does this make them if they can?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
I don't think that the real problem is the question of what unbounded means; this is no worse than any other situation in parsing.
The trouble lies with characterizing backreferences, which are both very powerful and very limited: they allow description of some non-context-free languages, without allowing some context-free languages. For example, the regex
It's easy enough to give a denotational semantics saying what strings are in a language to regexes, but giving a good automata-theoretic characterization seems much more challenging. It's something like a register machine, into whose registers you can copy substrings of your input, and which you can use to test your current string against, but for which you lack the ability to modify these registers.
People doing finite model theory have a bunch of funky machine models, and it would be interesting to know if this corresponds to any of their models.
The problem with answering this question is capturing the notion of "unbounded" in an actual implementation. For example, the regex
But in principle, regexps as specified are more powerful than regular languages, as this related question discusses in much more detail (with a nifty example as well).
One interesting result, taken from this other question, also linked by Suresh Venkat, is that "Practical" regexps are NP-complete, and thus they should be equivalent in power to SAT.
Being a non-expert, while I agree that intuitively "regexes with backreferences don't seem to be sufficient to match the balanced parenthesis language", there is something strange going on. NP-completeness implies that any NP problem can be polynomially reduced to a regexp, so probably there is just a polynomial reduction from the "balanced parentheses" language to one recognizable with regexps. But again, there might be some absurd regexp to parse a CFL, since they can even parse non-prime unary numbers!
Probably, the lesson is that complexity classes and language classes are not comparable, in general. Which also suggests rephrasing your question, to reference the Chomsky hierarchy rather than the "complexity scale" (even if, to be fair, I was not confused by that).
Charles Stewart writes:
A partial preview (at least of the statement) can be found on Google Books, at page 289, and a bibliographic reference to the paper can be found here. Note that in the paper, rewbr stands for Regular Expression With BackReferences.
PCRE, the most popular implementation of "regular expressions" also implements recursive patterns, which go beyond backreferences. A questions about their complexity has just been asked at Stackoverflow. According to the practical-in-depth-answer by Perl guru brian d foy, this makes PCRE as powerful as context-free grammars. However the syntax is awful compared to Backus-Naur Form.