I recently discussed with a friend about a website that proposed regex challenges, mainly matching a group a of words with a special property. He was looking for a regex that matches strings like |||||||| where the number of | is prime. I immediatly told him that won't ever work because if such a language was regular, the translation of pumping lemma would gives the fact that for a prime $p$ large enough, it exists $k \leq p$ such that $p + nk$ is prime for all $n \geq -1$, and well this is not likely to be the case at all (repartition of primes, triviality of such an unknown and crushing property, ...)
But then someone came with the solution : NOT MATCHING (||+?)\1+
This expression tries to match the capture group (that can be ||,|||,|||| and so on of $k \geq 2$ occurences of |) $n \geq 2$ times. If it matches, it means that the number represented by the string is divisible by $k$, and hence is not prime. Otherwise, it is.
And I felt stupid, because it became obvious that grouping and backreference allows regex to be actually a lot more expressive than...regular expression, in the theoritical sense. Now they even added lookarounds and other operators I didn't know about when I used to do real regex.
According to Wikipedia, it is even more expressive that languages generated by a context-free grammar. So here is my question :
- can we represent any algebraic language (generated from a context-free grammar) with modern regular expression engines
- is there a more general description, or at least an upper bound on the complexity of what kind of languages can be described by a modern regex ?
More pragmatically, is there any serious theory behind it or are we just adding any new features as it comes each time it seems implementable to the initial block of real regular expressions based on finite automata ?
I know that "modern regex" isn't very specific while the question is, but I mean at least with backreferences, and possibly more. Of course, if you have partial anwsers assuming certain restrictions on this "modern regex" language, feel free to post it.
