[regex] What do 'lazy' and 'greedy' mean in the context of regular expressions?

What are these two terms in an understandable way?

Best shown by example. String. 192.168.1.1 and a greedy regex \b.+\b You might think this would give you the 1st octet but is actually matches against the whole string. Why? Because the.+ is greedy and a greedy match matches every character in 192.168.1.1 until it reaches the end of the string. This is the important bit! Now it starts to backtrack one character at a time until it finds a match for the 3rd token (\b).

If the string a 4GB text file and 192.168.1.1 was at the start you could easily see how this backtracking would cause an issue.

To make a regex non greedy (lazy) put a question mark after your greedy search e.g

*?
??
+?

What happens now is token 2 (+?) finds a match, regex moves along a character and then tries the next token (\b) rather than token 2 (+?). So it creeps along gingerly.

Greedy Quantifiers are like the IRS/ATO

If it’s there, they’ll take it all.

The IRS matches with this regex: .*

$50,000

This will match everything!

See here for an example: Greedy-example

Non-greedy quantifiers - they take as little as they can

If I ask for a tax refund, the IRS sudden becomes non-greedy, and they use this quantifier:

(.{2,5}?)([0-9]*) against this input: $50,000

The first group is non-needy and only matches $5 – so I get a $5 refund against the $50,000 input. They're non-greedy. They take as little as possible.

See here: Non-greedy-example.

Why bother?

It becomes important if you are trying to match certain parts of an expression. Sometimes you don't want to match everything.

Hopefully that analogy will help you remember!

Taken From www.regular-expressions.info

Greediness: Greedy quantifiers first tries to repeat the token as many times as possible, and gradually gives up matches as the engine backtracks to find an overall match.

Laziness: Lazy quantifier first repeats the token as few times as required, and gradually expands the match as the engine backtracks through the regex to find an overall match.

+-------------------+-----------------+------------------------------+
| Greedy quantifier | Lazy quantifier |        Description           |
+-------------------+-----------------+------------------------------+
| *                 | *?              | Star Quantifier: 0 or more   |
| +                 | +?              | Plus Quantifier: 1 or more   |
| ?                 | ??              | Optional Quantifier: 0 or 1  |
| {n}               | {n}?            | Quantifier: exactly n        |
| {n,}              | {n,}?           | Quantifier: n or more        |
| {n,m}             | {n,m}?          | Quantifier: between n and m  |
+-------------------+-----------------+------------------------------+

Add a ? to a quantifier to make it ungreedy i.e lazy.

Example:
test string : stackoverflow
greedy reg expression : s.*o output: stackoverflow
lazy reg expression : s.*?o output: stackoverflow

try to understand the following behavior:

    var input = "0014.2";

Regex r1 = new Regex("\\d+.{0,1}\\d+");
Regex r2 = new Regex("\\d*.{0,1}\\d*");

Console.WriteLine(r1.Match(input).Value); // "0014.2"
Console.WriteLine(r2.Match(input).Value); // "0014.2"

input = " 0014.2";

Console.WriteLine(r1.Match(input).Value); // "0014.2"
Console.WriteLine(r2.Match(input).Value); // " 0014"

input = "  0014.2";

Console.WriteLine(r1.Match(input).Value); // "0014.2"
Console.WriteLine(r2.Match(input).Value); // ""

From Regular expression

The standard quantifiers in regular expressions are greedy, meaning they match as much as they can, only giving back as necessary to match the remainder of the regex.

By using a lazy quantifier, the expression tries the minimal match first.

'Greedy' means match longest possible string.

'Lazy' means match shortest possible string.

For example, the greedy h.+l matches 'hell' in 'hello' but the lazy h.+?l matches 'hel'.

Greedy means your expression will match as large a group as possible, lazy means it will match the smallest group possible. For this string:

abcdefghijklmc

and this expression:

a.*c

A greedy match will match the whole string, and a lazy match will match just the first abc.

Greedy means it will consume your pattern until there are none of them left and it can look no further.

Lazy will stop as soon as it will encounter the first pattern you requested.

One common example that I often encounter is \s*-\s*? of a regex ([0-9]{2}\s*-\s*?[0-9]{7})

The first \s* is classified as greedy because of * and will look as many white spaces as possible after the digits are encountered and then look for a dash character "-". Where as the second \s*? is lazy because of the present of *? which means that it will look the first white space character and stop right there.

Greedy matching. The default behavior of regular expressions is to be greedy. That means it tries to extract as much as possible until it conforms to a pattern even when a smaller part would have been syntactically sufficient.

Example:

import re
text = "<body>Regex Greedy Matching Example </body>"
re.findall('<.*>', text)
#> ['<body>Regex Greedy Matching Example </body>']

Instead of matching till the first occurrence of ‘>’, it extracted the whole string. This is the default greedy or ‘take it all’ behavior of regex.

Lazy matching, on the other hand, ‘takes as little as possible’. This can be effected by adding a ? at the end of the pattern.

Example:

re.findall('<.*?>', text)
#> ['<body>', '</body>']

If you want only the first match to be retrieved, use the search method instead.

re.search('<.*?>', text).group()
#> '<body>'

Source: Python Regex Examples

As far as I know, most regex engine is greedy by default. Add a question mark at the end of quantifier will enable lazy match.

As @Andre S mentioned in comment.

• Greedy: Keep searching until condition is not satisfied.
• Lazy: Stop searching once condition is satisfied.

Refer to the example below for what is greedy and what is lazy.

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Test {
    public static void main(String args[]){
        String money = "100000000999";
        String greedyRegex = "100(0*)";
        Pattern pattern = Pattern.compile(greedyRegex);
        Matcher matcher = pattern.matcher(money);
        while(matcher.find()){
            System.out.println("I'm greeedy and I want " + matcher.group() + " dollars. This is the most I can get.");
        }

        String lazyRegex = "100(0*?)";
        pattern = Pattern.compile(lazyRegex);
        matcher = pattern.matcher(money);
        while(matcher.find()){
            System.out.println("I'm too lazy to get so much money, only " + matcher.group() + " dollars is enough for me");
        }
    }
}

I'm greeedy and I want 100000000 dollars. This is the most I can get.

I'm too lazy to get so much money, only 100 dollars is enough for me