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.