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.
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.
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.
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 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.
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.
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.
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.
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).
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
22 comments
[ 2.0 ms ] story [ 11.7 ms ] threadNow they have three problems.
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.
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.
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.
Obviously they have their place, but I know a lot of the older guys seemed to love them way more than the young.
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?)
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.
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).
Never abuse "absolutely", and match != parse.