Программирование на Visual C++. Архив рассылки

2. Традиционные NFA-машины (Nondeterministic Finite-State Automaton – недетерминированные конечные автоматы) используют "жадный" алгоритм отката, проверяя все возможные расширения регулярного выражения в определенном порядке и выбирая первое подходящее значение. Поскольку традиционный NFA конструирует определенные расширения регулярного выражения для поиска соответствий, он может искать подвыражения и backreferences. Но из-за откатов традиционный NFA может проверять одно и то же место несколько раз. В результате работает он медленнее. Поскольку традиционный NFA принимает первое найденное соответствие, он может и не найти самое длинное из вхождений. Именно такие механизмы регулярных выражений используются в Perl, Python, Emacs, Tcl и .Net.

3. POSIX NFA – машины похожи на традиционные NFA-машины, за исключением "терпеливости" – они продолжают поиск, пока не найдут самое длинное соответствие. Поэтому POSIX NFA-машины медленнее традиционных, и поэтому же нельзя заставить POSIX NFA предпочесть более короткое соответствие длинному. Одно из главных достоинств POSIX NFA-машины – наличие стандартной реализации.

Чаще всего программисты используют традиционные NFA-машины, поскольку они точнее, чем DFA или POSIX NFA. Хотя в наихудшем случае время их работы растет по экспоненте, использование образцов, снижающих уровень неоднозначности и ограничивающих глубину поиска с возвратом (backtracking), позволяет управлять их поведением, уменьшая время поиска до приемлемых значений.

Различия синтаксиса регулярных выражений

Реально только в синтаксис Perl использование регулярных выражений встроено непосредственно. В остальных языках для этого используются методы классов. Так, например, в C# работа с регулярными выражениями выглядит следующим образом:

Regex re = new Regex("pattern", "options");
MatchCollection mc = re.Matches("this is just one test");
iCountMatchs = mc.Count;

где re – это новый объект-Regex, в чьем конструкторе передается образец поиска (pattern) и опции (options) (Таблица 1), задающие различные варианты поиска

Символ	Значение
I	Поиск без учета регистра.
m	Многострочный режим, позволяющий находить совпадения в начале или конце строки, а не всего текста.
n	Находит только явно именованные или нумерованные группы в форме (?<name>:). Значение этого будет объяснено ниже, при обсуждении роли скобок в регулярных выражениях.
c	Компилирует. Генерирует промежуточный MSIL-код, перед исполнением превращающийся в машинный код.
s	Позволяет интерпретировать конец строки как обыкновенный символ-разделитель. Часто это значительно упрощает жизнь.
x	Исключает из образца неприкрытые незначащие символы (пробелы, табуляция и т.д.) и включает комментарии в стиле Perl (#). Есть некоторая вероятность, что к выходу в свет эти комментарии могут исчезнуть.
r	Ищет справа налево.

Сочетание флагов m и s дает очень удобный режим работы, учитывающий концы строк и позволяющий пропустить все незначащие символы, включая символ конца строки.

Ниже приведен пример на VB 6, использующий внешнюю библиотеку VBScript RegExp, поставляемую с MS Scripting Host. Ее можно скачать с сайта Microsoft (или найти vbscript.dll в большинстве его продуктов). Этот пример разбирает строку и помещает найденные вхождения в список List1.

Dim re As New VBScript_RegExp.RegExp
Dim matchs As MatchCollection
re.Pattern = "pattern"
re.Global = True ' для поиска по всему тексту.
Set matchs = re.Execute("this is just one test")
Dim m As VBScript_RegExp.Match List1.Clear
For Each m In matchs
 List1.AddItem m.Value & " Ndx " & m.FirstIndex & " Len " & m.Length
Next

В других языках все выглядит аналогично.

Perl разделяет составные части определения регулярного выражения символами "/". Выглядит это примерно так:

expression =~ m/pattern/[switches]

Такое выражение выполняет поиск подстроки, соответствующий шаблону 'pattern' в строке expression и возвращает найденные подстроки ($1, $2, $3, …). "m" означает "match", т.е. соответствие. Например,

$test = "this is just one test";
$test =~ m/(o.e)/

вернет "one" в $1.

Для замены применяется выражение

expression =~ s/pattern/new text/[switches]

Это выражение, как несложно догадаться, заменяет "pattern" на "new text". Например:

$test = "this is just one test";
$test =~ s/one/my/

заменит one на my, в результате давая "this is just my test", сохраняемое в $test.

В Perl используются те же опции, что и в .Net, кроме "n" и "r". В других реализациях библиотек регулярных выражений опций меньше, либо вовсе нет. Так, в приведенном выше примере на VB настройки производятся через свойства объекта RegExp. Ниже примеры будут даваться в основном в стиле Perl.

Основы синтаксиса регулярных выражений

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

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

В Perl метасимволы, которые вы хотите использовать не как таковые, а как собственно символы, должны быть прикрыты escape-символом \, как в C++ (в других языках может быть иначе, например, в VB это не нужно). То есть, чтобы найти "[", нужно писать '\['. Символ \ означает, что идущий за ним символ – это спецсимвол, константа и так далее. Например, 'n' означает букву "n". '\n' означает символ новой строки. Последовательность '\\' соответствует "\", а '\(' соответствует "(".

Символ '.' соответствует любому символу, кроме '\n' (если не используется опция 's', увы, доступная только в Perl 5-совместимых реализациях). Чтобы найти любой символ, включая \n, используйте что-нибудь вроде '[.\n]'.

Искомые выражения

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

Классы символов (Character class)

Используя квадратные скобки, можно указать группу символов (это называют классом символов) для поиска. Например, конструкция 'б[аи]ржа' соответствует словам «баржа» и «биржа», т.е. словам, начинающимся с «б», за которым следуют «а» или «и», и заканчивающимся на «ржа». Возможно и обратное, то есть, можно указать символы, которых не должно содержаться в найденной подстроке. Так, '[^1-6]' находит все символы, кроме цифр от 1 до 6. Следует упомянуть, что внутри класса символов '\b' обозначает символ backspace (стирания).