[ruby-talk:9102] Re: Regexp for matching Ruby reg exps?

Dave Thomas <[e-mail]> wrote:
>
>"Ben Tilly" <[e-mail]> writes:
>
> > Dave Thomas <[e-mail]> wrote:
> > >
> > >"Ben Tilly" <[e-mail]> writes:
> > >
> > > > Yup.  Perl's documentation agrees with me.  Can't be done
> > > > in Perl with a straight regular expression.
> > >
> > >Not with one, perhaps, but it can with two, or three if you allow
> > >escaping of a delimiter (at least in all the cases I've come across).
> >
> > Depends on what you mean with 2.
> >
> > Abigail has a nice substitution trick, which strips out all
> > of the balanced text, and then if you have any parens left
> > it was unbalanced.
>
>Latex2html does it by expanding nested braces, starting with the
>innermost, tagging each pair with a unique number. I used the same
>technique in a home-grown script that converts Pragmatic Programmer
>chapters from LaTeX to XML. By moving the loop out of the regexp and
>making explicit, performance is perfectly fine
>
>   1 while ($text =~ s/\{([^\{\}]*)\}/ $count++; 
>"!!O:$count:$1!!C:$count:"/ges);
>
Performance may be fine for your application, but that is
basically the trick I saw Abigail use.  It is O(n*m) where
n is the length of the string, and m the number of nested
structures.  In a deeply nested string m is O(n), so in
general that scales like O(n*n).

Why?

Because each substitution has to start scanning the string
from the beginning to the end looking for a matching pair
to expand.

Also there is a bug.  You assume that the string !!O:50:
does not already appear in the text.  If it does you are
likely to be confused.  Using a real data structure you
will not have that problem.  Of course it won't happen by
accident, and for your own text that is something you can
know to avoid.  (Whatever gets the job done.)   But I
would be dubious of that kind of code if security was an
issue.

Cheers,
Ben
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com