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. Потому и говорят, что квантификаторы обладают жадностью, т.е. находят максимально возможное совпадение.




- Начало -  - Назад -  - Вперед -



Книжный магазин