Matching double char delimited strings with regular expressions

Question

Suppose you want to match text that is delimited by double characters like so:

a = <<
Hello
World!
>>

The regular expression /<<(.*)>>/ would seem to do it, but unfortunately when these can be repeated greedy matching gets too much:

a = <<
Hello
World!
>>

b = <<
Goodbye
World!
>>

The previous regexp will capture

Hello
World!
>>

b = <<
Goodbye
World!

The obvious answer is to make the regexp non-greedy: /<<(.*?)>>/

Unfortunately this has extreme performance problems for long strings (in Perl at least). If the delimiters were single characters, then we could use a character class (everything but the character) to solve the greedy problem.

Any ideas on a regular expression to make this match without the performance penalty?

NB: I have to use Perl and this has to be a regular expression because of the larger system it's embedded in.

Thanks.

Answer 1

Please see if the performance of a dedicated parser (such as Text::Balanced) would be acceptable in this case. It's not regex, but without more details on your "NB" poststcriptum it sounds like you might have an XY problem when looking for a regex-only solution.

If you absolutely must use a regex, please look at using a look-ahead functionality - it may improve the speed.

Answer 2

Using a negated character class in this case will work:

/<<([^>]*)>>/ is the same probe count as /<<(.*)>>/ so should be just as fast with less backtracking as /<<(.*?)>>/

I do agree with DVK however; is a regex the only way?

Answer 3

Expanding drewk's answer so it actually works:

/<<((?:(?>[^>]+)|>(?!>))*)>>/

Match "<<", then a sequence of 0 or more chunks which are either any number of non-">" characters, or a single ">" not followed by another ">", then finally ">>".

Answer 4

Say you have a simple grammar

my $p = Parse::RecDescent->new(<<'EOGrammar');
  program: assignment(s)

  assignment: id '=' '<<' angle_text '>>'
              { $return = [ $item{id}, $item{angle_text} ] }

  angle_text: <skip:undef> / ( [^>] | >(?!>) )* /x

  id: /\w+/
EOGrammar

and a source text of

a = <<
Hello

World!

>>

b = <<


Goodbye
World!
>>

When you process the result with

for (@{ $p->program($text) }) {
  my($name,$what) = @$_;
  print "$name: [[[$what]]]\n";
}

you'll see output of

a: [[[
Hello

World!

]]]
b: [[[


Goodbye
World!
]]]

Answer 5

Are you using Perl 5.10? Try this:

/<<([^>]*+(?:>(?!>)[^>]*+)*+)>>/

Like the regex @hobbs posted, this one performs lookahead only after it finds a > (as opposed to the non-greedy quantifier, which effectively does a lookahead at every position). But this one uses Friedl's "unrolled loop" technique, which should be slightly faster than the alternation approach. Also, all quantifiers are possessive, so it doesn't bother saving the state information that would make backtracking possible.