Quantifiers | Regular Expression

Introduction

Quantifiers can be used to specify number of times a token should be matched by the regex engine. Below are common qualifier used in regular expression

? : Match the token zero times or exactly once
* : Match the token zero or more times
+ : Match the token one or more times
{m,n} : Match the token between m and n (both including) times, where m and n are natural numbers and n ≥ m.

Greedy Quantifier

A greedy quantifier always attempts to repeat the sub-pattern as many times as possible before exploring shorter matches by backtracking. Generally, a greedy pattern will match the longest possible string. By default, all quantifiers are greedy.

Lazy Quantifier

A lazy quantifier always attempts to repeat the sub-pattern as few times as possible, before exploring longer matches by expansion. Generally, a lazy pattern will match the shortest possible string. To make quantifiers lazy, append ? to the existing quantifier i.e.

??
*?
+?
{m,n}?

Example

Consider below string

aaaaaAlazyZgreeedyAlaaazyZaaaaa

Greedy repetition A.*Z yields 1 match: AlazyZgreeedyAlaaazyZ while lazy pattern A.*?Z yields 2 matches: AlazyZ and AlaaazyZ .

In Greedy search, when it matched the first A, the .*, being greedy, tries to match as many . as possible.

// 1
aaaaaAlazyZgreeedyAlaaazyZaaaaa
     \________________________/
      A.* matched

// 2
aaaaaAlazyZgreeedyAlaaazyZaaaaa
     \_______________________/
     A.* matched, Z can't match

After this match whole string is used, since the Z is still left to match, the engine backtracks, and .* must then match one fewer (2). This happens a few more times, until it finally comes as given below. Now Z can match, hence the overall pattern matches as mentioned earlier.

aaaaaAlazyZgreeedyAlaaazyZaaaaa
     \__________________/
     A.* matched, Z can now match

While Lazy repetition in A.*?Z, first matches as few . as possible, and then taking more . as necessary. This explains why it finds two matches in the input. Below is the visual representation of the same

aaaaaAlazyZgreeedyAlaaazyZaaaaa
     \____/       \______/

Reference

Quantifiers