The true power of regular expressions (2012) | Hacker News Reader

The true power of regular expressions (2012)

npopov.com

81 pointsuneven943462 comments

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).

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.

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.

There is no backtracking in actual regular expressions. Your misunderstanding is the technicality that the parent was taking about.

Regular expressions aren't an algorithm. DFA/NFA-based matching and backtracking are both valid implementation strategies, with different performance characteristics. Backtracking is arguably the most intuitive direct implementation. You and the other poster are confusing the mathematical definition with algorithms used to perform matching.

That's the whole point of the article, that regular expressions you use day-to-day are not strictly regular.

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.

I eagerly await your angry letters to the authors of pretty much every programming language in use today that their RegExp class isn't, in fact, a regular expression implementation and needs a better name.

> "Regex absolutely can't match HTML"

Never abuse "absolutely", and match != parse.

Something that seems obvious but not always implied by people's comments is that people are rarely trying to match an entire document with a regular expression so it doesn't really matter that "HTML is not a regular language".

If I am trying to e.g. count div tags with a regex like "<div" or whatever, then clearly this would work in 99.9% of cases and probably achieve what the poster is looking for.

As soon as you also add character classes to ignore various parts of the document that you are not interested in like "<div[^>]*>" or whatever it is, then it is eminently useful even if the bit we are ignoring is not fully regular.

One lovely thing about regex is how fast it is. I was asked to parse a massive CAN Bus log file for how many times some event had logged. This was the early 2000s and the file was 6GB, which was pretty big. I tried .Net's string.StartsWith or something and that took ages to run through the file. I did the same thing with a regex and it finished in like 5 seconds (HDD, not SSD!). I don't know how the magic works but it is very impressive.

RegExps is the way to tokenize, so it's not surpassing you can look for individual tokens using them.

It's parsing that's hard , for example when it needs to match up braces, or start and end tags, even if either is easily matched by a RegExp.

And you still need to be careful if the source you're looking in has any way to escape text or have different meanings for the same text. In source code, you should recognize comments and strings (and RegExp literals) so you don't match inside those. In HTML, you should recognize CDATA sections, including script elements. If they contain `<div`, it's not a tag.

That's is, your 99.9% is probably too damn high.

Are we also counting divs inside comments or literals within scripts?

There is a reason this advice is default. The chances an edge case exist are probably a lot higher than anyone is prepared to accept. Even in the "simple" cases.

Regex can also be horribly slow - it depends on the particular regex you are using.

> Regex can also be horribly slow - it depends on the particular regex you are using.

And the alternative approach we are comparing to.

"Doom Using Regular Expressions" https://news.ycombinator.com/item?id=49094081

This is wonderful! You should submit this to the HN feed.

Some people, when confronted with a problem, think "I know, I'll get my agent to solve it with regular expressions."

Now they have three problems.

It's ok, someone else can maintain it.

It might just be a me problem, but I've always been wary of regexes. They're not too bad to write, but reading them back and understanding what's actually going on can get a bit hairy. Plus, all of the subtle differences between regex libraries seems like a bit of a footgun.

Obviously they have their place, but I know a lot of the older guys seemed to love them way more than the young.

I know I am very very alone in this, but I've always found regex very readable. It's just not _quickly_ readable. You can't look at 20 characters of regex and read it and understand it as quickly as you would 20 characters of English. The biggest issue, I think, is people trying to do that. Regex is very information dense, it should be approached with the care of a mathematical formula or a sudoku rather than English prose.

The readability should be compared to alternative ways to solve the same problem. Sure, regexes are not the most intuitive syntax, but it is compact and declarative. What is the alternative? Substring searches? Looping over characters? Hand-rolled recursive descent? Neither are obviously more readable, and intermingles the pattern with the mechanism.

Raku worked on this. As the Perl successor, they gave regex a lot of attention. The result still look like regex, but more powerful and with a more consistent syntax. They also made "/x" the default, which ignores unescaped whitespace and lets you put comments, so you can use spacing and indentation for readability. The general idea is that they are treated like actual programs rather than extended search strings.

But Raku, despite some good ideas and what looks like a nice community is not mainstream to say the least. So I don't expect "RCRE" to become a thing anytime soon.

> older guys seemed to love

I actually don't love regular expressions. But honestly I think it is implementations that make me dislike using them.

They are unclear in most programming languages.

Using regular expressions in just about every language I've used has had this programming language vs regular expression language ambiguity that makes them hard to recommend in production past minimal complexity.

I don't like to hand off code to my coworkers where it's unclear if a character is part of the quoting system, part of the programming language, part of the regular expression syntax, or a character to match literally.

for example, what if the program variable foo contained "abc" and you wanted that to be matched by a regular expression. each language has a different way of doing this and reviewing the code has a high chance of an error unless the person is really pedantically accurate regarding regular expressions. for example a regular expression in bash vs python is different because of quoting and escapes. And what if you wanted to use it in a search and replace?

What would help would be:

- a very very syntax aware editor that could color the regular expression, showing language characters vs regular expression control characters vs literals

- a tool for bidirectional conversion. Type in a pure regular expression and it will put out the expression in your programming language. or check an expression in the language and it will expand/annotate the regular expression.

(maybe there are things like this?)

Various libraries (e.g. Python's `re` library) support comments and whitespace as an option allowing you to format the regex on multiple lines with commenting to document what each part does.

I'm not sure if there are any regex libraries that support DSLs and easy composability (e.g. the email RFC regex would be easier to read/maintain if you could specify the individual parts like are defined in the RFCs).

Emacs/Elisp has the rx library: https://www.gnu.org/software/emacs/manual/html_node/elisp/Rx...

You get s-exp-based regex syntax (example for C-style block comments; there are shorter aliases too, e.g. `zero-or-more` can be written as `*`):

    (rx "/*"                    ; Initial /*
        (zero-or-more
         (or (not "*")          ;  Either non-*,
             (seq "*"           ;  or * followed by
                  (not "/"))))  ;     non-/
        (one-or-more "*")       ; At least one star,
        "/")                    ; and the final /

and you have rx-define and rx-let to defined named subforms:

    (rx-let ((comma-separated (item) (seq item (0+ "," item)))
             (number (1+ digit))
             (numbers (comma-separated number)))
      (re-search-forward (rx "(" numbers ")")))

And this is just the regex builder - syntactic sugar - as it still just builds a single regex serialized to a normal string.

I tend to use it everywhere, since it is guaranteed to always properly escape all backslashes (a major pain point in string regexes in Emacs), but it's also useful for building larger regexes from chunks and reusing chunks in multiple related regexes.*

Swift even has a `RegexBuilder` DSL which makes writing regular expressions pure code and type-safe. Pretty amazing tbh

I honestly never knew that, should give it another go.

I would recommend trying something like PyParsing[1] instead. Libraries like this allow you to compose the parser from language-level entities (object and functions, on top of regex and string literals). This means you can attach comments to those entities naturally within the syntax of the language. You also get much better error reporting out of the box, as well as a well-defined way of attaching transforming code to parts of the parser.

There's a place for simple regexes, but complex regex DSLs (with comments and non-significant whitespace, etc.) are almost always less convenient than simply using your language directly.

[1] https://pyparsing-docs.readthedocs.io/en/latest/HowToUsePypa...

there is, I think, a divide between programmers that is pretty basic. Do they need a language that maps somewhat to written human language, or can they adapt to languages that do do not at all resemble the human languages they are familiar with.

This divide is most probably cultural, programmers in Western societies often have pre-programming familiarity with English and thus they do not need to learn a language that does not match to how they understand languages to work (as might be the case with programmers from Asian countries or others where familiarity with English is not guaranteed)

So if your primary gateway to programming languages are ones that slightly resemble a human language you are familiar with you may have lots of psychological blocks keeping you from making that final jump to reasoning in J, or APL, or even a DSL like regular expressions.

Of course DSLs also have the problem that many programmers do not seem to fit well in things that do not have all the logical control operators they are used to, thus programmers who do not handle CSS, SQL or similar languages even though they are significantly simpler than a full featured programming language.

In short, things that are very different from what you are used to will probably be difficult to learn, use, and remember, and the same goes for most of your coworkers.

I never have patience with normal regex but I can handle it when expressed something like this:

https://github.com/philiprehberger/dotnet-regex-builder

> as might be the case with programmers from Asian countries or others where familiarity with English is not guaranteed

Lots of Asian countries where familiarity with English is assumed in professional contexts.

> So if your primary gateway to programming languages are ones that slightly resemble a human language you are familiar with you may have lots of psychological blocks keeping you from making that final jump to reasoning in J, or APL, or even a DSL like regular expressions.

That raises the interesting possibility that J or APL might be more appealing to non-English speaking countries, or maybe where the dominant languages are not Indo-European (so not similar to English either). I wonder whether there is any evidence of this?

I doubt there has been studies on it, but I figure if you are already learning an alphabet and expression in that alphabet that are nonsensical to you to be able to program, then J or APL syntax should be definition not increase difficulty.

It might show up if there are national or even regional numbers for popular languages.

the might at beginning of the clause was also meant to take into account that people might have familiarity with English, as I could not be certain, but probably should have been expressed better.

I should really have worded my comment differently too. You need to filter out those Asian countries.

Thinking about it, I think one thing that might stop that is that most people will start with English like languages first even if they are not English speaking and by the time they learn things like APL they will already be familiar with the more common style of languages.

probably, so harder to check, but if the "english-like" languages are still just gibberish to them that does things they might still be able to learn what to English speaking peoples looks like gibberish that does things easier.

I think there's also a bit of Unix philosophy in there.

If you're using 5 different dsls to write a script, 1 more isn't really an issue. Now the fashion is for 1 big batteries included language, which requires you to know a lot of things itself, so that non regular (ha) DSL sticks out.

Theres probably an issue of many tools being much more powerful than the average case, so if you want you can write a re/bash/sed script that's impenetrable to the average programmer.

I don't know if the same is true for large individual languages? Could you take one element of c++ to the extreme to the point that it doesn't make sense to most c++ers?

Slightly tangential to your point, but I'm leaning towards programming languages no longer limiting themselves to ASCII. IOW, I'm leaning more towards APL than to J. I'm wondering how much of a blocker it's been to not embrace non-ASCII characters, or italic/bold/underlined formatting.

Problem is, how do you tell that character X is indeed character X and not something that looks like character X?

Further, how far do we take the function names are a language thing? Should an ss be rendered differently in Germany? Is leß() the same as less()?

So yes I don't mind non ASCII characters, I'm not sure this should primarily be about supporting users of foreign languages, rather to increase the number of characters.

Although at this point, I would guess that most programmers have some kind of ASCII compatible keyboard? So what's being gained by having characters that aren't on that keyboard?

>> I've always been wary of regexes.

Be afraid: https://owasp.org/www-community/attacks/Regular_expression_D...

https://en.wikipedia.org/wiki/ReDoS

This is by design, the regexp syntax has been invented for write-only programming at the CLI, and graduated to ubiguitous programming language syntax because worse is better.

The regular formalism is all about composability, and most languages don't offer a way to compose regexps, which is a real shame IMO.

Just like jq there will be some lad along to tell us that "I don't like the syntax and find it confusing" not realising that's the exact superpower it presents is it's terseness is a key property to it's adoption. jq and regex really are sort of handy one liners that you invoke in other scripts and you explain what they do in your script with a comment.

Before the AI craze, I'd gotten quite good at writing regexes. Regexr was quite useful for decoding and composing them. I feel like they're going to become a lost art.

Totally agree. Selfishly, I was always the "regular expression" guy because they were a bit hobby space of mine (engine implementation and such), so seeing LLMs rip them is a bid of a bummer.

Half the reason it's a bummer is because I've seen coworkers who don't know when a regular expression is very suboptimal performance wise, but the LLM has no problem spitting it out. Part of really understanding regular expressions is knowing when to not use them.

The one that sticks in my head is when I was debugging some code that I was suspicious was causing our high memory consumption on a simple API service just to find out the regular expression was being used to strip a potential "data" front of a base64 encoded file (apparently someone thought we should do that instead of rejecting the payload). The regular expression scanned an entire base64 string that was up to 50 MB for the raw file, so about 66MB base64 encoded. I'll tell you what, replacing it with a loop over the first handful of characters solved all the problems. It should've never been a regular expression. If you see regular expressions as an archaic language that solve string problems, and now the magic box can make them for you, you're in for hell.

Being the "regex guy" at work was also my thing. I was even in the process of making a regexr-like extension for vscode, but right about then everyone jumped ship to AI and making vscode extensions kinda felt like a last years thing.

They really are a "tool for the job" type thing, and I've seen the abuses people put them through. The fact that we struggled to know when to reach for it before worries me that this will be exacerbated now that we don't even read our own code.

Regular expressions will always remain fundamental to computer science: They characterise all of those - and only those - conditions on bytestrings (or bitstrings, or Unicode strings, etc) which are checkable in constant memory.* In other words, they characterise the set of all "regular languages", which is a name for DSPACE(O(1)). Furthermore, regular expressions can be matched in O(n) time and O(1) memory, within a single left-to-right pass, which is the highest level of efficiency mathematically possible. Since they operate on bytestrings, they can be applied to computer memory and computer state itself, which are ultimately just bytestrings, and not just to text.

To be fair, you might know all of that, but I wanted to highlight this. LLMs are a lot less efficient than regular expressions wherever both are applicable, simply because everything is less efficient than regular expressions.

* By constant memory, I mean that the memory usage has a maximum value independent of the size or the contents of the input bytestring.

It's a pity that the Perl6 saga killed the new regex ideas - I wish the raku regexes were adopted elsewhere (like the Perl5 regexes were): https://docs.raku.org/language/regexes

Regexes are great, they seem like magic when you use them right. They can solve your problems even if you don't use them right. Just make sure not to mix the flavors.

There was a time when everyone was like “you can’t parse html with regex, use beautiful soup!” And beautiful soup defaulted to a regex parser

While true in principle, writing grammars in regexes is problematic in practice: the syntax for the more advanced features (named submatches, lookahead, backreferences, etc.) is pretty complex, and refactoring the expression means you're working within a string literal, with no help whatsoever from your editor or IDE.

My "go to" solution for parsing (and validating/matching) non-trivial grammars is a library that wraps regexes and allows you to structure the grammar with entities above substrings of a string literal (including arbitrary code for transformations). PyParsing for Python, scala-parser-combinators for Scala, Grammar in Raku, PetitParser in Smalltalk, PEGs in Janet, parser combinators in F#, and so on. These are mostly internal/embedded DSLs, which makes them much easier to use than the typical lexer/parser generators, while giving you all the power to structure and evolve the grammar easily.

For simple grammars, a well-written library adds little overhead over plain regexes. However, grammars rarely stay simple - very often, during the course of development, you find edge cases or the need for extensions. If you started with a structured parser, you're fine: there are specific ways of evolving the grammar, and you can use normal refactoring tools to perform them. If you started with a regex, you quickly end up with a monster regex literal that becomes more brittle and harder to change with each modification.

One important property I look for in parsing libraries is the support for left-recursion. Memoizing/packrat parser generators can handle it gracefully, which is important, because if I'm implementing a published grammar, I want to encode it as closely to the original as possible. For the same reason, I prefer having dedicated tools for associativity and precedence (so that I don't have to invent names for intermediate levels).

TL;DR: yes, regexes are much more expressive than the "regular" in the name would imply, but they still have their limits. For parsing things, it's better to start with something that can work in the simple case fast (so no lex/yacc-style codegen from 2 separate external DSLs), but which also provides enough structure that adding good error handling, extending the grammar, attaching arbitrary code transformations, etc. won't be a big problem later.

Obligatory: https://stackoverflow.com/a/4234491 (tchrist's "Oh Yes You Can Use Regexes to Parse HTML!", which refers to https://stackoverflow.com/a/1732454/459233 "TONY THE PONY, HE COMES" (I won't risk copy-pasting the "corrupted-looking" version, heh))

omigosh - this is an internet classic that never gets old!

The last thing we need is huge regexs made by AI

Every time I cut-n-paste a regex into code, I comment with the url of the spell book page I copied so future me can answer, "WTF does this do again?"

I'm wary of external urls in code. Some plaintext comment would come in handy for the day the link inevitably goes dead.

Why could external URLs be a problem? And is it still one if you swap https to hxxps or something? What could go wrong with having a URL as a comment in code?

I put URLs there sometimes and think it's very helpful.

You don't control these external resources, and now the explanation of what your code does is tied to a site that could be taken down tomorrow, leaving you with a dead link and an unexplainable regex.

Agreed- I'm all for comments explaining a RegEx, but not hyperlinks in comments. The link inevitably goes dead and now you've left a helpful-looking present in a comment with dust inside.

> The regular expression is very simple

OT but this me-problem makes me angry every time I read it. Nothing is simple, otherwise it is trivial and not worth mentioning. I can't read over this without thinking that I'm not smart enough to wrap my head around something instantly.

Reply on news.ycombinator.com