Сопоставление строк, разделенных двойными символами, с регулярными выражениями

Question

Предположим, вы хотите сопоставить текст, разделенный двойными символами, например:

a = <<
Hello
World!
>>

Регулярное выражение /<<(.*)>>/, похоже, делает это, но, к сожалению, когда их можно повторить, жадное сопоставление становится слишком большим:

a = <<
Hello
World!
>>

b = <<
Goodbye
World!
>>

Предыдущее регулярное выражение захватит

Hello
World!
>>

b = <<
Goodbye
World!

Очевидный ответ - сделать регулярное выражение нежадным: /<<(.*?)>>/

К сожалению, это приводит к серьезным проблемам с производительностью для длинных строк (по крайней мере, в Perl). Если разделители были одиночными символами, то мы могли бы использовать класс символов (все, кроме символа), чтобы решить жадную проблему.

Есть ли какие-нибудь идеи относительно регулярного выражения, чтобы сделать это соответствие без потери производительности?

Примечание: я должен использовать Perl, и это должно быть регулярное выражение из-за большей системы, в которую он встроен.

Спасибо.

Answer 1

Расширяем ответ Дрюка, чтобы он действительно работал:

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

Совпадение «<<», затем последовательность из 0 или более фрагментов, которые представляют собой любое количество символов, отличных от «>», или один «>», за которым не следует другой «>», затем, наконец, «>>» .

Answer 2

Вы используете Perl 5.10?Попробуйте это:

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

Как и опубликованное регулярное выражение @hobbs, этот выполняет предварительный просмотр только после того, как найдет > (в отличие от некожадного квантификатора, который эффективно выполняет предварительный просмотр в каждой позиции),Но этот использует технику «развернутого цикла» Фридла, которая должна быть немного быстрее, чем альтернативный подход.Кроме того, все квантификаторы являются притяжательными, поэтому не стоит сохранять информацию о состоянии, которая сделала бы возможным возврат.

Answer 3

Использование отрицательного класса символов в этом случае будет работать:

/<<([^>]*)>>/ - это то же число проб, что и /<<(.*)>>/, поэтому оно должно быть таким же быстрым с меньшим возвратом, как /<<(.*?)>>/

Однако я согласен с ДВК;регулярное выражение единственный путь?

Answer 4

Скажем, у вас простая грамматика

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

и исходный текст

a = <<
Hello

World!

>>

b = <<


Goodbye
World!
>>

Когда вы обрабатываете результат с

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

вы увидите вывод

a: [[[
Hello

World!

]]]
b: [[[


Goodbye
World!
]]]

Answer 5

Пожалуйста, посмотрите, будет ли производительность выделенного парсера (например, Text :: Balanced ) приемлемой в этом случае. Это не регулярное выражение, но без дополнительной информации о вашем постскриптуме "NB" может показаться, что у вас может возникнуть проблема XY при поиске решения только для регулярных выражений.

Если вам абсолютно необходимо использовать регулярное выражение, обратите внимание на использование функции упреждающего просмотра - это может улучшить скорость.