title: How do greedy / lazy (non-greedy) / possessive quantifiers work internally?
body: <p>I noticed that there are 3 different classes of quantifiers: greedy, lazy (i.e. non-greedy) and possessive.</p>
  <p>I know that, loosely speaking, <em>greedy</em> quantifiers try to get the longest match by first reading in the entire input string and then truncate the characters one by one if the attempts keep failing; <em>lazy</em> quantifiers try to get the shortest match by first reading in the empty string and then add in the characters one by one if the attempts keep failing; <em>possessive</em> quantifiers try the same way as greedy quantifiers while they will stop matching if the first attempt fails.</p>
  <p>However, I'm not sure how exactly the aboves are being implemented 'internally', and would like to ask for clarification (hopefully with examples).</p>
  <hr />
  <p>For example, say we have the input string as <code>&quot;fooaaafoooobbbfoo&quot;</code>.</p>
  <p>If the regex is <code>&quot;foo.*&quot;</code> (greedy), will the <code>foo</code> in the regex first match the <code>foo</code> in the input string, and then <code>.*</code> reads in <code>aaafoooobbbfoo</code> as 'the entire string'? Or will <code>.*</code> first read in <code>fooaaafoooobbbfoo</code> as 'the entire string', and then truncates <code>fooaaafoooobbbfoo</code> to try matching the <code>foo</code> in the regex? If it is the latter, will <code>fooaaafoooobbbfoo</code> be truncated from its left or from its right in each attempt?</p>
  <p>Will the answers to the above questions change if I replace <code>&quot;foo.*&quot;</code> with <code>&quot;.*foo&quot;</code> or <code>&quot;foo.*foo&quot;</code> as my regex? What about if I change those greedy quantifiers to lazy ones and possessive ones?</p>
  <p>And if there are more than one quantifiers in a regex, how will the engine deal with the priority (if that matters)?</p>
  <hr />
  <p>Thanks in advance!</p>