11 ms·
The Greatest Regex Trick Ever (2014)
- aaronbrethorst 11y agoThis article desperately needs a tl;dr, but major props for the two regex tricks at the very top of the page.
- forrestthewoods 11y agoI thought the answer was going to be "tricking the world into thinking regex was a good idea". I've always considered regex to have the rare and elusive "write only" flag. Write only. As opposed to read only. Because once you write a regex that's it. You will never know what it does ever again.
- shurcooL 11y agoI'm glad I'm not the only one who feels this way. I feel like I gain more than I lose by simply excluding regexps from my toolbelt. (It's a personal choice, I'm not saying it'd be the same for others, since their values may differ from mine.)
- guard-of-terra 11y agoThis is a bit true, but when you want to get things done, one line regex is often better than a whole file of code. Write only regexes are trivial once you have tests: when you don't understand one, throw it off and replace with something you do. Tests pass? Here you go. Whereas having a whole file of many lines of code is much harder to replace when you don't understand what's it all about.
- stormbeta 11y agoSimple regexes are still fairly readable (e.g. a three number version string match), but if you find yourself having to worry about stuff like matching within escapable delimiters, it's time to put the regexes down and pick a different solution.
- Retra 11y agoMatching within escapable delimiters is not too hard. For instance this will match C-style escaped strings: "(\.|[^"])*" You just won't be able to nest them. You're either in a string or you aren't. You're never in a string inside another string.
- fsloth 11y agoI've found regexes very useful when writing quick parsers. For these cases it's often the simplest solution. If the alternative would be a huge chunk of hand written parsing code I would claim the regex is more maintainable.
- radicalbyte 11y agoIn general, yes. That's what I always document my regexes well and include write unit tests with all of the positive/negative test cases that I used whilst building the regex. That makes them pretty maintainable. Why go to this effort? Because for they're beautiful and a very powerful tool when used for the right problem. Unfortunately they're widely misused (i.e. email validation).
- Johnny_Brahms 11y agoI have taken to thoroughly explaining what a regex does in the code comments. Not just "match that and not that" but going through every character in the expression. It is a practice i took up when playing around with brainfuck. My magnum opus was a program that factored numbers in an arbitrary amount of time. That is _NOT_ something you hammer out in an afternoon, and without commenting everything thoroughly (like what I was doing, where I was in code execution, what state the whole program was in) I would never have made it. Non-related story time: At first when playing with brainfuck, I wrote my own BF-interpreter that compiled to an IL which was easier to debug (with my own interpreter that could give me stack traces with comments about where I was in memory and what the hell was going on). After a month, I really didn't need to. My brain had gotten used to reasoning about BF-code and I could actually understand what code was doing as long as I knew which kind of compiler/interpreter it was written for.
- krylon 11y agoUnless it is not overly complicated, it is possible to write regular expression in such a way you can later on understand what you were thinking at the time you wrote them (using the extended syntax available in Perl and elsewhere - it allows you to break up the regex into multiple lines and embed comments). It takes a little more effort, and one does not get the "look how dense it is"-rush, but I guess the same can be said for all code. There is a point where it breaks down, but there is a range of text-matching/extracting problems where regexes are both useful and - if one makes the effort - maintainable.
- TeMPOraL 11y agoJust use tests and comments. For instance, in many language it's trivial to declare regexp in multiple lines like this: regex = "(^[0-9])" //catch the initial digit (group 1) + "/" //skip the following slash + "([A-Z]+) //capture the identifier (group 2) ... Regexps are too powerful a tool to ignore. I'd much rather write a simple regex than a whole screenfull of code, especially when the former does the work faster (because regex engines are pretty efficient).
- to3m 11y agoAnother way of doing it is to use variables and helper functions, particularly if you're going to be creating lots of regexps from similar components. This is what I usually do in Python. For example, while making no promises about the value of this code specifically: def any(x): return x+"*" def many(x): return x+"+" def capture(x): return "("+x+")" def lit(x): return re.escape(x) # shorthand bol="^"; eol="$" ident="[A-Za-z_][A-Za-z0-9_]*"; find_function=(bol+any(" ")+lit("def")+many(" ")+ capture(ident)+any(" ")+lit(":")+ any(" ")+eol) You can handle more or less stuff this way according to how much you and/or your readers like regexp syntaxp. The above is probably further than I'd take it in practice; I'm familiar with the regular expression syntax, but I'd still probably at least use something like the `ident' variable just to keep clutter out of the regexp. (A nice demonstration of this sort of thing is emacs's rx module (see, e.g., http://emacswiki.org/emacs/rx http://emacswiki.org/emacs/rx). I couldn't find any good non-emacs documentation about this, nor much that would make sense to people unfamiliar with lisp, but when you're in emacs you can get help on it using C-h f rx RET.)
- TeMPOraL 11y agoI agree. In terms of variables, I think a good strategy is assigning names to meanings, e.g. PRODUCT_ID = "[0-9]{2}[A-Z]{1,5}" ... CUSTOMER_ID = "[0-9]{2}[A-Z]{1,5}" ... ... regexp = "(" + PRODUCT_ID + ")" // capture product ID in group 1 + "something something" // something something + "(" + CUSTOMER_ID + ")"; // capture customer ID in group 2 In this example, even though the two constants contain the same regular expresison, they refer to two different concepts. Part of the problem with understanding regexp-based code is connecting parts of the expression with what they mean. Above strategy addresses this. I also like assigning names to capture groups I depend on. So instead of, later in code, asking for e.g. matcher.group(2), I ask for matcher.group(GROUP_CUSTOMER_ID). Makes for a much more readable code. Speaking of Emacs's rx, it's absolutely amazing and I'm sad that I only discovered it just few days ago :(. Another similar concept, from the other side of "code = data" equality is Common Lisp's (of course it's Lisp again) CL-PPCRE and its internal representation of regular expressions: * (parse-string "(ab)*") (:GREEDY-REPETITION 0 NIL (:REGISTER "ab")) * (parse-string "(a(b))") (:REGISTER (:SEQUENCE #\a (:REGISTER #\b))) * (parse-string "(?:abc){3,5}") (:GREEDY-REPETITION 3 5 (:GROUP "abc")) You can encode any regexp you want as an S-expression, trading off conciseness for legibility. See http://weitz.de/cl-ppcre/#create-scanner2 http://weitz.de/cl-ppcre/#create-scanner2 for more.
- singingfish 11y agoI once used the wonderful perl module [Regexp::Assemble](https://metacpan.org/pod/Regexp::Assemble https://metacpan.org/pod/Regexp::Assemble) to produce a regexp to match [every single suburb/town name in Australia](https://gist.githubusercontent.com/singingfish/d43c884fbac0089d8523/raw/63eeaf88a2e8d896c07da3b2440080233dd48395/regex%2520for%2520every%2520suburb%2520name%2520in%2520australia.txt https://gist.githubusercontent.com/singingfish/d43c884fbac00...) from a csv file download from the post office website. It was blazingly fast ... considering (better than the recdescent parser I'd been previously experimenting with). Here's the code that generated the regex: use Regexp::Assemble; my $ra = Regexp::Assemble->new; while (<$FH>) { $csv->parse($_); next if $. == 1; my @fields = $csv->fields; $ra->add($fields[1]); } my $suburbs = $ra->as_string;
- voltagex_ 11y agoCan you still get that csv file? I thought AusPost had started charging for everything.
- singingfish 11y agoyeah I heard that, not very sportsmanlike of them if it's the case.
- x0 11y agobam http://badcunt.club/cant/stop/information/babe/every-australian-postcode.csv http://badcunt.club/cant/stop/information/babe/every-austral...
- x0 11y agoWoah, do you mean this? If so, wow, never thought my tiny little data collection would come in handy. http://badcunt.club/cant/stop/information/babe/every-australian-postcode.csv http://badcunt.club/cant/stop/information/babe/every-austral...
- voltagex_ 11y ago
- leeoniya 11y agothis one is great, too. matches all printable ascii characters: [ -~] http://www.catonmat.net/blog/my-favorite-regex/ http://www.catonmat.net/blog/my-favorite-regex/
- ExpiredLink 11y agoEnglish only.
- joosters 11y agoHence the ASCII in the description.
- ExpiredLink 11y agoSince accented characters are used in the English language it's not even 'English only'.
- leeoniya 11y ago"printable ascii" describes everything that it is and everything that it isn't; no further clarification is needed. https://en.m.wikipedia.org/wiki/ASCII https://en.m.wikipedia.org/wiki/ASCII
- ExpiredLink 11y agoI will spare us an answer because it wouldn't be printable English.
- tokenizerrr 11y agoYou are the only one who said "printable English". Everyone else has said "printable ASCII". Do you perhaps not understand what ASCII is?
- edoloughlin 11y agoI almost wrote this off as it seemed to be about how to write unmaintainable regex soup but the author pulled something quite elegant out of the hat at the end.
- smegel 11y ago> Match Tarzan but not "Tarzan" Unfortunately it doesn't work. Let's say I wanted to match a string following Tarzan but not "Tarzan", I will try his technique: ("Tarzan"|(Tarzan))\s+and JillOfTheJungle Unfortunately this matches both: "Tarzan" and JillOfTheJungle and Tarzan and JillOfTheJungle Or maybe he meant: > Capture Tarzan but not "Tarzan"
- geocar 11y agoa=/(?:"Tarzan"|(Tarzan))\s+and JillOfTheJungle/; matched = !!a.exec(x)[1] Works fine. People often forget to solve the problem they need to solve (match x), and instead work on other things (find a regex to match x).
- jameshart 11y ago"People often forget to solve the problem they need to solve (match x), and instead work on other things (find a regex to match x)." Completely agree. One common mistake is building a complex regex to match the elements you want to find from a string, when an easier approach is to split the string on a simple regex that matches the things you want to throw away.
- jameshart 11y agoYes, when you apply a technique incorrectly, it often doesn't work. "Tarzan"\s+and JillOfTheJungle|(Tarzan\s+and JillOfTheJungle) Seems to meet your needs?
- smegel 11y agoNo I dont want to capture anything, I just want to match a string that contains Tarzan but not "Tarzan". Your example seems to match both both. Is that too much to ask?
- jameshart 11y agoNo, it's not. Just run through the matches returned by this regex, and reject the ones which don't have a captured group. Done. Did you want a more complex solution?
- wodenokoto 11y agoGenerally I found it strange how difficult it is to do a search for everything except something. The script looks elegant, but like the author mentions, doesn't work in a text-editor, so I would consider it the greatest.
- ExpiredLink 11y agoMany searches that you can easily explain to your grandmother are difficult with regex.
- smsm42 11y agoVery nice trick, while using of foo|(bar) is very simple, somehow I don't see such approach being used very often, and it looks like it could simplify a number of things.
- wonnage 11y agoRegular expressions match regular languages (hence the name). If your language involves pairs of things (e.g HTML), it's not regular. Perl hacked support for this in via backreferences and other extensions, but these are slow and illegible. Use a proper context-free grammar parser if you need to parse a context free grammar, you know? More broadly, people fear and misunderstand regexes because they have no idea how they work. It becomes much easier if you understand how they map to deterministic finite state machines. Recommended reading: https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html Once you understand how they work, you can basically read a regex left to right and intuitively know all the strings they'd match. There is no such thing as an unmaintainable/illegible basic regex - they're just words with some placeholders in them - it's when you cram in extended functionality (which is basically a programming language where all the keywords are single characters) that shit hits the fan.
- ExpiredLink 11y agoIOW, study the implementation to understand the interface.
- kps 11y agoMore like, know what the notation is a notation of to understand the notation.
- ginko 11y ago>Use a proper context-free grammar parser if you need to parse a context free grammar, you know? The thing is that regular expression are supported as language feature or as standard library in pretty much every language. If you want to build a proper parser, you'll have to jump through a lot more hoops. For instance for C++ I've tried tons of different lexer and parser generators and they all suck for various reasons. (Verbose syntax, uses global variables, C only, lexer not compatible with parser and vice versa,..) Most people seem to end up writing their own parsers from scratch. The only time I've ever seen parsing done right is with Parsec for Haskell.
- 11y ago
- logn 11y agoMore like the author tricked you by changing the problem halfway through the very long article. Try this instead: (?:(?<!")|(?!Tarzan"))Tarzan
- edward 11y agoParsing HTML with a regex? You should read this answer on Stack Overflow: http://stackoverflow.com/a/1732454/84250 http://stackoverflow.com/a/1732454/84250
- brey 11y agoVery elegant, I like it. Except I'm now having a major case of semantic satiation for the word "Tarzan"...
- jwhite 11y ago... and now you have two problems.
- chris_wot 11y agoI love regexes but they make my head hurt. I really rather badly need to spend some time properly learning it inside and out.
- GlennS 11y agoI first learned them properly by reading through [http://www.regular-expressions.info/tutorial.html http://www.regular-expressions.info/tutorial.html]. I'd also recommend the website as a good reference for when you forget things.
- userbinator 11y agoThat reminds me of something else with regex which I thought was extremely clever: implementing an A* search: http://realgl.blogspot.com/2013/08/battlecode.html http://realgl.blogspot.com/2013/08/battlecode.html
- kragen 11y agothat is a very nice hack. this kind of 'do as much work per standard library call as you can' approach is pretty much the way to go in interpreted languages like python or octave, which is in part why numpy is so popular — not only does it allow you to program at a higher level of abstraction, it also makes your program run more efficiently. however, i think that technically, that's not an A* search he implemented, just a breadth-first search. i'm not an expert (i've never even implemented A* search), so i could be mistaken. i'm interested to hear whether other people agree.
- pkaye 11y agoReminds me of this quote from Jamie Zawinski: "Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems."
- based2 11y agohttp://www.rexegg.com/regex-humor.html#twoprobs http://www.rexegg.com/regex-humor.html#twoprobs
- jameshart 11y agoWhy does this remind you of that quote? Because it's about regular expressions? Because it seems to me that if you have the problem described in this post, and you solve it the way the post describes, using regular expressions, you have solved your problem, regardless of what jzw says.
- incepted 11y agoMeh. I think an even greater Regexp trick is the regular expression that determines primality: http://stackoverflow.com/questions/3296050/how-does-this-regex-find-primes http://stackoverflow.com/questions/3296050/how-does-this-reg...
- metafunctor 11y agoThe article actually talks about the prime validator regex, and goes on to say that while it's an awesome trick, it is not the "best ever" because it has limited scope. I for one think the trick described in the article is pretty useful, and might even use it someday (and possibly have already without realizing it).
- JoeCoder_ 11y agoHere is the TL;DR. This regex matches Tarzan but not "Tarzan": "Tarzan"|(Tarzan) You can also include more than one case of what you don't want to match. This one also finds only the cases of Tarzan that don't match the first three patterns: Tarzania|--Tarzan--|"Tarzan"|(Tarzan) You can even use more complex regexes. This matches all words not in an image tag: <img[^>]+>|(\w+) And likewise this matches anything not surrounded by <b> tags: <b>[^<]*</b>|([\w\s]+)
- ajnin 11y agoThat's not exactly it, the regexp does match both "Tarzan" and Tarzan, but the capture group 1 will only be set for strings that contain Tarzan without quotes. So by examining that group after matching you know in which case you are. (that also means you can only use this "trick" when you can examine capture groups, i.e. not generally in editors).
- raldi 11y ago<img[^>]+>|(\w+) ...has some bugs. The part on the left mistakenly matches `<imgasvaasdf>` and mistakenly misses `<img>`. Better would be: <img\b.*?>|(\w+)
- bro-stick 11y agoUnimpressive. The author of this article obviously didn't have a compiler class where one learns how regexes are basically glorified NFAs that are deterministicly convertible into a much more efficient DFA state machines (read: PCRE JIT), instead of assuming regexes are processed by O(N^2) algorithms.
- kragen 11y ago'convertible into a much more efficient DFA state machines (read: PCRE JIT)' pcre supports reduction to dfa and also jit, but not only are they not the same thing, they are mutually exclusive. also, ever regexp engine i've seen that supports capturing and backreferences uses not worst-case quadratic-time but actually worst-case exponential-time algorithms, although i'm pretty sure this isn't actually unavoidable. may i suggest that the next time you think about posting a comment that begins with 'Unimpressive. The author of this article obviously didn't', that you include less than one major technical error per sentence in it.
- rbobby 11y agoMaybe I'm too old. I tend to think of a regex as either matching or not matching. Finding a bit of code that uses a capture to determine whether a match was found seems like it would easily be confusing/inobvious. Some pretty clear commenting and it would be ok... maybe. Also... I wonder how well it would work as part of a larger regex, one that already uses captures (or non-capturing groups)? The examples are all nice, short and sweet... but how often do regex based solutions stay short and sweet? A few maintenance cycles/years and suddenly you've got this funky regex/capture thing that only Bob understands and he's way to busy to talk to you for 5 minutes... and once you change things then Bob suddenly finds time to review your code to complain how you broke it for such a simple change. There goes your bonus you told the wife you were sure to get so you could take her and the kids on vacation. The day after your divorce finalized Bob sends you a fix request to use that improved scheme of yours because the old regex one isn't flexible enough anymore.
- jfb 11y agoConvincing the world that they don't exist?
- amluto 11y agoHow does this handle '"Tarzan" Tarzan'?
- rntz 11y agoThis "trick" is simply exploiting a bug in regex implementations. The regex "Tarzan"|(Tarzan) should match the string "Tarzan" in two ways: first, matching the entire string; and second, matching the substring "Tarzan" in the whole string "\"Tarzan\"". But most regex implementations drop extra overlapping matches. I argue this is incorrect behavior, because it complicates understanding what a regex means - you have to understand the /order/ in which your regular expression matcher interprets your regular expression, which is an implementation detail. I conjecture that a DFA-based regex engine would not be able to exhibit this order-biased behavior, at least not with the standard approach. However, it's interesting that this "bug" turns out to be a "feature" for the case of excluding other behavior. I'm not sure what conclusion to draw from this.
- GhotiFish 11y agoGiven a string "aaabbb" what should the results be, of the regular expression "(aa|aaa)(abbb|bbb)"? $1 = ? $2 = ?
- rntz 11y agoI believe it matches in three ways: - the whole string, grouped as "(aa)(abbb)", - the whole string, grouped as "(aaa)(bbb)"; - the substring "aabbb", grouped as "(aa)(bbb)".
- GhotiFish 11y agoSorry, I made an assumption there that you were talking about the practical applications of regex, not the theoretical applications, and I was asking you to explain how you would practically return multiple matches in... any environment. This was a small regex designed to create multiple answers to see how you resolved the issue, obviously we can engineer regexes that return far more results. So something's got to give. I don't agree with you that regex's innately imply all matches are valid.
- rntz 11y ago
- bza 11y agoThis technique is unreliable in practice, and the author's discussion is confused. First, their explanation doesn't make sense. They're supposing that there's some determinacy in the order in which a matcher can be expected to examine the different possible matches. But that's provably not the case: if it were, then deterministic and non-determinsitic finite automata would be inequivalent. But the technique in question does seem to require some determinacy as to which of several alternatives will match against a string. Where does that determinacy come from? The semantics of the alternation operator (the '|') as usually formulated don't specify any preference among alternations. For that reason, POSIX additionally requires that a matcher return the longest possible match (and if there are several such, the leftmost is what must be returned). Where you do find an explicit guarantee concerning which of several different possible ways of matching will be preferred, it's almost certainly because the engine is aiming at POSIX compliance. Such compliance has a significant cost, though, as it requires the matcher to consider all possible matches (in order to find the largest). For that reason, most regex engines forego strict POSIX compliance and only guarantee that some match will be returned if one exists, not that that match will be the leftmost longest. Some engines offer the option of requesting strict POSIX behavior, but the default will always be to eagerly return the first match encountered (and recall the point above that there provably can't be a guarantee about the order in which matches are encountered, in general). You should never do this in production code unless you're sure that your matcher is POSIX-compliant.