Comment by jakobnissen
8 hours ago
This article misleads you by conflating regular expressions with specific implementations like PCRE, which also does non-regex string matches. Annoyingly, the article does a good job of explaining what a regex is and what the limitations of regex are relative to PCRE, so the author should understand that what they are talking about when they talk about NP-complete string matching is not regex, but PCRE-specific features.
The distinction matters because regex absolutely can't match HTML, and because regex, unlike PCRE expressions, have guaranteed O(1) space and O(n) time complexity when matching a string of length n. When you use PCRE features for string matching, that may degrade to exponential time which makes it useless. For example, you can do denial of service PCRE attacks, but not denial of service regex attacks (unless you can query with some megabyte-large regex).
In common usage, "regex" means patterns accepted by regex engines like PCRE. Police the formal term "regular expression" if you like, but ordinary usage does not honour that distinction.
Also, it's not guaranteed that an engine implementing regular expressions will have O(n) time complexity - a backtracking engine can still have much worse performance on formal regular expressions.
You’re splitting hairs. The author is writing from the perspective of a PHP programmer (author is in fact a major PHP contributor), where the term “regex” has a single very clear definition, namely PHP’s PCRE-based implementation.
No, this is not splitting hairs. This is the author using the straight up wrong terminology. Regex can’t match HTML, and aren’t NP-complete. The fact that the author believes that “regex obviously means PCRE” is objectively wrong and misleading in the sense that all the things his article are about would have another conclusion if he actually talked about Regex.
It’s like if there was a library called QuickSort which also included a SAT solver and I then wrote an article about how you can solve SAT-equivalent problems with quicksort (“in the programmer sense, which obviously means a SAT solver”)
I already quoted from TFA in response to you, completely refuting your misrepresentation of it. To post this more than an hour after my comment while ignoring my comment is bad faith, especially this extraordinary falsehood and fake quote:
> the author believes that “regex obviously means PCRE”
The actual statement in TFA is
> (Reminder: When I say “regular expression” here I obviously mean it in the programmer sense, not the formal language theory sense.)
There are regex libraries that are more powerful than the regular expressions corresponding to Chomsky's regular languages. One can pedantically argue that these libraries are "using the straight up wrong terminology" by using such terms as "regex" or "regexp", but that ship has sailed, and the charge against TFA is bogus since it is very explicit about talking about those libraries and not the something from formal language theory, and it is very explicit about these regexes being able to parse CFGs and not just Chomsky's regular languages.
Finally, you're just plain wrong about "the straight up wrong terminology". The technical language theory terminology is "regular language", which has a formal definition and TFA is completely accurate in its discussion of that. But "regular expression" and "regex" has a broader and more casual meaning: https://en.wikipedia.org/wiki/Regular_expression#Patterns_fo...
I won't respond further.
Actually TFA is explicit about this:
> Regular expressions in the formal grammar sense can (pretty much by definition) only parse regular grammars and nothing more.
> But when programmers talk about “regular expressions” they aren’t talking about formal grammars. They are talking about the regular expression derivative which their language implements. And those regex implementations are only very slightly related to the original notion of regularity.
> Any modern regex flavor can match a lot more than just regular languages. How much exactly, that’s what the rest of the article is about.