From: Brian Candler <b.candler@...>
Date: 2008-11-27T04:50:57+09:00
Subject: Re: regexp problem

Chai Muang thong wrote:
> Hi,
> 
> I have been searching on the Internet about how to solve my problem. I
> have a string that needs to be split using regexp in ruby. The problem
> is that I cannot find a way to get it right. The string has a fix
> format. The rules for matching are as followed:
>  1)A string starts and end with any character string
>  2)Matching string starts from "<<" and end with ">>"
>  3)Matching string must be a pair of "<<" and ">>" and must be nested
> correctly

A Regular Expression (by the computer science definition of Regular 
Expression) cannot match nested pairs. You'd need a parser for a 
context-free grammar.

Having said that: many "regexp" implementations have a features crammed 
into them which do that. But the penalty you pay is in complexity, and 
often artefacts such as exponential time taken in backtracking.

So: if you want to do it right look at a parser generator such as antlr, 
racc, coco, rockit, treetop etc.

However, I admit those may be very large hammers to crack a small nut.

What regexps *are* very good at is tokenising:

str = "<<p1 <<p2>> <<p3 <<p4>>>>>> <and> <<p5>> or <<p6 <<p7 <<p8>>>>>>"
tokens = str.scan(/<<|>>|(?:[^<>]|<(?!<)|>(?!>))+/)

# => ["<<", "p1 ", "<<", "p2", ">>", " ", "<<", "p3 ", "<<", "p4", ">>", 
">>", ">>", " <and> ", "<<", "p5", ">>", " or ", "<<", "p6 ", "<<", "p7 
", "<<", "p8", ">>", ">>", ">>"]

The constructs I've used are:

  (?: ... )       grouping without capture
  (?! ... )       zero-width negative lookahead (match if string
                  is not followed by ... without consuming it)

From this you can count << to find matching >>, or implement a recursive 
parser.

A naive counting solution:

depth = 0
out = []
while t = tokens.shift
  case t
  when "<<"
    res = "" if depth == 0
    res << t
    depth += 1
  when ">>"
    if depth > 0
      res << t
      depth -= 1
      out << res if depth == 0
    end
  else
    res << t if depth > 0
  end
end

-- 
Posted via http://www.ruby-forum.com/.