You asked too many questions and your node is too long so I will respond to only one question.

Con(tains i(mbalan(ced Br(ack)ets, )one c)lose missing
     Match succeeded
     (ack)
     (ced Br(ack)ets, )
     (mbalan(ced Br(ack)ets, )one c)
     (ack)
     (ced Br(ack)ets, )
     (mbalan(ced Br(ack)ets, )one c)
[download]

The engine started matching the initial (, successfully matched those three complete (...) strings, then found that it couldn't find a ) to complete the ( that was already in progress. It skipped to the next ( and tried again. Then it fully succeeded.

If you wanted it to fail because there were unbalanced parens, you'd need to have asserted that there were to be no parens leading or following the balanced part. I thinkg that's what you said you were doing later down your node but like I said, it was too long and I didn't read the rest of it.

Oh yeah, when you "put it all in one," you used ^ which asserted that you were at the beginning of the string. You can't write a regex that says $recurse = qr/^...(??{ $recurse })/ because when you recurse you aren't at the beginning of the string nymore.

Thank you for actually answering both questions. It's obvious now that you state it that anchoring and recursion don't go together like that. And I am kicking myself.

Cheers,

JohnGG

...

our $rxNest;
$rxNest = qr{(?x)
   (
      \(
      [^()]*
      (?:
         (??{$rxNest})
         [^()]*
      )*
      \)
   )
   (?{ [ @{$^R}, $1 ] })
};

our $rxOnlyNested = qr{(?x)
   (?{ [] })
   ^
   [^()]*
   (?:
      $rxNest
      [^()]*
   )*
   \z
   (?{ @memoList = @{$^R} })
};

...

    if ($string =~ $rxOnlyNested)

...
[download]

Note that @memoList is now correct whether there is backtracking or not, thanks to the use of $^R.

Note that I used $1 instead of $+. Using $+ will negatively impact on the performance of all regexps without captures executed in that perl interpreter instance, whereever they are located.

Update: Removed unnecessary parens. (Copy and paste bug.)

Thank you for providing a solution, which I think I understand. Please correct me if I am wrong.

The (?{ [] }) at the start of $rxOnlyNested creates an empty list reference and the reference will be held in $^R (the result of the last code block). In $rxNest the (?{ [ @{$^R}, $1 ] }) at the end creates a new list reference which contains the dereferenced contents of the last list plus the memory group of the successful match. This list keeps growing as the regular expression recursed, in effect. Finally, in $rxOnlyNested the list is dereferenced and assigned to @memoList.

I hope I have understood correctly and if it is doing what I think it is doing, it is a very neat solution. I am glad I have finally started visiting the Monastery as I am learning a lot of new techniques.

Cheers,

JohnGG

That's exactly it.

Now, you might wonder why I didn't add to @memoList directly. It might be best to use an example:

local $_ = 'abbbbbc';

{
   local @memoList;

   /
      a
      (?:
         (b)
         (?{ push @memoList, $1 })
       )*
      bbc
   /x;

   print(@memoList, "\n");  # bbbbb
                            # Wrong! There should only be three!
}


{
   local @memoList;

   /
      (?{ [] })
      a
      (?:
         (b)
         (?{ [ @{$^R}, $1 ] })
      )*
      bbc
      (?{ @memoList = @{$^R} })
   /x;

   print(@memoList, "\n");  # bbb
}


{
   local @temp;
   local @memoList;

   /
      # (?{ @temp = (); })  # Redundant with 'local @temp'.
      a
      (?:
         (b)
         (?{ local @temp = (@temp, $1); })
      )*
      bbc
      (?{ @memoList = @temp })
   /x;

   print(@memoList, "\n");  # bbb
}
[download]

When the regexp engine finds that it read too many 'b's — rememeber that * is greedy — it backtracks, "unreading" the last 'b' and eventually then a second last 'b'. $^R and @temp (since we keep using local to assign to @temp) are unwound when backtracking occurs, so the last assignment is undone with each "unreading". @memoList is not unwound, on the other hand, so it keeps holding the extra 'b's.

A quick tests shows that using $^R is *much* faster than using local.

Update: Removed unnecessary parens. (Copy and paste bug.)

Your first test (slightly reformatted) had:

  $rxNest = qr{(?x)
    \(
    (?: (?>[^()]+) | (??{$rxNest}) )*
    \)
  };
  $string =~ /$rxNest/;
[download]

Note that you can put regexp flags at the end of a qr() expression just as with a normal regexp, so this is the same:

  $rxNest = qr{
    \(
    (?: (?>[^()]+) | (??{$rxNest}) )*
    \)
  }x;
[download]

The regexp that is being recursively repeated is "find an open/close paren pair with valid nesting of any parens between". Since the match was unanchored, this will locate the first starting point that works; "contains (im(balanced) parens" would therefore match "(balanced)", for example.

The (??{$rxNest}) is called a "deferred eval". When the main /$rxNest/ is compiled, this just appears as a code block in the compiled form - and the compiled form, among other things, needs to know how many capturing parens there are in the pattern. When the deferred eval is invoked the resulting regular expression is independent of the original one from which it was called. That means in particular that the deferred expression has its own capture groups numbering from $1, and these are not available to the parent expression when it returns.

Your attempt to capture the nested strings with a code block was along the right lines, but to cope with backtracking you need to take advantage of the fact that local() will do the right thing. The easy solution is to localise the list:

  (?{ local @memoList = (@memoList, $+) })
[download]

  (?{ local $offset = $offset + 1; local $memoList[$offset] = $+ })
[download]

Going on to the second problem, which was to try and make the match fail if there were imbalanced brackets, I thought the best way would be to add stuff to anchor the match to the beginning and end of the string.

When using recursion, it is vital to understand what is the repeated part of the recursion. If you have anchors in the repeated part, it probably won't do what you want - it is equivalent to a regexp like m{^ text ^ more}x.

So you need to take the anchors out of the repeated part, which is as simple as:

  $string =~ /^$rxNest\z/;
[download]

Not sure if I covered all your points here. As diotalevi says, it would be better shorter - either using shorter examples, or splitting into multiple posts would be better.

Hugo

Thank you again for very clear explanations and suggestions which I will take away and try out. With luck this will not result in another post by way of a cry for help.

I take your and diotalevi's point about the length of the post. As I was typing I kept thinking "this is getting too long." I should have split it in two. But I am also aware of the number of posts where not enough information is given and Monks are left guessing what the problem might be.

Anyway, thanks again,

JohnGG

I found your post while trying to solve one of my own problems at (??{ code }) versus (?PARNO) for recursive regular expressions. Anyway, in that process, I solved your original problem using both (??{ code }) and (?PARNO) which had not been introduced at the time of your question. I'm therefore just sharing them here in case anyone else happens by this thread.

#!/usr/bin/perl

use strict;
use warnings;

our $code_re;
$code_re = qr{
    \(
    (?: (?>[^()]+) | (??{$code_re}) )*
    \)
}x;

our $parno_re = qr{
    (
    \(
    (?: (?>[^()]+) | (?-1) )*
    \)
    )
}x;

while (<DATA>) {
    chomp;
    print /^(?:(?>[^()]+)|$code_re)*$/  ?  'PASS' :  '    ';
    print /^(?:(?>[^()]+)|$parno_re)*$/ ? ' PASS' : '     ';
    print " $_\n";
}

__DATA__
+ Cont(ains balanced( nested Br(ack)ets )in t)he text
- Con(tains i(mbalan(ced Br(ack)ets, )one c)lose missing
- Contains i(mbalan(ced Br(ack)ets, )one op)en m)missing
+ No brackets in this string
- Won)ky br(ackets in) this s(tring
- More wonky br(ackets in) th)is s(tring
- Just the one( leading bracket
- And just th)e one trailing bracket
+ So(me m(ultip)le n(est(s in) thi)s o)ne
+ Ther(e is( mo(re) de(e)p )nes(ti(n(g i)n (mul)ti)p(l)es) he)re
+ Some d((oub)le b)rackets
+ ab(())cde
+ ab()()cde
- ab(c(d)e
- ab(c)d)e
[download]

PASS PASS + Cont(ains balanced( nested Br(ack)ets )in t)he text
          - Con(tains i(mbalan(ced Br(ack)ets, )one c)lose missing
          - Contains i(mbalan(ced Br(ack)ets, )one op)en m)missing
PASS PASS + No brackets in this string
          - Won)ky br(ackets in) this s(tring
          - More wonky br(ackets in) th)is s(tring
          - Just the one( leading bracket
          - And just th)e one trailing bracket
PASS PASS + So(me m(ultip)le n(est(s in) thi)s o)ne
PASS PASS + Ther(e is( mo(re) de(e)p )nes(ti(n(g i)n (mul)ti)p(l)es) h
+e)re
PASS PASS + Some d((oub)le b)rackets
PASS PASS + ab(())cde
PASS PASS + ab()()cde
          - ab(c(d)e
          - ab(c)d)e
[download]

I also attempted to get the tracking of captured groups working like ikegami and others demonstrated. I can't think of a way to get it to work with (?PARNO). However, I did get a working solution using (??{ code }). The biggest problem I noticed with your doubling of results was that you didn't have enough (?> ) sections to avoid backtracking.

our @matches;

our $code_re;
$code_re = qr{
    (
    \(
    (?: (?>[^()]+) | (??{$code_re}) )*
    \)
    )
    (?{ push @matches, $1 })
}x;


while (<DATA>) {
    chomp;
    @matches = ();
    print /^(?:(?>[^()]+)|$code_re)*$/  ?  'PASS' : (@matches = (), ' 
+   ');
    print " $_\n";
    print "       $_\n" foreach @matches;
}
[download]

It might be an interesting challenge to get the results to print out aligned with where they're captured. But this was the limit of the goofing off I'm going to do for now :).