From: Robert Klemme <shortcutter@...>
Date: 2008-02-08T17:07:58+09:00
Subject: Re: regex dynamic count modifier {min, max} ?

2008/2/8, jOhn <netcam@gmail.com>:
> Here is an idea and tell me if it could be accomplished by some other means.
>
>
> To parse a logic statement like this:
>
> fn:function3(fn:function2(fn:function1(xargs)))
>
> Using a regex sorta like so to grep the function-start-pattern(s) :
>
> /\A((fn\:[\w\-]+)[ ]*\([ ]*)+\z/i
>
> It would be nice to ensure the proper count of ')', without confusion if say
> the xargs had ')' literal or escaped string value(s) in there.
>
> One way is to provide a count ref for function-start-pattern, so I could
> then group a pattern for match on post-xargs ')' and force the {min,max}
> count by some backref to count-of-(function-start-pattern) =X and put that
> in there for the (function-end-pattern)+{X,X}.
>
> Then it might be something like this (ignore the lack of a match on possible
> xargs for now) :
>
> /\A((fn\:[\w\-]+)[ ]*\([ ]*)+[ ]*(\)){$#1,$#1}\z/i
>
> Where $#1 would be the count ref of the first group etc. Then there would be
> matching count-left-side-( and count-right-side-).
>
> Or I don't understand enuf about the internals of regex to know that this is
> impossible.

Parsing nested structures is not possible with standard regular
expressions. IIRC they added something to Perl regexps to do that and
it may be possible with Ruby 1.9; but I do not know the 1.9 regexp
engine good enough to answer that off the top of my head.

So the usual approach is to use a context free grammar and parser.
You can find parser generators in the RAA.

If you just want to ensure counts match you could do something like this:

raise "brackets do not match!" if
  str.scan(/\(/).size != str.scan(/\)/).size

However, this does not ensure proper nesting.  I bit more sophisticated:

c = 0
str.scan /[()]/ do |m|
  case m
    when "("
      c += 1
    when ")"
      c -= 1
      raise "Mismatch at '#$`'" if c < 0
    else
      raise "Programming error"
  end
end
raise "Mismatch" unless c == 0

But now you get pretty close to a decent parser. :-)

Kind regards

robert

-- 
use.inject do |as, often| as.you_can - without end