On 3/20/24 01:40, arn...@skeeve.com wrote:
It's possible to write a POSIX compliant matcher for EREs that doesn't
have such problems; I know someone doing it.
I think matching POSIX regular expressions in polynomial time is
equivalent to proving P=NP, i.e., you'll win the Turing Award if you
actually pull it off. This is due to back-references.
See, for example:
Câmpeanu C, Santean N. On pattern expression languages. 2007. Proc
AuthMathA. https://cs.smu.ca/~nic.santean/art/regex.pdf
For a more programmer-friendly summary of the problem, and the subset of
POSIX REs that you can match more quickly, see:
Pinto PED, Lopes JPA, de Brito MAS. A polynomial-time regular
expressions implementation. 2017. Cadernos Do IME - Série Informática,
37(Junho), 22–36. https://doi.org/10.12957/cadinf.2016.13778
