gotoken / math.sci.hokudai.ac.jp (GOTO Kentaro) wrote:
>
>In message "[ruby-talk:9035] Re: Regexp for matching Ruby reg exps?"
>     on 01/01/10, "Ben Tilly" <ben_tilly / hotmail.com> writes:
> >A Ruby regexp can contain any set of balanced parens.
> >Balanced parens are a classic problem that is unsolvable
> >in a regular expression.
>
># Note: this message isn't practical but may be a pazzle :-)
>
>Ruby's regexp is extended rather than the theoretical one.  So, this
>problem is solvable in Ruby perhaps.  Indeed, a Perl's regexp for a
>kind of balanced parens, i.e. email address, is known (e.g. appears in
>Jeffrey E. F. Friedl's book).

Not so.

Friedl's solution only handles nesting to a limited depth.
Enough for parsing email addresses but not a general
solution.  Not only is handling arbitrary nesting in a
single regular expression of a standard regular expression
engine impossible, but to the best of my knowlege Perl's
regular expression engine does not yet have enough
extensions to solve this problem in general by itself.  In
fact try this:

    perldoc -q nesting

Yup.  Perl's documentation agrees with me.  Can't be done
in Perl with a straight regular expression.

>On the other hand, writing negative pattern in Ruby's regexp is very
>difficult sometimes.  So, I think there slightly is a gap between the
>classic problem and that sort of explanation.

Writing negative patterns in any regular expression engine
tends to be difficult.  I claim that this is a limitation
inherent in the RE view of the world, and not to any
specific implementation.

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