3 ms·

> The awkward part is that a PCRE is demonstrably more powerful than a regular language, but not as powerful as a CFG Hmm, there's a reduction of 3-cnf-sat to

> The awkward part is that a PCRE is demonstrably more powerful than a regular language, but not as powerful as a CFG Hmm, there's a reduction of 3-cnf-sat to perl regexps, making them NP-complete. As CFGs are in NP... https://perl.plover.com/NPC/NPC-3SAT.html https://perl.plover.com/NPC/NPC-3SAT.html

shagie 3y ago
Reading up on the current spec, apparently a PCRE can do recursive calls. https://www.pcre.org/original/doc/html/pcrepattern.html#SEC23 https://www.pcre.org/original/doc/html/pcrepattern.html#SEC2... \( ( [^()]++ | (?R) )* \) https://regex101.com/r/eBtSTM/1 https://regex101.com/r/eBtSTM/1 for a slightly different formulation of that regex.