The Greatest Regex Trick Ever (2014)

http://www.rexegg.com/regex-best-trick.html

by user_235711 • 11 years ago

227 131 11 years ago

This article desperately needs a tl;dr, but major props for the two regex tricks at the very top of the page.

I 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• 11 years ago

I'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• 11 years ago

This 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• 11 years ago

Simple 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• 11 years ago

Matching 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• 11 years ago

I'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• 11 years ago

In 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• 11 years ago

I 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• 11 years ago

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

TeMPOraL3• 11 years ago

Just 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• 11 years ago

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

singingfish2• 11 years ago

I once used the wonderful perl module [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/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_2• 11 years ago

Can you still get that csv file? I thought AusPost had started charging for everything.

singingfish2• 11 years ago

yeah I heard that, not very sportsmanlike of them if it's the case.

x02• 11 years ago

Woah, 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-austral...

leeoniya2• 11 years ago

this one is great, too. matches all printable ascii characters:

[ -~]

http://www.catonmat.net/blog/my-favorite-regex/

ExpiredLink5• 11 years ago

English only.

joosters6• 11 years ago

Hence the ASCII in the description.

edoloughlin• 11 years ago

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

smegel2• 11 years 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• 11 years ago

    a=/(?:"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).

jameshart5• 11 years 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.

jameshart5• 11 years ago

Yes, when you apply a technique incorrectly, it often doesn't work.

"Tarzan"\s+and JillOfTheJungle|(Tarzan\s+and JillOfTheJungle)

Seems to meet your needs?

smegel2• 11 years ago

No 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?

wodenokoto2• 11 years ago

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

ExpiredLink5• 11 years ago

Many searches that you can easily explain to your grandmother are difficult with regex.

smsm42• 11 years ago

Very 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• 11 years ago

Regular 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

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.

ExpiredLink5• 11 years ago

IOW, study the implementation to understand the interface.

kps• 11 years ago

More like, know what the notation is a notation of to understand the notation.

ginko2• 11 years 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.

hacker_92• 11 years ago

It's a mistake to write your own parser because they can get so complex so quickly to even do basic stuff, and you'll lose sight of the original goal of the project. See Prolog - a whole programming language built around the idea of parsing language (albeit NLP)!

I suggest you take alook at Antrl4 for a powerful but easy to use parser plus lexer combo.

dankohn1• 11 years ago

Obligatory "You can't parse HTML with Regex" link: http://stackoverflow.com/a/1732454/1935918

gavinpc• 11 years ago

You might be interested in OMeta, whose goal is to make language experimentation quicker and more accessible by providing a kind of interface layer between a declarative grammar and a host language. I'm still reading the paper, so I can't vouch for it yet. But it's from VPRI and has Alan Kay's backing.[0]

[0] http://www.tinlizzie.org/ometa/

eru3• 11 years ago

That's too optimistic. Here's a challenge for you: write a (grep) regular expression that checks a decimal number for divisibility by 7.

That's totally a regular language, but I doubt you'll find a legible way to express it.

hacker_92• 11 years ago

What does that have to do with the language syntax..

3dfan• 11 years ago

If the number N can be converted to a string of length N, this regex checks if it's divisible by 7:

    ^(.......)+$

agumonkey• 11 years ago

Obligatory prime regex link: http://www.catonmat.net/blog/perl-regex-that-matches-prime-n...

joosters6• 11 years ago

I use regexes all the time for parsing data on a variety of 3rd-party websites. Just because they aren't perfect at matching every potential theoretical situation doesn't mean they shouldn't be used. In practice, regexes can be a simple and reliable way to grab data out of HTML. Don't dismiss them out of hand!

Another point, generally overlooked by the theoretical purists, is that HTML in the wild is rarely correct, and your perfect HTML parser will barf when trying to process it. Regexes on the other hand don't have to care about exact syntax and can cope with horribly mangled data.

inglor2• 11 years ago

Good HTML Parsers typically use engines of browsers and will actually match websites very well. They'll let you use selectors and not regex and are a lot more accurate.

It also won't break if the website adds a single attribute or a quirky value.

lojack• 11 years ago

But what's the comparative advantage over a faster, easier to comprehend, and more correct html parser?

olavk4• 11 years ago

It is not a question of "theoretical purity", it is a fact that it is simply not possible in the real world to parse a html document using only a regex. But this is often misunderstood as saying they regex shouldn't be used in parsing. Regex'es are quite useful as a part of a parsing process, eg. to locate the tags and attributes and separate them from text. This is the scanning or tokenization step. But after this, you need to create a hierarchical data model corresponding the DOM, and you need to do that outside of a regex. A regex outputs only a string or flat list of strings (in all regex libraries I know of), it does not output a hierarchical data structure, so it follows that you need something more than a single regex to parse a hierarchical data structure like a programming language or a html document.

Only exception would be if you need to extract very specific data items which are not hierarchical in nature. Eg. you want to extract only the specified character encoding or something like that.

Your point about the "perfect HTML parser" is kind of missing the point, since regexes does not magically solve the problem of imperfect HTML either. A perfect HTML parser would be one which implement HTML spec fully, including the error recovery rules. These are quite complex, eg, if you reach a <p> then an open <h1> is implicitly closed, but an open <i> is not. Try implementing this logic in a single regex! ("Regexes does not care about perfect syntax" - what does that even mean? A regex match exactly what you tell it to match, just like a parser parses what you program it to parse.)

evilotto2• 11 years ago

An ordinary regex obviously can't parse html, because html is not regular (given nested elements and the pumping lemma). But what you can easily do with a regex is to tokenize html - extract anything that looks like a start tag, for example. The simply approach will obviously get some things wrong - a tag inside a comment is meaningless, for example - but for a lot of uses, this difference simply isn't important.

If the job is to extract all links from a webpage, regexes will do just fine, and will probably be easier to write and understand than alternate approaches. (This is absolutely not a fair comparison of course; you could compare writing a regex engine to writing a html parser. But I digress.)

If the job is to determine whether a given webpage is a member of the set that includes all valid html documents. then a regex is not sufficient.

If the job is to extract a list of syntax tokens from a webpage, a regex is likely fine.

If the job is to assign semantic meaning to every token in that list, a regex just won't work.

Either way, the point is to know what you're doing. Much "parsing" of webpages is not parsing in the formal language sense, and who cares that it isn't because it doesn't need to be.

cameldrv• 11 years ago

Except nobody uses strict regexes anymore. In particular, without the minimal match (*?) operator, they're of limited utility in real-world situations. It's easy to tell people to use a context-free grammar parser, but the ones that I know of require a lot more setup than a one-liner regex. There's probably an opportunity for someone to really improve the practice of programming by coming up with a compact language to specify and match structures in CFGs, or some subset of them.

ulrikrasmussen• 11 years ago

Minimal match is still OK, that will only affect disambiguation and won't allow you to write a pattern that does not denote a regular language.

paulmd3• 11 years ago

JSON-Schema and XML-Schema provide the "specify and match" functionality, in the sense of deciding whether or not a given instance of a document conforms to a defined standard. For simple regex-style queries there are XPath and JSONPath expressions.

If you want to actually touch them as plain objects it's a very straightforward task of implementing a data provider to marshal the objects. In Java this is provided by libraries such as Jackson (JSON) and JAXB (XML). These basically work just like Hibernate.

JSON and XML cover many of the real-world use cases of parsing such CFGs. If you make your data fit into one of those boxes it's very straightforward to validate or marshal them according to those schema protocols. They obviously do have a greater complexity than just writing a regex, but that's kind of the nature of using a more expressive language, and it's by no means an insurmountable increase.

jameshart5• 11 years ago

Not sure I understand the relevance of this comment to the post in question. Unless your objection is that using capture groups in this way is an example of 'cramming in extended functionality'?

On the other hand, this post has spawned the usual regex thread including a zalgo link and a pointer to a regex that finds prime numbers, so I guess you've done your part to perpetuate regex mythology.

nmadden8• 11 years ago

I agree with the general gist of your post, but I should point out that all finite languages are regular. So while potentially infinite HTML documents cannot be parsed by regular expressions, they don't turn up very often.

colanderman2• 11 years ago

You're missing the distinction between a finite language, and an arbitrarily large finite production of an infinite language.

No-one cares about "infinite HTML documents". I don't even think the Chomskyan hierarchy concerns itself with languages with "infinite" productions. All you have to worry about is infinite languages -- i.e., languages with arbitrarily large productions.

There's a key difference between "infinite" and "arbitrarily large": the latter is quantifiable. While indeed to can build a regular expression to match any finite subset of HTML, it can only match HTML documents up to some fixed size. I can always give you a (finite!) document that is one tag deeper that your regex will choke on.

"But recursive parsers have the same issue!" you say. "Their stack will run out of memory at some point!" Yes, but they have a key difference: the amount of stack (memory) they require is bounded by the size of the document. This is not true for a regular expression! In fact, not only would a regular expression to match a given subset of HTML require memory exponentially proportional† to the size of the document, the automata itself would be similarly massive!

I really wish someone came up with and promulgated a concise handy built-in ubiquitious equivalent of regular expressions for, say, PEGs. The closest I've seen are DCGs in Prolog. Would make so many parsing problems more easy to do correctly!

† It's possible I'm wrong about this since it's early morning and I'm basing this off my intuition rather than a proof. The part about the automata itself being exponential w/r/t the size of the document is definitely true though.

ised• 11 years ago

"There is no such thing as an unmaintainable/illegible basic regex..."

To someone who knows BRE. I am one of those people. It's ERE and PCRE I do not understand very well.

Sharing solutions to common problems using BRE on HN always seems to trigger (unwarranted) criticism using either of the exact words you mention, or synonyms for them. "Unmaintainable" (by who?). "Illegible" (to who?).

I "maintain" 100's of BRE scripts. They are perfecty legible to me. None of them are so complex I cannot re-write them in a short time. It is the structure of the input that is complex and which takes time to recall.

I also use lex, a common utility found on almost all UNIX derived OS; this article seems to ignore that option. I like to think it's faster than Perl or Python, but I cannot say for sure.

kevin_thibedeau• 11 years ago

I like to think it's faster than Perl or Python, but I cannot say for sure.

It is. I implemented an assembly language parser with pyparsing. It worked okay but the function call overhead with a combinator-based parser handling both the lexing and grammar was murder. I replaced it with regexes and got a 6x speedup. Not something I would do with a complex grammar though. Native code would obviously blow this away in speed but it is fast enough now.

0x400614• 11 years ago

When quoting the article please put quotes around the text, or use the `>` character for each line you quote. Thank you.

logn• 11 years ago

More like the author tricked you by changing the problem halfway through the very long article. Try this instead:

  (?:(?<!")|(?!Tarzan"))Tarzan

edward• 11 years ago

Parsing HTML with a regex? You should read this answer on Stack Overflow: http://stackoverflow.com/a/1732454/84250

brey• 11 years ago

Very elegant, I like it.

Except I'm now having a major case of semantic satiation for the word "Tarzan"...

jwhite• 11 years ago

... and now you have two problems.

chris_wot• 11 years ago

I love regexes but they make my head hurt. I really rather badly need to spend some time properly learning it inside and out.

GlennS• 11 years ago

I first learned them properly by reading through [http://www.regular-expressions.info/tutorial.html]. I'd also recommend the website as a good reference for when you forget things.

userbinator• 11 years ago

That 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

kragen3• 11 years ago

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

pkaye2• 11 years ago

Reminds 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• 11 years ago

http://www.rexegg.com/regex-humor.html#twoprobs

jameshart5• 11 years ago

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

evilotto2• 11 years ago

When I'm faced with a problem, I think about using recursion. Then I have two problems. Then I think about using recursion. Then I have three problems. Then I ...

pkaye2• 11 years ago

Because people think they are clever and write difficult to maintain expressions that tend to have flaws.

JoeCoder_• 11 years ago

Here 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• 11 years ago

That'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• 11 years ago

    <img[^>]+>|(\w+)

...has some bugs. The part on the left mistakenly matches `<imgasvaasdf>` and mistakenly misses `<img>`. Better would be:

    <img\b.*?>|(\w+)

incepted• 11 years ago

Meh.

I think an even greater Regexp trick is the regular expression that determines primality:

http://stackoverflow.com/questions/3296050/how-does-this-reg...

metafunctor• 11 years ago

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

bro-stick4• 11 years ago

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

kragen3• 11 years 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• 11 years ago

Maybe 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• 11 years ago

Convincing the world that they don't exist?

amluto• 11 years ago

How does this handle '"Tarzan" Tarzan'?

rntz3• 11 years ago

This "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.

GhotiFish2• 11 years ago

Given a string "aaabbb"

what should the results be, of the regular expression "(aa|aaa)(abbb|bbb)"?

$1 = ?

$2 = ?

rntz3• 11 years ago

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

bza• 11 years ago

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

The Greatest Regex Trick Ever (2014)

Related Stories