Re: Forwarded: Segmentation Fault via recursive loop in Gawk

[Paul Eggert]

On 3/20/24 01:40, arnold@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