> The awkward part is that a PCRE is demonstrably more powerful than a regular l... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		davidgay on June 21, 2023 \| parent \| context \| favorite \| on: A regular expression to check for prime numbers (2... > 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

shagie on June 21, 2023 [–]

Reading up on the current spec, apparently a PCRE can do recursive calls.

https://www.pcre.org/original/doc/html/pcrepattern.html#SEC2...

    \( ( [^()]++ | (?R) )* \)

https://regex101.com/r/eBtSTM/1 for a slightly different formulation of that regex.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact