From: Rudolf Polzer <denshimeiru-sapmctacher@...>
Date: 2003-07-23T04:37:46+09:00
Subject: Re: RegExp outermost ()

Scripsit ille �Chris Morris� <chrismo@clabs.org>:
> This may be a case where RegExp ain't the way to go, but I want to scan 
> a string with nested paren groups and extract each outermost group. Is 
> this best done in an RegExp?

Impossible. REs can't do that, ask computer science people.

BTW, where is that proof available?

Hm... aren't REs equivalent to finite automata? If yes, the proof looks
easy... count how many different states you need, n, and then look what
happens if I feed it with (n+1) opening parens and then (n+1) closing
braces. Especially look how many different states you need then.

But wait... Ruby REs can check "w consists exactly of a composite number
of ones": /^(11+)\1+$/. Can finite automata do that?

perlre says it is at least possible using recursive REs:

   The following pattern matches a parenthesized group:

     $re = qr{
                \(
                (?:
                   (?> [^()]+ )    # Non-parens without backtracking
                 |
                   (??{ $re })     # Group with matching parens
                )*
                \)
             }x;

No idea if Ruby has a similar feature. BTW, where is (?:something)
documented? It just works like in Perl, but where does it stand?


-- 
Nochn Hinweis: Ein Fragezeichen pro Satz reicht, mehr wirkt leicht
albern. Und davor bitte kein Leerzeichen machen. Hab ich "Warum" geh�rt
? Hier hast du die Antwort.
                               [Volker Gringmuth in de.newusers.questions]