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

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

вернуться

Jenter Алекс

Шрифт:

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

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

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.