The true power of regular expressions (2012)(npopov.com)
npopov.com
The true power of regular expressions (2012)
https://www.npopov.com/2012/06/15/The-true-power-of-regular-expressions.html
3 comments
Great article! Ah someone else also read it through...
"Matching of regular expressions is NP-complete. As such you can solve any other NP problem using regular expressions."
Would love to see that be the mechanism of that proof.
"Matching of regular expressions is NP-complete. As such you can solve any other NP problem using regular expressions."
Would love to see that be the mechanism of that proof.
This is a really nice article.
tl,dr: Regexp with backrefs can "solve" NP-hard problems and thus theoretically can parse HTML, but in practice they are not the right tool to do so.
tl,dr: Regexp with backrefs can "solve" NP-hard problems and thus theoretically can parse HTML, but in practice they are not the right tool to do so.
I recently tried converting Org-mode files to html with sed and hit a block pretty soon -- sed's extended regex doesn't account for newline characters. That led to me abandoning the project, because even though I had it down 90%, I couldn't make code blocks free from being interpreted as regular org syntax. With PCRE it would have been much easier.