From: Warren Brown <wkb@...>
Date: 2003-04-25T02:06:21+09:00
Subject: Re: grep and regular expressions in ruby

Ara,

> may have a hole, but it think it can be done:

    Yup, this has a hole in cat_and_notsmall:

cat_and_notsmall((?:(?:cat.*^[^s]*$|^[^s]*(?:s(?!mall)[^s]*)+$)|(?:^[^s]*$|^
[^s]*(?:s(?!mall)[^s]*)+$.*cat))+)
========
 cat              matched? true
 small            matched? false
 smallcat         matched? false
 catsmall         matched? false
 smalcat          matched? true
 smalcat small    matched? false
 catsmal          matched? true
 catsmal small    matched? false
 smal             matched? true  <----
 smalsmall        matched? false
 smal small       matched? false
 smallsmal        matched? false
 smalcatsmall     matched? false
 smalcat small    matched? false
 smallcatsmal     matched? false

    If you take a close look at the regular expression, you will see it
breaks down into:

[01]  (?:
[02]    (?:
[03]      cat.*^[^s]*$
[04]      |
[05]      ^[^s]*(?:s(?!mall)[^s]*)+$
[06]    )
[07]    |
[08]    (?:
[09]      ^[^s]*$
[10]      |
[11]      ^[^s]*(?:s(?!mall)[^s]*)+$.*cat
[12]    )
[13]  )+

    Lines [03] and [11] can never match anything (because of the 'cat.*^'
and '$.*cat').  The only reason this regular expression matches anything is
due to [05] and [09].  Since [05] is a more restrictive superset of [09],
this regular expression basically reduces to [05] (i.e. notsmall).

    However, this is not just a case of bad parenthesis, the problem is with
the whole '(something).*(not_something_else)' approach.  This will never
work because the '.*' portion is always able to consume a something_else
before the '(not_something_else)' portion ever sees it.

    The only way I know of to do this is with a
'^(not_something_else)*something(not_something_else)*$' approach.

    I hope this didn't end up sounding like a critique.  It's just that I
couldn't see how this was working until I pulled it apart, and when I did I
found what I thought was interesting stuff.

    - Warren Brown