From: ahoward <ahoward@...>
Date: 2003-04-24T14:46:22+09:00
Subject: Re: grep and regular expressions in ruby

On Thu, 24 Apr 2003, Daniel Carrera wrote:

<snip>
>  /cat|small/  -> true if matches /cat/ or matches /small/
>  /cat&small/  -> true if matches /cat/ and matches /small/
>  /cat|!small/ -> true if matches /cat/ or does not match /small/
>  /cat&!small/ -> true if matches /cat/ and does not match /small/
</snip>

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

----CUT----
  #!/usr/bin/env ruby

  small    = 'small'
  notsmall = '^[^s]*$|^[^s]*(?:s(?!mall)[^s]*)+$'
  cat      = 'cat'

  patterns = {
    :cat_or_small     =>
      %r/(?:#{cat})|(?:#{small})/,
    :cat_and_small    =>
      %r/(?:(?:#{cat}.*#{small})|(?:#{small}.*#{cat}))+/,
    :cat_or_notsmall  =>
      %r/(?:#{cat})|(?:#{notsmall})/,
    :cat_and_notsmall =>
      %r/(?:(?:#{cat}.*#{notsmall})|(?:#{notsmall}.*#{cat}))+/,
  }

  words = [
      'cat',
      'small',
      'smallcat',
      'catsmall',
      'smalcat',
      'smalcat small',
      'catsmal',
      'catsmal small',
      'smal',
      'smalsmall',
      'smal small',
      'smallsmal',
      'smalcatsmall',
      'smalcat small',
      'smallcatsmal',
  ]

  patterns.each do |name, pattern|
    puts "#{name}(#{pattern.source})\n========"
    words.each do |word|
      matched = word =~ pattern ? 'true' : 'false'
      printf "\s%-16.16s matched? %-8.8s\n", word, matched
    end
  end

  def notword word
    a, rest = word[0..0], word[1..-1]
    %r/^[^#{a}]*$|^[^#{a}]*(?:#{a}(?!#{rest})[^#{a}]*)+$/
  end
----CUT----

the finite state machine for 'not small' is easy to draw.  it really helped
make the RE.


<pre>

   .------------------------------------
  / \          |       |       |       |
 /   ^s      ^[ms]   ^[as]   ^[ls]   ^[ls]
/     \        |       |       |       |
[start ]---s---*---m---*---a---*---l---*---l---[fail]
              /|       |       |       |
             s |       s       s       s
            /  |       |       |       |
            ---|-----------------------|

start -> accept
*     -> accept

</pre>


-a

--
  ====================================
  | Ara Howard
  | NOAA Forecast Systems Laboratory
  | Information and Technology Services
  | Data Systems Group
  | R/FST 325 Broadway
  | Boulder, CO 80305-3328
  | Email: ara.t.howard@fsl.noaa.gov
  | Phone:  303-497-7238
  | Fax:    303-497-7259
  ====================================