title: Negative Lookahead Regex greed (why is .*? too greedy)
body: <p>I'm having trouble understanding the finer details of negative lookahead regular expressions.  After reading <a href="https://stackoverflow.com/questions/2973436/regex-lookahead-lookbehind-and-atomic-groups">Regex lookahead, lookbehind and atomic groups</a>, I thought I had a good summary of negative lookaheads when I found this description:</p>
  <blockquote>
  <p><code>(?!REGEX_1)REGEX_2</code></p>
  <p>Match only if <code>REGEX_1</code> does not match; after checking <code>REGEX_1</code>, the search for <code>REGEX_2</code> starts at the same position.</p>
  </blockquote>
  <p>Hoping I understood the algorithm, I cooked up a two-sentence test insult; I wanted to find the sentence without a certain word.  Specifically...</p>
  <blockquote>
  <p><strong>Insult:</strong> 'Yomama is ugly.  And, she smells like a wet dog.'</p>
  <p><strong>Requirements</strong>:</p>
  <ul>
  <li>Test 1:  Return a sentence without 'ugly'.</li>
  <li>Test 2:  Return a sentence without 'looks'.</li>
  <li>Test 3:  Return a sentence without 'smells'.</li>
  </ul>
  </blockquote>
  <p>I assigned the test words to <code>$arg</code>, and I used <code>(?:(?![A-Z].*?$arg.*?\.))([A-Z].*?\.)</code> to implement the test.</p>
  <ul>
  <li><code>(?![A-Z].*?$arg.*?\.)</code> is a negative lookahead to reject a sentence with the test word</li>
  <li><code>([A-Z].*?\.)</code> matches <em>at least</em> one sentence.</li>
  </ul>
  <p>The critical piece seems to be in understanding where the regex engine starts matching after processing the negative lookahead.</p>
  <p><strong>Expected Results</strong>:</p>
  <blockquote>
  <ul>
  <li>Test 1 ($arg = &quot;ugly&quot;): &quot;And, she smells like a wet dog.&quot;</li>
  <li>Test 2 ($arg = &quot;looks&quot;): &quot;Yomama is ugly.&quot;</li>
  <li>Test 3 ($arg = &quot;smells&quot;): &quot;Yomama is ugly.&quot;</li>
  </ul>
  </blockquote>
  <p><strong>Actual Results</strong>:</p>
  <blockquote>
  <ul>
  <li>Test 1 ($arg = &quot;ugly&quot;): &quot;And, she smells like a wet dog.&quot; (Success)</li>
  <li>Test 2 ($arg = &quot;looks&quot;): &quot;Yomama is ugly.&quot; (Success)</li>
  <li>Test 3 ($arg = &quot;smells&quot;): <em>Failed, no match</em></li>
  </ul>
  </blockquote>
  <p>At first I thought Test 3 failed because <code>([A-Z].*?\.)</code> was too greedy and matched both sentences; however, <code>(?:(?![A-Z].*?$arg.*?\.))([A-Z][^\.]*?\.)</code> didn't work either.  Next I wondered whether there was a problem with the python negative lookahead implementation, but perl gave me exactly the same result.</p>
  <p>Finally I found the solution, I had to reject periods in my <code>.*?</code> portion of the expressions by using <code>[^\.]*?</code>; so this regex works: <code>(?:(?![A-Z][^\.]*?$arg[^\.]*?\.))([A-Z][^\.]*?\.)</code></p>
  <h2>Question</h2>
  <p>However, I have another concern; &quot;Yomama is ugly.&quot; does not have &quot;smells&quot; in it.  So, if <code>.*?</code> is supposed to be a non-greedy match, why can't I complete Test 3 with <code>(?:(?![A-Z].*?$arg.*?\.))([A-Z].*?\.)</code>?</p>
  <h2>EDIT</h2>
  <p>In light of @bvr's excellent suggestion to use <code>-Mre=debug</code>, I will consider this some more after work.  It certainly looks like Seth's description is accurate at this point.  What I learned so far is that negative lookahead expressions will match whenever possible, even if I put non-greedy <code>.*?</code> operators in the NLA.</p>
  <hr>
  <h2>Python Implementation</h2>
  <pre><code>import re
  
  def test_re(arg, INSULTSTR):
      mm = re.search(r'''
          (?:                  # No grouping
          (?![A-Z].*?%s.*?\.)) # Negative zero-width
                               #     assertion: arg, followed by a period
          ([A-Z].*?\.)         # Match a capital letter followed by a period
          ''' % arg, INSULTSTR, re.VERBOSE)
      if mm is not None:
          print &quot;neg-lookahead(%s) MATCHED: '%s'&quot; % (arg, mm.group(1))
      else:
          print &quot;Unable to match: neg-lookahead(%s) in '%s'&quot; % (arg, INSULTSTR)
  
  
  INSULT = 'Yomama is ugly.  And, she smells like a wet dog.'
  test_re('ugly', INSULT)
  test_re('looks', INSULT)
  test_re('smells', INSULT)
  </code></pre>
  <h2>Perl Implementation</h2>
  <pre><code>#!/usr/bin/perl
  
  sub test_re {
      $arg    = $_[0];
      $INSULTSTR = $_[1];
      $INSULTSTR =~ /(?:(?![A-Z].*?$arg.*?\.))([A-Z].*?\.)/;
      if ($1) {
          print &quot;neg-lookahead($arg) MATCHED: '$1'\n&quot;;
      } else {
          print &quot;Unable to match: neg-lookahead($arg) in '$INSULTSTR'\n&quot;;
      }
  }
  
  $INSULT = 'Yomama is ugly.  And, she smells like a wet dog.';
  test_re('ugly', $INSULT);
  test_re('looks', $INSULT);
  test_re('smells', $INSULT);
  </code></pre>
  <h2>Output</h2>
  <pre><code>neg-lookahead(ugly) MATCHED: 'And, she smells like a wet dog.'
  neg-lookahead(looks) MATCHED: 'Yomama is ugly.'
  Unable to match: neg-lookahead(smells) in 'Yomama is ugly.  And, she smells like a wet dog.'
  </code></pre>