Меню
Что нового?

PCRE: обход вложенных скобок с учётом их парности (рекурсивные подмаски)

Offshore

Новичок
PCRE: обход вложенных скобок с учётом их парности (рекурсивные подмаски)

В документации по пхп есть момент, описывающий получение содержимого скобок верхнего уровня с учётом парных скобок внутри.

Исходя из этого материала, получение выражения описывается так (с модификатором PCRE_EXTENDED), пока просто обратите внимание на выделение:
"\( ( (?: (?>[^()]+) | (?R) )*) \)", а если не оптимизировать, то так: "\( ( (?: [^()]+ | (?R) )*) \)".

Таким образом из строки "head (blabla(bla)blabla(bbllaa)) asdasd (bla(BLA)foo) tail" при использовании preg_match_all мы получим:

Array
(
_[0] => Array
__(
___[0] => (blabla(bla)blabla(bbllaa))
___[1] => (bla(BLA)foo)
__)
_[1] => Array
__(
___[0] => blabla(bla)blabla(bbllaa)
___[1] => bla(BLA)foo
__)
)


И всё было бы превосходно, если бы не необходимость в качестве ограничителей использовать не '(' и ')', а, например, '{[' и ']}', т.е. ограничители в длину более одного символа, а их не засунешь в символьный класс просто так, как это было сделано выше -- (?>[^()]+).

То есть, проблема состоит в том, чтобы создать подмаску, которая воспринимала бы все строки, в которых не содержатся сочетания символов '{[' или ']}', т.е. чтобы строки 'abcabc', 'abc[{abc', 'ab{c[abc', 'a[}b{c[abc' и т.п. проходили проверку, а 'abc{[abc', '{[abcabc', 'abcabc{[', 'abca]}bc' итп -- нет.

Давайте думать сообща, а то мозг уже скрипит.

P.S. Подозреваю, что это как-то можно легко сделать с помощью lookbehind и/или lookahead assertions, но мыслей нет, захват в моих экспериментах происходит не так, проблемы то с жадностью, то с совпадением только в конце подмаски и т.п.
P.P.S. http://www.pcre.org/pcre.txt -- мегадокумент (кроме всего прочего, например, можно узнать много интересного про рекурсивные подшаблоны, да и вообще 95% этого документа нигде в мануалах не цитируется).
 

Rin

*
Кусок кода из моего скрипта, думаю, идея понятна. Если нет, могу "разжевать".
PHP: 
#вырезаем парные вложенные друг в друга скобки вместе с содержимым, 
#которые не содержат внутри себя выражение "SELECT"
        $sql = preg_replace('/
                                \(
                                   (?>
                                        (?>  [^()]  (?<![^a-z\d_]SELECT[^a-z\d_])  )+
                                     |  (?R)
                                   )*
                                \)
                             /sxi', '{_BRACKETS_}', $sql);
На больших объёмах данных это рег. выражение не быстрое.

Еще есть вариант сделать замену '{[' и ']}' на временные метки заменители, которые не встречаются в данных, например на "\x01", "\x02".
 

Offshore

Новичок
Rin, да, разжевать было бы неплохо :)

Что касается замены на метки -- это было одной из первых мыслей, но она была отметена как низкопроизводительная :/

Сейчас пока сделал так:
(?(R)\{|\{\[) ((?:[^\{\}]+|(?R))*) (?(R)\}|\]\})

Т.к. мне важно содержимое только самого верхнего уровня, а внутри этого содержимого скобки "{" и "}" всегда парные даже вне в конструкции типа "{[" или "}]", то можно пойти таким путём. Кстати, если использовать конструкцию (?>[^\{\}]+), то шаблон перестаёт работать правильно.
 

Rin

*
>Что касается замены на метки -- это было одной из первых мыслей, но она была отметена как низкопроизводительная :/

Ну и зря. Это будет работать не медленнее, чем выражение с использованием запаздывающих или опережающих проверок.

В Вашем рег. выражении разобраться сходу невозможно, используйте отступы и переносы строк.

Регулярные выражения PCRE. Обход вложенных тагов с учётом их парности (рекурсивные подмаски)
PHP: 
<pre>
<?php
$s = 'Начало.
     [span]Текст1[/span]
     [span]Текст2 [span]внутри[/span] текcта[/span].
     [span]Текст3 [span]внутри[/span] текcта[/span].
     [span]Текст4[/span]
     [span][/span]
     [span][span][/span][/span]
     Конец.';
$opentag  = '[span]';
$closetag = '[/span]';
$re_opentag  = preg_quote($opentag, '/');
$re_closetag = preg_quote($closetag, '/');
$re = '/
          ' . $re_opentag . '
             (?>
                  (?>  (?!' . $re_opentag . '|' . $re_closetag . ') .  )+
               |  (?R)
             )*
          ' . $re_closetag . '
       /sxi';
#echo $re . "\r\n";
$result = preg_match_all($re, $s, $m);
if ($result === false) echo 'Произошла ошибка с кодом ' . preg_last_error();
elseif ($result > 0) print_r($m);
else echo 'Совпадений не найдено.';
?>
</pre>
Результат работы:
Код: 
Array
(
    [0] => Array
        (
            [0] => [span]Текст1[/span]
            [1] => [span]Текст2 [span]внутри[/span] текcта[/span]
            [2] => [span]Текст3 [span]внутри[/span] текcта[/span]
            [3] => [span]Текст4[/span]
            [4] => [span][/span]
            [5] => [span][span][/span][/span]
        )

)
 

Offshore

Новичок
> Ну и зря. Это будет работать не медленнее, чем выражение с использованием запаздывающих или опережающих проверок.
Отнюдь не факт на больших объёмах. Но проверять лень.


> В Вашем рег. выражении разобраться сходу невозможно, используйте отступы и переносы строк.
(?(R)\{|\{\[) ((?:[^\{\}]+|(?R))*) (?(R)\}|\]\})
[^\{\}]+ -- все символы до появления { или };

(?(R)\{|\{\[) ((?:[^\{\}]+|(?R))*) (?(R)\}|\]\})
((?:[^\{\}]+|(?R))*) -- описание выражения внутри скобок; "отсутствие '{' и '}' или рекурсия";

(?(R)\{|\{\[) ((?:[^\{\}]+|(?R))*) (?(R)\}|\]\})
(?(R)\{|\{\[) -- если мы не на первом уровне, считать за ограничитель '{[', иначе '{' ("Т.к. мне важно содержимое только самого верхнего уровня, а внутри этого содержимого скобки '{' и '}' всегда парные ...").


Кстати, хочу сказать вот что. Я был неправ с самого начала ("проблема состоит в том, чтобы создать подмаску, которая воспринимала бы все строки, в которых не содержатся сочетания символов '{[' или ']}'"). Проблема состояла в том, чтобы выбрать все символы до появления '{[' или ']}'.

Кусок Вашего кода, который её решает -- '(?> (?! \{\[ | \]\} ) . )+'; правда, меня опять терзают смутные сомнения на тему производительности, но тут уж точно без бенчмарков не выяснишь, что к чему, так что воспользуемся пока тем, что есть.

Спасибо!
 

WP

^_^
Встает вопрос о месте где растёт такая славная трава =)
Посмотри Quicky.compiler и Quicky_BBcode.

-~{}~ 23.03.08 06:29:

PHP: 
$string = '{[{[a{[b]}]}{[c{[d]}]}{[e]}]}';
preg_match('~\{\[((?:(?R)|.)*?)]}~',$string,$matches);
var_dump($matches);
/*
array(2) {
  [0]=>
  string(29) "{[{[a{[b]}]}{[c{[d]}]}{[e]}]}"
  [1]=>
  string(25) "{[a{[b]}]}{[c{[d]}]}{[e]}"
}
*/
 

Offshore

Новичок
Хм, порядок обхода другой.
Здесь он сначала погружается на самый грубокий уровень рекурсии, потом разгребает, а мы сначала вынуждены были разгребать с использованием дополнительной проверки и потом уходить в рекурсию.

В моём коде тоже работает.
И, опять же, навскидку не могу оценить производительность...

Кстати, последние 2 символа ("~\{\[((?:(?R)|.)*?)]}~") лучше всё-таки экранировать.
 

Rin

*
WP
Решение хорошее, но для этой строки работать будет по другому, "заглатывая" открывающие таги, которые не имеют закрывающих. Т.о. проверка на парность некорректна.
PHP: 
$string = '{[
             {[ unclosed!
               {[a{[b]}]}
               {[c{[d]}]}
               {[e]}
           ]}';
 

Rin

*
WP
Учитывая название темы -- неправильный. :)

Я соптимизировал моё предыдущее рег. выражение:
PHP: 
$re = '/
          ' . $re_opentag . '
             [^\[]*  #оптимизация через приём, который называется "раскрутка цикла"
             (?>
                 (?>  (?!' . $re_opentag . '|' . $re_closetag . ') .  )+
               | (?R)
             )*
          ' . $re_closetag . '
       /sxi';
Регулярные выражения (2-е издание), Фридл Д. -- рекомендую тем, кто еще не читал, это высший пилотаж!
 

Offshore

Новичок
Rin,
> [^\[]* #оптимизация через приём, который называется "раскрутка цикла"

Это означает "Всё до первого символа открывающего тега" или "Всё до первого символа закрывающего тега" или вообще, как это трактовать? =) (имею ввиду пример с тегами '[span]' и '[/span]').
 

WP

^_^
Rin
А смысл? Если тег не закрыт, то он закрывается с концом строки.

-~{}~ 23.03.08 23:44:

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

-~{}~ 24.03.08 00:25:

Вообще всё делается намного проще, стеком тегов. Я не зря отправил смотреть продукты в которых это реализовано.
 

Offshore

Новичок
WP, к моменту написания первого поста в эту тему я уже реализовал отдельный парсер на пхп, который проверях вложенность и обрабатывал данные, как было надо.

Но ведь гораздо компактне и изящнее проблему можно решить на PCRE :)
 

WP

^_^
Offshore
А какой смысл в таком неправильном разборе?

berkut
У тебя я посмотрю сезонное обострение?
 

Offshore

Новичок
WP, почему в неправильном? Приведённые Вами примеры работали почти корректно :), а Rin так вообще полностью решил проблему.
 

Rin

*
Самый "скорострельный" вариант с однократными паттернами.
PHP: 
$re = '/
          ' . $re_opentag . '
             (?>
                 (?> [^\[]+ | (?!' . $re_opentag . '|' . $re_closetag . '). )+
               | (?R)
             )*
          ' . $re_closetag . '
       /sxi';
 
Войдите или зарегистрируйтесь для ответа.
Сверху