title: Greedy vs. Reluctant vs. Possessive Qualifiers
body: <p>I found this <a href="https://docs.oracle.com/javase/tutorial/essential/regex/quant.html" rel="noreferrer">tutorial</a> on regular expressions and while I intuitively understand what &quot;greedy&quot;, &quot;reluctant&quot; and &quot;possessive&quot; qualifiers do, there seems to be a serious hole in my understanding.</p>
  <p>Specifically, in the following example:</p>
  <pre class="lang-none prettyprint-override"><code>Enter your regex: .*foo // Greedy qualifier
  Enter input string to search: xfooxxxxxxfoo
  I found the text &quot;xfooxxxxxxfoo&quot; starting at index 0 and ending at index 13.
  
  Enter your regex: .*?foo // Reluctant qualifier
  Enter input string to search: xfooxxxxxxfoo
  I found the text &quot;xfoo&quot; starting at index 0 and ending at index 4.
  I found the text &quot;xxxxxxfoo&quot; starting at index 4 and ending at index 13.
  
  Enter your regex: .*+foo // Possessive qualifier
  Enter input string to search: xfooxxxxxxfoo
  No match found.
  </code></pre>
  <p>The explanation mentions <strong>eating</strong> the entire input string, letters been <strong>consumed</strong>, matcher <strong>backing off</strong>, rightmost occurrence of &quot;foo&quot; has been <strong>regurgitated</strong>, etc.</p>
  <p>Unfortunately, despite the nice metaphors, I still don't understand what is eaten by whom... Do you know of another tutorial that explains (concisely) <em>how</em> regular expression engines work?</p>
  <p>Alternatively, if someone can explain in somewhat different phrasing the following paragraph, that would be much appreciated:</p>
  <blockquote>
  <p>The first example uses the greedy quantifier <code>.*</code> to find &quot;anything&quot;, zero or more times, followed by the letters <code>&quot;f&quot;</code>, <code>&quot;o&quot;</code>, <code>&quot;o&quot;</code>. Because the quantifier is greedy, the <code>.*</code> portion of the expression first eats the entire input string. At this point, the overall expression cannot succeed, because the last three letters (<code>&quot;f&quot;</code>, <code>&quot;o&quot;</code>, <code>&quot;o&quot;</code>) have already been consumed [by whom?]. So the matcher slowly backs off [from right-to-left?] one letter at a time until the rightmost occurrence of <code>&quot;foo&quot;</code> has been regurgitated [what does this mean?], at which point the match succeeds and the search ends.</p>
  <p>The second example, however, is reluctant, so it starts by first consuming [by whom?] &quot;nothing&quot;. Because <code>&quot;foo&quot;</code> doesn't appear at the beginning of the string, it's forced to swallow [who swallows?] the first letter (an <code>&quot;x&quot;</code>), which triggers the first match at 0 and 4. Our test harness continues the process until the input string is exhausted. It finds another match at 4 and 13.</p>
  <p>The third example fails to find a match because the quantifier is possessive. In this case, the entire input string is consumed by <code>.*+</code> [how?], leaving nothing left over to satisfy the &quot;foo&quot; at the end of the expression. Use a possessive quantifier for situations where you want to seize all of something without ever backing off [what does back off mean?]; it will outperform the equivalent greedy quantifier in cases where the match is not immediately found.</p>
  </blockquote>