Related content on Stack Overflow: "Regex: How to find and extract acronyms and corresponding definition of acronym from a text?"[0] that gives the nearly the s

Related content on Stack Overflow: "Regex: How to find and extract acronyms and corresponding definition of acronym from a text?"[0] that gives the nearly the same RFC 5322 parser. The reduction of 3CNF-SAT seems to be borrowed from "Reduction of 3-CNF-SAT to Perl Regular Expression Matching"[1], whose author is careful to note that the reduction shows that regex matching with backreferences is NP-hard. To show that it is NP-complete, you'd also have to show that regex matching with backreferences is also in NP, i.e., that any match is checkable in polynomial time. Readers may also be interested in "Oh Yes You Can Use Regexes to Parse HTML!"[2] on Stack Overflow by Tom Christiansen. [0]: https://stackoverflow.com/a/18339610/123109 https://stackoverflow.com/a/18339610/123109 [1]: https://perl.plover.com/NPC/NPC-3SAT.html https://perl.plover.com/NPC/NPC-3SAT.html [2]: https://stackoverflow.com/a/4234491/123109 https://stackoverflow.com/a/4234491/123109