From: Ben Tilly Date: 2001-01-11T13:32:55+09:00 Subject: [ruby-talk:9102] Re: Regexp for matching Ruby reg exps? Dave Thomas wrote: > >"Ben Tilly" writes: > > > Dave Thomas wrote: > > > > > >"Ben Tilly" 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