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

Особенно полезны регулярные выражения в программах, написанных на скриптовых (интерпретируемых) языках, например, VBScript, JScript и Perl. Из-за того, что весь их код интерпретируется, разбор текстовых строк и выражений выполняется неприемлемо медленно. Применение регулярных выражений дает значительное увеличение производительности, поскольку библиотеки, интерпретирующие регулярные выражения, обычно пишутся на низкоуровневых высокопроизводительных языках (С, C++, Assembler). Например, в MSDN с помощью регулярных выражений осуществляется динамическое форматирование HTML-страниц:

Рис.1. Всплывающее окно See Also создается динамически с помощью регулярных выражений. 

Обычно с помощью регулярных выражений выполняются три действия:

• Проверка наличия соответствующей шаблону подстроки.

• Поиск и выдача пользователю соответствующих шаблону подстрок.

• Замена соответствующих шаблону подстрок.

Наибольшее развитие регулярные выражения получили в Perl, где их поддержка встроена непосредственно в интерпретатор. В других языках, как правило, используются реализующие регулярные выражения дополнения и модули сторонних разработчиков. В VBScript и JScript используется объект RegExp, в С/C++ можно использовать библиотеки Regex++ и PCRE (Perl Compatible Regular Expression), а также ряд менее известных библиотек, для Java существует целый набор расширений – ORO , RegExp, Rex и gnu.regexp.

Особняком стоит Microsoft Visual Studio.Net, существующая пока только в beta-версии, но уже удостоившаяся массы публикаций и разговоров. Реализация регулярных выражений в .Net (Regex) полностью совместима с Perl, и даже несколько расширена. Все, что говорится про Perl, вполне применимо к .Net.

В составе ATL 7, также входящего в VC.Net, имеется шаблон XXX, который позволяет встраивать регулярные выражения в C++-программы (независимо от CLR). Он доступен в исходных текстах, поэтому его можно довольно просто приспособить к своим надобностям, то есть встроить в него поддержку нужного языка или добавить необходимую функциональность. Этот шаблон по всей видимости, должен оказаться самой быстрой реализацией регулярных выражений, поскольку весь код подставляется компилятором как inline и, соответственно, компилятор может качественно оптимизировать код. Прямая работа с любыми видами строк (вид строки задается в качестве параметра шаблона) также повышает производительность.

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

Синтаксис регулярных выражений до сих пор не полностью стандартизован. Существует POSIX-версия регулярных выражений, полностью описывающая стандарт синтаксиса для POSIX. Но версия Perl шире и более гибка, чем и объясняется ее широкая распространенность. Большинство библиотек по синтаксису и используемым метасимволам совместимо с Perl, поэтому имеет смысл начать разбираться с использованием регулярных выражений на примере именно этого языка.

Три типа машин регулярных выражений

На практике применяются три типа машин регулярных выражений.

1. DFA (Deterministic Finite-State Automaton – детерминированные конечные автоматы) машины работают линейно по времени, поскольку не нуждаются в откатах (и никогда не проверяют один символ дважды). Они могут гарантированно найти самую длинную строку из возможных. Однако, поскольку DFA содержит только конечное состояние, он не может найти образец с обратной ссылкой и, из-за отсутствия конструкций с явным расширением, не ловит подвыражений. Они используются, например, в awk, egrep или lex.

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.

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

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

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