23
$\begingroup$

As the title says, I spent a couple of hours last weekend trying to wrap up my mind about the class of languages matched by Perl-compatible regular expressions, excluding any matching operator that allows to execute arbitrary code inside the pattern.

If you don't know what PCREs are, please read this and this.

The problem is, the resources available on internet pretty much stop at context-free languages, and PCREs can match more than those (see below); but I really don't know where to find more theorems or papers about this kind of stuff.

In particular: PCREs are obviously a superset of regular languages (as the PCRE syntax has all the regular language operators).

Any CFG can be put in Greibach normal form, which removes left recursion. I think this can be used by means of (?(DEFINE)...) groups to "translate" the grammar into matching subroutines, avoiding to choke on left recursion, by translating:

  • the non-terminal at the head of each production becomes a subroutine (?<HEAD>...)
  • the body of each production is put in the subroutine; terminals are left as-is, non-terminals become procedure invocations (i.e. (?&NONTERMINAL));
  • all the productions with the same nonterminal as head are ORed together by means of the | operator (plus additional grouping with (?:...), if necessary)
  • the pattern then becomes a (?(DEFINE)...) group containing all the "translated" productions, and an invocation for the procedure of the starting symbol, to match the entire string, i.e. ^(?(DEFINE)...)(?&START)$

This should deal with any CFG. Therefore, PCREs should be able to match any CFL.

There's more: let's take the simple language $$L = \{ ww | w \in \Lambda^* \} $$ i.e. the language of the strings repeated twice. This language is not a CFL -- the pumping lemma for CFLs fails. (Pay particular attention that $$ |vxw| \leq p$$ must hold, thus you can't just pump the beginnings or the ends of the two repeated strings.)

However, this language is easily matched by a PCRE: ^(.*)\1$. Therefore, we're strictly above CFLs.

How much above? Well, as I said, I have no idea. I couldn't find any resources about CSLs or all the other classes in between to make up my mind. Any expert willing to discuss this?

Addendum: I was asked to specify exactly which subset of the PCRE syntax must be allowed. As I wrote at the beginning of the post, I wanted to exclude any operator that allows to execute arbitrary code inside of the pattern, such as ??{}.

For the argument's sake, I think we can stick with the syntax defined by the pcresyntax(3) man page, which is a reasonable subset of what Perl 5.10-5.12 offers, minus the callouts (as they're not inside the pattern). I'm not sure that adding or removing backtracking control verbs change the language we can recognize; if so, it would be nice to figure out which classes we get with and without those.

$\endgroup$
  • 2
    $\begingroup$ Please include your chosen definition of PCRE in your question, as it has changed between versions. The real Perl regexes can contain arbitrary Perl code, making them Turing-complete. $\endgroup$ – Gilles 'SO- stop being evil' Oct 2 '12 at 20:05
  • $\begingroup$ I added a note at the end, I hope it makes this point more clear. $\endgroup$ – peppe Oct 2 '12 at 22:35
7
$\begingroup$

I've also found this blog post extremely interesting http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html. It provides the very same proof I gave before about the fact that regexps recognizes the CFLs (by rewriting the grammar through DEFINE blocks), and even some CSLs (like the language of repeated strings); it builds on that and goes on, giving a proof that regexps with backreferences are NP-hard (by reducing 3-SAT to a regexp).

$\endgroup$
  • 2
    $\begingroup$ When the author says "NP-complete" they should be saying "NP-hard". They provide no proof that the class of PCRE languages is contained in NP. $\endgroup$ – András Salamon Jun 5 '13 at 13:49
  • $\begingroup$ True, it's also noted in the comments. $\endgroup$ – peppe Jun 5 '13 at 15:19
5
$\begingroup$

They decide at most the context-sensitive languages (which, as you point out, is a superset of the context-free languages). See this perl monks post.

The basic insight is that the "memory" of the machine is the number of capture groups, which is linearly bounded.

$\endgroup$
  • 5
    $\begingroup$ The argument you give in the second paragraph explains why PCRE can not accept more than CS, but not why this inclusion is exact (which you suggest in your first paragraph). It does not seem as if the linked article gave a proof of that, either. $\endgroup$ – Raphael Oct 2 '12 at 17:57
  • $\begingroup$ Well, you can't group more than what's in the input string, and the number of groups is fixed in a given pattern, so you have an upper (linear) limit to the memory a pattern uses. Still, I miss a formal proof of a PCRE -> linear bounded automaton transformation... $\endgroup$ – peppe Oct 4 '12 at 10:29
  • $\begingroup$ Yes, you two are right. I have modified the answer. $\endgroup$ – Xodarap Oct 4 '12 at 15:14
  • $\begingroup$ See also perlmonks.org/?node_id=406253 for an earlier discussion. $\endgroup$ – András Salamon Jun 5 '13 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.