29
$\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.

Improve this question
$\endgroup$
2
  • 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, 2012 at 20:05
  • $\begingroup$ I added a note at the end, I hope it makes this point more clear. $\endgroup$
    – peppe
    Oct 2, 2012 at 22:35

3 Answers 3

Reset to default
11
$\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).

Improve this answer
$\endgroup$
3
  • 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, 2013 at 13:49
  • $\begingroup$ True, it's also noted in the comments. $\endgroup$
    – peppe
    Jun 5, 2013 at 15:19
  • $\begingroup$ The language of PCRE is in PSPACE, which is obvious since an implementation which uses polynomial space exists. While it's not a proof, it feels to me like the subset of PCRE without greedy operators is likely to be NP, because that would only require finding some match; greedy operators direct the search to a specific match. $\endgroup$
    – Pseudonym ♦
    Aug 17, 2021 at 6:49
7
$\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.

Improve this answer
$\endgroup$
4
  • 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, 2012 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, 2012 at 10:29
  • $\begingroup$ Yes, you two are right. I have modified the answer. $\endgroup$
    – Xodarap
    Oct 4, 2012 at 15:14
  • $\begingroup$ See also perlmonks.org/?node_id=406253 for an earlier discussion. $\endgroup$
    – András Salamon
    Jun 5, 2013 at 13:45
6
$\begingroup$

OP already linked an awesome blog post. I did some more research on it, and found the following pieces of information:

  • Wikipedia article on Context-sensitive grammar mentions that right-context-sensitive grammars can express all general CSGs (at the end of section, near reference 13). Unfortunately, neither that nor the referenced page shows how to find an equivalent right-CSG for a given CSG.
  • The blog post shows that lookbehind and lookahead assertions can be used to specify left and right context (α and β in αAβ → αγβ) respectively. Lookbehind is limited to fixed-length, but lookahead is not restricted at all.

Assuming both sources are true, any given CSG can be converted to a right-CSG, which can be expressed in Perl regex using lookahead. Therefore, Perl regexes are strong enough to match all CSGs.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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