The true power of regular expressions (2012)

This is a great article.

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.

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.

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.