Where do most REGEX implementations fall on the complexity scale?

Question

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?

Answer 1

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 (a*)b\1b\1 matches strings of the form $a^n \cdot b \cdot a^n \cdot b \cdot a^n$, and you can use the pumping lemma to show this is not a context-free language. However, on the other hand, regexes with backreferences don't seem to be sufficient to match the balanced parenthesis language, which is the prototypical context-free language.

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.

Answer 2

The problem with answering this question is capturing the notion of "unbounded" in an actual implementation. For example, the regex /(.*)\1/ will capture the language $L = \{ ww | w \in \Sigma^*\}$ which is a CFL much more powerful. In practice there might be limits on the stack used (i.e maybe $w$ can't be longer than some large number $K$), which would effectively turn the language into $L_K = \{ ww | w \in \Sigma^*, \mid w \mid \le K\}$, which for any fixed $K$ is a regular expression again.

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).

Answer 3

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:

Aho, 1990, "Algorithms for finding patterns in strings" shows that the membership problem for regular languages with backtracking is NP complete.

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.

Answer 4

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.