Perl - статьи

       

Как работают регулярные выражения


Регулярные выражения, использующие квантификаторы, могут порождать процесс, который называется перебор с возвратом (backtracking). Чтобы произошло совпадение текста с шаблоном, надо построить соответствие между текстом и всем регулярным выражением, а не его частью. Начало шаблона может содержать квантификатор, который поначалу срабатывает, но впоследствии приводит к тому, что для части шаблона не хватает текста или возникает несоответствие между текстом и шаблоном. В таких случаях perl возвращается назад и начинает построение соответствия между текстом и шаблоном с самого начала, ограничивая "жадность" квантификатора (именно поэтому процесс и называется "перебор с возвратом"). Перечислим квантификаторы perl:

  • * - ноль или несколько совпадений,
  • + - одно или несколько совпадений,
  • ? - ноль совпадений или одно совпадение,
  • {n} - ровно n совпадений,
  • {n,} - по крайней мере n совпадений,
  • {n,m} - от n до m совпадений.
  • Например квантификатор + соответствует фразе "один или несколько" и является жадным. Расмотрим пошагово принцип перебора с возвратом на примере квантификатора +:

    'aaabc' =~/a+abc/;

    a+ сразу в силу жадности совпадает с тремя а:

    (aaa)bc

    но после aaa не следует строка "abc", а следует "bc". Поэтому результат - failed поэтому анализатор должен откатиться назад и вернуть с помощью a+ два a:

    (aa)abc



    т.е. на втором шаге шаблон найдет совпадение.

    Рассмотрим пример работы еще одного жадного квантификатора *(ноль или несколько совпадений):

    amxdemxg /.*m/

    Сначала будет найдена вся строка abcdebfg в силу жадности .*, потом квантификатору нужно будет найти сравнение с буквой m, произойдет ошибка. Квантификатор .* отдаст одну букву и его содержимое будет уже amxdemx. На конце снова нет буквы m. Будет отдана еще одна буква и снова не будет найдено совпадение со всем шаблоном и наконец квантификатор .* будет содержать подстроку amxde, за которой уже стоит символ m. И поиск на этом и закончится не смотря на то, что в строке amxdemxg содержится не одна буква m. Потому и говорят, что квантификаторы обладают жадностью, т.е. находят максимально возможное совпадение.


    Допустим нужно найти совпадение:

    $uu="How are you? Thanks! I'm fine, you are ok??"; $uu=~s/.*you//; print $uu;

    Квантификатор .* оставит текст " are ok??", а вовсе не "? Thanks! I'm fine, you are ok??". Если же поставить ограничитель ?, который вместе со знаком квантификатора означает максимально возможное совпадение

    $uu="How are you? Thanks! I'm fine, you are ok??"; $uu=~s/.*you//; print $uu;

    то переменная $uu будет содержать текст "? Thanks! I'm fine, you are ok??".

    Предположим нужно найти совпадения типа network workshop, т.е. перекрытия.

    $u='network'; $m='workshop'; print "перекрытие $2 найдено: $1$2$3\n" if("$u $m" =~/^(\w+)(\w+) \2(\w+)$/);

    $1 сразу берет все слово в $u, но дальше идет еще один максимальный квантификатор (\w+), которому тоже чего-то надо и он забирает из переменной \1 букву k(причем только одну):

    #!/usr/bin/perl $uu="asdfg asdf"; $uu=/(\w+)(\w+)\s(\w+)(\w+)/; print "$1 $2##$3 $4"; asdf g##asd f

    далее пошаговая работа regex выглядит примерно так:

    1: 'networ''k'=> '\sk' совпадает ли с '\sworkshop' falure 2: 'netwo''rk'=> '\srk' совпадает ли с '\sworkshop' falure 3: 'netw''ork'=> '\sork' совпадает ли с '\sworkshop' falure 4: 'net''work'=> '\swork' совпадает ли с '\sworkshop' ok

    и в результате программа выдаст: перекрытие work найдено: networkshop

    Данный регексп не сработает, если

    $u='networkwork'; $m='workshop';

    шаблон найдет перекрытия workwork, а не work. Чтобы этого избежать, нужно сделать минимальным \1: /^(\w+?)(\w+) \2(\w+)$/

    Квантификатор действует только на предшествующий ему элемент шаблона. Например, конструкция \d{2}[a-z]+ будет соответствовать последовательности из одной или нескольких строчных латинских букв, начинающейся с двух цифр, а не последовательности, составленной из чередующихся цифр и букв. Для выделения группы элементов, на которую действует квантификатор, используются круглые скобки: (\d{2}(a-z])+


    Содержание раздела