6
$\begingroup$

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 \s* 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?

$\endgroup$
5
  • $\begingroup$ The PCRE are different concept than regular expressions here. $\endgroup$
    – Evil
    Commented Nov 21, 2017 at 2:24
  • $\begingroup$ I know there are mathematical and programming regular expressions, but this seemed too general for SO, so I thought it would be appropriate here. Isn't the design of programming languages and libraries a CS issue? $\endgroup$
    – Barmar
    Commented Nov 21, 2017 at 5:46
  • $\begingroup$ Ok, well, it is mostly about PCRE, particular implementation, which is strictly more powerful than RE. The tag may be misleading and with heavy comments on SO questions I wanted to be sure this is intented. The design of programming languages: yes, libraries: not really. The "Edit" is not needed in the post. I am not sure how the answer should look like, the design was made very long time ago, in the most cases lazy eval is faster than greedy one, but the choice had been made. Now it will be hard to guess the basis for that decision. $\endgroup$
    – Evil
    Commented Nov 21, 2017 at 6:15
  • $\begingroup$ Regular expressions existed for many years before PCRE, they were used in text editors for search/replace. For searching the difference between greedy and non-greedy is irrelevant, but it matters if you're replacing since a greedy RE will cause you to replace too much at once. And it's in this mode that it causes problems in programming. $\endgroup$
    – Barmar
    Commented Nov 21, 2017 at 15:42
  • $\begingroup$ Barmar, REs were also used by tokenizers. In that use case, abstemious matching would always identify only the first digit in a number or the first letter in an identifier, which is generally not what is wanted. I tried to make this clearer in my answer. $\endgroup$
    – rici
    Commented Nov 21, 2017 at 15:58

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ "Using regexes to find substrings was a (very useful) adaptation of a theoretical concept to practical programming problems." - You're not wrong, but I think your answer is a bit misleading here, you make it seem as if the original interpretation of regular expressions is somehow more theoretically pure. Submatching has been formalized. But it's true that this is a relatively recent development AFAIK (since about 2000 or 2005?). $\endgroup$ Commented Mar 2, 2022 at 3:10
  • $\begingroup$ "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 [...]" - I think this isn't correct. See Russ Cox's blog post (section "Digression: POSIX Submatching"), as far as I understand Cox implies that the POSIX semantics are a relatively recent invention. His claim about POSIX disambiguation rules being difficult to implement is coroborrated by a couple of papers published around 2010. $\endgroup$ Commented Mar 2, 2022 at 3:15
  • $\begingroup$ The papers find (or claim, at least) that almost all implementations are buggy, see, e.g., the slides accompanying the "POSIX Regular Expression Parsing with Derivatives" paper: jaist.ac.jp/flops2014/lu.pdf $\endgroup$ Commented Mar 2, 2022 at 3:18
  • $\begingroup$ " it requires significant extra memory and time because many alternative partial matches may need to be remembered during the scan." - I think this is wrong? You seem to imply that non-greedy Kleene iteration can't be implemented with finite automata? The TRE regexp library does, in fact, support non-greedy iteration, and it should fall back to backtracking only in case back-references are used. $\endgroup$ Commented Mar 2, 2022 at 3:25
  • $\begingroup$ "Consequently, many regex libraries do not use this algorithm, preferring a backtracking recursive solution." - This is misleading in the context of your answer: backtracking does enable "irregular" features such as back-referencing, but I don't think it enables more freedom regarding disambiguation. $\endgroup$ Commented Mar 2, 2022 at 3:38
2
$\begingroup$

@rici wrote a very good answer. I actually intended to write a comment but I write it as answer instead.

I can think of only these reasons: first POSIX as mentioned before. Second a misunderstanding. Third, formal language theory could have influenced it.

For the first reason, my subjective opinion is, the best way of implementing POSIX is ignoring it. Its usability level is outdated. But that's not the debate.

For the second reason, the misunderstanding is that the original concept of .* – matching any text until end of line/string – would necessitate greedy semantics. But it may as well be lazy (frugal, abstemious) and still match at the end of the string. The end of (search) string would be a special generic character which is invisible (and not encoded in bits) but exist after the last encoded string character. This special character is an assertion which matches, if nothing else in the regex can match anymore at the current point in search (subject string).

So while regular languages indeed were invented for verifying (deciding) whole strings, not just parts within them, adapting them to search within strings requires the above mentioned adaption which is what humans probably intuitively understand. So a* would mean a*(?!a) but not a*(?=) as it is usually translated.

For the third reason, greedy quantification is required if you need to match a full list of consecutive repeated patterns when you don't have anchors or assertions available (as was the case in the early regex versions) while ignoring anything between these repeated patterns. That said, greedy quantifiers are semantically rather not suited for search within strings but rather for verification of entire strings. (EDIT: I saw that greedy quantification also is exploited to do backwards search (from right to left) when used in assertions.) And this "verification" is what regular languages are doing in formal language theory. In terms of traditional formal language theory, a* is understood as \Aa*\Z in practice. Under these semantics, having greedy quantifiers are probably more performant because they are looking at the end of string to match the subsequent part of the regex instead of trying to match the subsequent part at every visited non-deterministic branch point.

Conclusion (my usability perspective)

I don't see "greedy by default" to make sense in practice because it's not the common case for the application in searching/tokenization. I very rarely require greedy quantifiers for searching (probably never?). Backwards search is a use case for greedy quantification but how often appears backwards search compared to forwards search? Greedy quantifiers make sense if you want to get the last match of a subsequent regex part in the entire subject string but most of use cases known to me match things locally.

My honest recommendation is to blatantly ignore POSIX RegExp standards for usability's sake, write new history and turn the quantifier convention into lazy by default. [Probably also non-backtracking as default, but another story.]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.