Lookahead assertions seem to short-circuit ordering of alternates in regular expressions

Question

I'm working with a (Python-flavored) regular expression to recognize common and idiosyncratic forms and abbreviations of scripture references. Given the following verbose snippet:

>>> cp = re.compile(ur"""
    (?:(
        # Numbered books
        (?:(?:Third|Thir|Thi|III|3rd|Th|3)\ ? 
           (?:John|Joh|Jhn|Jo|Jn|Jn|J))
        # Other books
        |Thessalonians|John|Th|Jn)\ ? 
      # Lookahead for numbers or punctuation
      (?=[\d:., ]))

    |

    # Do the same check, this time at the end of the string.
    (
      (?:(?:Third|Thir|Thi|III|3rd|Th|3)\ ?
         (?:John|Joh|Jhn|Jo|Jn|Jn|J))
      |Thessalonians|John|Th|Jn)\.?$
    """, re.IGNORECASE | re.VERBOSE)

>>> cp.match("Third John").group()
'Third John'

>>> cp.match("Th Jn").group()
'Th'

>>> cp.match("Th Jn ").group()
'Th Jn'

The intention of this snippet is to match various forms of "Third John", as well as forms of "Thessalonians" and "John" by themselves. In most cases this works fine, but it does not match "Th Jn" (or "Th John"), rather matching "Th" by itself.

I've ordered the appearance of each abbreviation in the expression from longest to shortest expressly to avoid a situation like this, relying on a regular expression's typically greedy behavior. But the positive lookahead assertion seems to be short-circuiting this order, picking the shortest match instead of the greediest match.

Of course, removing the lookahead assertion makes this case work, but breaks a bunch of other tests. How might I go about fixing this?

Answer 1

I've given up after a little try to follow what _sre.so is doing in this case (too complicated!) but a "blind fix" I tried seemed to work -- switch to a negative lookahead assertion for the complementary character set...:

cp = re.compile(ur"""
(?:(
    # Numbered books
    (?:(?:Third|Thir|Thi|III|3rd|Th|3)\ ? 
       (?:John|Joh|Jhn|Jo|Jn|Jn|J))
    # Other books
    |Thessalonians|John|Th|Jn)\ ? 
  # Lookahead for numbers or punctuation
  (?![^\d:., ]))

|

etc. I.e. I changed the original (?=[\d:., ])) positive lookahead into a "double negation" form (negative lookahead for complement) (?![^\d:., ])) and this seems to remove the perturbation. Does this work correctly for you?

I think it's an implementation anomaly in this corner case of _sre.so -- it might be interesting to see what other RE engines do in these two cases, just as a sanity check.

Answer 2

The lookahead isn't really short circuiting anything. The regex is only greedy up to a point. It'll prefer a match in your first big block because it doesn't want to cross that "|" boundary to the second part of the regex and have to check that as well.

Since the whole string doesn't match the first big block (because the lookeahead says it needs to be followed by a particular character rather than end of line) it just matches the "Th" from the "Thessalonians" group and the lookahead sees a space following "Th" in "Th Jn" so it considers this a valid match.

What you'll probably want to do is move the "|Thessalonians|John|Th|Jn)\ ? " group out to another large "|" block. Check your two word books at the beginning of text OR at the end of text OR check for one word books in a third group.

Hope this explanation made sense.

Answer 3

Another alternate solution I discovered while asking the question: switch the order of the blocks, putting the end-of-line check first, then the lookahead assertion last. However, I prefer Alex's double negative solution, and have implemented that.