Note that I said EREs, which don't have to provide backreferences. Arnold
Paul Eggert <[email protected]> wrote: > On 3/20/24 01:40, [email protected] 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
