Regex with recursive expression to match nested braces?

Question

I'm trying to match text like sp { ...{...}... }, where the curly braces are allowed to nest. This is what I have so far:

my $regex = qr/
(                   #save $1
    sp\s+           #start Soar production
    (               #save $2
        \{          #opening brace
        [^{}]*      #anything but braces
        \}          #closing brace  
        | (?1)      #or nested braces
    )+              #0 or more
)
/x;

I just cannot get it to match the following text: sp { { word } }. Can anyone see what is wrong with my regex?

ikegami · Accepted Answer · 2012-10-04 04:36:57Z

6

There are numerous problems. The recursive bit should be:

(
   (?: \{ (?-1) \}
   |   [^{}]+
   )*
)

All together:

my $regex = qr/
   sp\s+
   \{
      (
         (?: \{ (?-1) \}
         |   [^{}]++
         )*
      )
   \}
/x;

print "$1\n" if 'sp { { word } }' =~ /($regex)/;

edited Oct 4, 2012 at 4:36

answered Oct 4, 2012 at 3:49

ikegami

391k17 gold badges291 silver badges555 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

tripleee Over a year ago

As near as I can tell, the regex doesn't allow spaces around the braces (sorry for the rhyme) so the test case should fail. What's up with that?

Nate Glenn Over a year ago

Hmmm... This ends up taking forever for some partial matches, like this: sp {word{(aaaaaaaaaaaaaaaaaaaaaaaaaaaaa)}.

Joel Berger Over a year ago

@NateGlenn see my solution, also what do you want to happen on that partial match, is that a failure or would you have it return the remainder of the string?

Nate Glenn Over a year ago

@JoelBerger that one should not match. The rest of the matches should be returned.

ikegami Over a year ago

Speed issue fixed by changing [^{}]+ to [^{}]++.

|

Joel Berger · Accepted Answer · 2012-10-04 04:35:24Z

6

This is case for the underused Text::Balanced, a very handy core module for this kind of thing. It does rely on the pos of the start of the delimited sequence being found/set first, so I typically invoke it like this:

#!/usr/bin/env perl

use strict;
use warnings;

use Text::Balanced 'extract_bracketed';

sub get_bracketed {
  my $str = shift;

  # seek to beginning of bracket
  return undef unless $str =~ /(sp\s+)(?={)/gc;

  # store the prefix
  my $prefix = $1;

  # get everything from the start brace to the matching end brace
  my ($bracketed) = extract_bracketed( $str, '{}');

  # no closing brace found
  return undef unless $bracketed;

  # return the whole match
  return $prefix . $bracketed;
}

my $str = 'sp { { word } }';

print get_bracketed $str;

The regex with the gc modifier tells the string to remember where the end point of the match is, and extract_bracketed uses that information to know where to start.

edited Oct 4, 2012 at 4:35

answered Oct 4, 2012 at 4:28

Joel Berger

20.3k5 gold badges52 silver badges106 bronze badges

2 Comments

Nate Glenn Over a year ago

I really need to read up on this module. It comes up a lot, but I always prefer regex because I've already invested so much time in learning it, it's fun to learn more of, and seems more compact. Thanks for the answer!

Joel Berger Over a year ago

@NateGlenn, it really is complementary to regexp and especially the regexp gc (parser) functionality. This is why it uses the pos of the string, because it is expected that you will intermingle the calls to text_balanced with //gc

Collectives™ on Stack Overflow

Regex with recursive expression to match nested braces?

2 Answers 2

6 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related