Why are regular expression quantifiers greedy by default?

Question

I can't count the number of times I've seen questions on StackOverflow related to regular expressions where the problem was due to the programmer not understanding the impact of greedy quantifiers. Most recently, Python regex issue — [\S\s]* vs \d*.

I wonder why regular expression quantifiers were defined to be greedy. It seems like this is less intuitive than non-greedy regular expressions. If someone writes a regexp like

BEGIN(.*)END

they intuitively expect the capture group to grab everything between adjacent BEGIN and END brackets. But if there are multiple BEGIN...END pairs, it will span all of them. You have to write

BEGIN(.*?)END

to express this. And I think non-greedy quantifiers like this didn't even exist until PCRE -- matching this was even more complicated then.

Non-greedy quantifiers are not a magic bullet solution for all such problems, but it seems like there would be fewer problems if they were the default.

EDIT:

I think I see a possible reason. If there's nothing after the quantifier, you usually want it to be greedy. My original answer to the above question had a bug, the regexp ended with Answer:\s*(.*?). By making this non-greedy, the last capture group matched an empty string rather than everything after the final Answer: prefix.

And also consider the \* there -- we want that to capture all the whitespace after the prefix, before grabbing the text in the capture group.

So the appropriate default really depends on what (if anything) is after the quantifier. And greediness is also often only an issue with .*, not if you quantify something more specific than ..

Is this all there is to it?

Answer 1

A regular expression, as the term is used here, is a mathematical construct; it is the formalism used to define regular languages. In that context, the Kleene star operator is neither greedy nor abstemious. Rather, it is non-deterministic: it will match as many times as necessary.

It's worth pointing out here that regular expressions define a "language", not a substring. In that sense, the regular expression matches (or recognises) the entirety of a sentence.

Using regexes to find substrings was a (very useful) adaptation of a theoretical concept to practical programming problems. But it introduces an ambiguity which was not present in the original: if the regex can match more than one different substring, which one should it choose?

The original regex libraries all chose the first matching substring (in a left-to-right scan), and of those matches which all start at the same position, they chose the longest one. These are the Posix semantics for regular expressions, which also define how subpatterns ("captures" between parentheses) correspond to substrings of the matched string. ("Captures" form no useful part of the theoretical model of regular expressions.)

The regular expression formalism has the enormous advantage that it can be compiled into a Deterministic Finite Automaton (DFA) which can then be used to perform a match -- or even a substring search -- in linear time. In effect, the DFA recognizes all possible matches in parallel; it is easy to make it recognize the longest match, by simply continuing until no further advance is possible. It would also be easy possible to recognize the shortest match, although that is not as common as you might think. (Consider, for example, recognizing numeric or identifier-like tokens: you really want to match the longest possible string.)

However, implementing abstemious repetition is not the same as implementing shortest match. Rather, it requires ordering possible matches by examining a subcomponent of the match. Since regular expressions do not need to be deterministic in submatches (and usually are not), ordering by subcomponent is non-trivial; it requires significant extra memory and time because many alternative partial matches may need to be remembered during the scan.

Once you have substring matches, possibly with captured submatches, you need to start worrying about resolving these ambiguities. And the Posix semantics are not always what are desired. Sometimes -- often, even -- one would want to find the shortest matching substring. (As in the BEGIN.*?END example you mention.)

Consequently, many regex libraries do not use this algorithm, preferring a backtracking recursive solution. One of the advantages of the backtracking algorithm is that it can cope with a number of extended regex operators which cannot be implemented with a DFA, including back-references which are not even context-free (in general). On the flipside, these operators can introduce pathological slow-down, and it is relatively easy to craft regexes which take exponential time to do a search. If you allow user-supplied ("tainted") regexes, this is a vector for DoS attacks. Even if you don't allow tainted regexes, you sometimes have to think carefully about how to write a given regex in order to produce as efficient a search as possible.

Over the years, regexes have drifted further and further away from their theoretical regular language roots. However, there are still contexts in which the original formulation and its guaranteed linear time complexity are useful:

• Lexical scanners, in which the regular expressions are not dynamic and therefore are usually compiled into the scanner. Since simple regular expressions are perfectly adequate for tokenising most programming languages, the efficient linear-time algorithm is preferred.

• As mentioned, tainted regular expressions, such as on-line search engines. See, for example, Russ Cox's re2 library, based on a (re-)discovery of the linear-time algorithm, which he wrote in order to protect the Google Code search engine from potential denial of service attacks.