Регулярные выражения для самых маленьких

Моделирование НКА

Определим некоторые вспомогательные функции:

1. \(ε^+(s)\) – множество состояний НКА, достижимых из состояния \(s\) за счёт ε-переходов (т.е. переходе по ребрам, помеченным ε)
2. \(ε^+(T)\) – множество состояний НКА, достижимых из состояния \(s\in T\) за счёт ε-переходов; \
3. \(move(T,a)\) – множество состояний НКА, в которые имеется переход из какого-то состояния \(s\in T\) при входном символе \(a\).

Тогда алгоритм моделирования НКА можно записать в виде:

Здесь читает следующий символ из входного потока, а означает конец входного потока.

Таким образом, на каждом шаге, мы имеем несколько “параллельных” автоматов, каждый из которых находится в своём состоянии и соответствует выбору одного из возможных путей. Каждый раз при чтении символа, производятся все возможные переходы по ε.

Наконец, если хоть один из этих “параллельных” автоматов пришёл к принимающему состоянию, алгоритм принимает строку. Иначе – нет.

Преобразование ДКА в регулярное выражение[править]

Алгебраический метод Бжозовскогоправить

При преобразовании ДКА в регулярное выражение создается система регулярных выражений для каждого состояния в ДКА, а затем она решается для регулярных выражений , связанных с терминальным состояниями . Построение уравнения происходит следующим образом: для каждого состояния уравнение является объединением переходов, ведущих в это состояние. Переход a из в обозначается за . Если — терминальное состояние, то в добавляется . Это приводит к системе уравнений вида:

где = если нет перехода от к .
Система может быть решена с помощью простой подстановки, за исключением случаев, когда неизвестное появляется как в правой, так и в левой части уравнения. Для этого можно воспользоваться теоремой Ардена:

Уравнение вида , где , имеет решение .

Примерправить

Задача: Построить регулярное выражение, удовлетворяющее данному ДКА.

Решение:

Рассмотрим первое терминальное состояние:

Воспользуемся теоремой Ардена:

Рассмотрим второе терминальное состояние :

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

Построение ДКА по РВ

Пусть есть регулярное выражение r
. По данному регулярному выражению необходимо построить детерминированный конечный автомат D
такой, что L
(D
) = L
(r
).

Построение дерева

Представим регулярное выражение в виде дерева, листья которого — терминальные символы, а внутренние вершины — операции конкатенации «.», объединения «∪» и итерации «*». Каждому листу дерева (кроме ε-листьев) припишем уникальный номер и ссылаться на него будем, с одной стороны, как на позицию в дереве и, с другой стороны, как на позицию символа, соответствующего листу.

Вычисление функций nullable, firstpos, lastpos

Теперь, обходя дерево T снизу вверх слева-направо, вычислим три функции: nullable
, firstpos
, и lastpos
. Функции nullable
, firstpos
и lastpos
определены на узлах дерева. Значением всех функций, кроме nullable
, является множество позиций. Функция firstpos
(n
) для каждого узла n синтаксического дерева регулярного выражения дает множество позиций, которые соответствуют первым символам в подцепочках, генерируемых подвыражением с вершиной в n
. Аналогично, lastpos
(n
) дает множество позиций, которым соответствуют последние символы в подцепочках, генерируемых подвыражениями с вершиной n
. Для узлов n
, поддеревья которых (т. е. дерево, у которого узел n
является корнем) могут породить пустое слово, определим nullable
(n
) = true
, а для остальных узлов false
. Таблица для вычисления nullable
, firstpos
, lastpos
:

Построение followpos

Функция followpos
вычисляется через nullable
, firstpos
и lastpos
. Функция followpos
определена на множестве позиций. Значением followpos
является множество позиций. Если i
— позиция, то followpos
(i
) есть множество позиций j
таких, что существует некоторая строка…cd
…, входящая в язык, описываемый РВ, такая, что i
соответствует этому вхождению c
, а j
— вхождению d
. Функция followpos
может быть вычислена также за один обход дерева по следующим двум правилам

1. Пусть n
   — внутренний узел с операцией «.» (конкатенация); a
   , b
   — его потомки. Тогда для каждой позиции i
   , входящей в lastpos
   (a
   followpos
   (i
   ) множество firstpos
   (b
   ).
2. Пусть n
   — внутренний узел с операцией «*» (итерация), a
   — его потомок. Тогда для каждой позиции i
   , входящей в lastpos
   (a
   ), добавляем к множеству значений followpos
   (i
   ) множество firstpos
   (а
   ).

Пример

Вычислить значение функции followpos
для регулярного выражения (a
(b
|c
))*c
.

Построение ДКА

ДКА представляет собой множество состояний и множество переходов между ними. Состояние ДКА представляет собой множество позиций. Построение ДКА заключается в постепенном добавлении к нему необходимых состояний и построении переходов для них. Изначально имеется одно состояние, firstpos
(root
) (root
— корень дерева), у которого не построены переходы. Переход осуществляется по символам из регулярного выражения. Каждому символу соответствует множество позиций {p
i
}. Объединение всех followpos
(x) есть состояние в которое необходимо перейти, где x — позиция, присутствующая как среди позиций состояния и так и среди позиций символа из РВ, по которому осуществляется переход. Если такого состояния нет, то его необходимо добавить. Процесс нужно повторять, пока не будут построены все переходы для всех состояний. Конечными объявляются все состояния, содержащие позицию добавленного в конец РВ символа #.

ДКА, полученный из РВ (a
(b
|c
))*c

Пример

Построить ДКА по регулярному выражению (a
(b
|c
))*c
.

Лемма о разрастании для регулярных языков

Существует простой метод проверки, является или нет заданный язык регулярным. Этот метод основан на проверке так называемой леммы о разраста­нии языка. Доказано, что если для некоторого заданного языка выполняется лемма о разрастании регулярного языка, то этот язык является регулярным; если же лемма не выполняется, то и язык регулярным не является .

Лемма о разрастании для регулярных языков формулируется следующим обра­зом: если дан регулярный язык и достаточно длинная цепочка символов, при­надлежащая этому языку, то в этой цепочке можно найти непустую подцепочку, которую можно повторить сколь угодно много раз, и все полученные таким спо­собом новые цепочки будут принадлежать тому же регулярному языку. (Если найденную подцепочку повторять несколько раз, то исходная цепочка как бы «раз­растается» — отсюда и название «лемма о разрастании языков»).

Формально эту лемму можно записать так: если дан язык L, то $ константа р > 0, такая, что если aÎL и |a| ³ р, то цепочку a можно записать в виде a = dbe, где 0 < |b| < р, и тогда a’ = dbie, a’ÎL «i ³ 0.

Используя лемму о разрастании регулярных языков, докажем, что язык L = {аnЬn | n > 0} не является регулярным.

Предположим, что этот язык регулярный, тогда для него должна выполняться лемма о разрастании. Возьмем некоторую цепочку этого языка a = аnЬn и запи­шем ее в виде a = dbe. Если bÎa+ или bÎb+ то тогда для i = 0 цепочка dbe = deне принадлежит языку L, что противоречит условиям леммы; если же bÎa+b+, тогда для i = 2 цепочка db2e = dbbe не принадлежит языку L. Таким образом, язык L не может быть регулярным языком.

Связь регулярных выражений и регулярных грамматик

Регулярные выражения и регулярные грамматики связаны между собой следую­щим образом:

· для любого регулярного языка, заданного регулярным выражением, можно по­строить регулярную грамматику, определяющую тот же язык;

· для любого регулярного языка, заданного регулярной грамматикой, можно по­лучить регулярное выражение, определяющее тот же язык.

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

Связь регулярных выражений и конечных автоматов

Регулярные выражения и недетерминированные конечные автоматы связаны между собой следующим образом:

· для любого регулярного языка, заданного регулярным выражением, можно построить конечный автомат, определяющий тот же язык;

· для любого регулярного языка, заданного конечным автоматом, можно полу­чить регулярное выражение, определяющее тот же язык.

Известен алгоритм, реализующий построение конечного автомата по регулярному выражению . Алгоритм построения регулярного выражения по конечному автомату здесь не представляет интереса, поскольку проще построить грамматику, эквивалент­ную заданному конечному автомату, а потом уже найти регулярное выражение для заданного грамматикой языка.

Построение конечного автомата на основе леволинейной грамматики

Пусть имеется леволинейная грамматика G(VT,VN,P,S), необходимо построить экви­валентный ей конечный автомат M(Q,V,d,qo,F).

Прежде всего для построения автомата исходную грамматику G необходимо привести к автоматному виду. Известно, что такое преобразование можно вы­полнить для любой регулярной грамматики. Алгоритм преобразования к авто­матному виду был рассмотрен выше, поэтому здесь на данном вопросе останав­ливаться нет смысла. Можно считать, что исходная грамматика G уже является леволинейной автоматной грамматикой.

Тогда построение конечного автомата M(Q,V,d,qo,F) на основе грамматики G(VT, VN, P, S) выполняется по следующему алгоритму.

Шаг 1. Строим множество состояний автоматаQ, Состояния автомата строятся таким образом, чтобы каждому нетерминальному символу из множества VN грам­матики G соответствовало одно состояние из множества Q автомата М. Кроме того, во множество состояний автомата добавляется еще одно дополнительное состояние, которое будем обозначать Н. Сохраняя обозначения нетерминальных символов грамматики G, для множества состояний автомата М можно записать:

Q=VNÈ{H}.

Шаг 2. Входным алфавитом автомата М является множество терминальных сим­волов грамматики G: V = VT.

Шаг 3. Просматриваем все множество правил исходной грамматики.

Если встречается правило вида AtÎP, где AÎVN, tÎVT, то в функцию перехо­дов d(H,t) автомата М добавляем состояние A: AÎd(H,t).

Если встречается правило вида ABtÎP, где A,BÎVN, tÎVT, то в функцию пе­реходов d(B,t) автомата М добавляем состояние A: AÎd(B,t).

Шаг 4. Начальным состоянием автомата М является состояние Н: qo = Н.

Шаг 5. Множество конечных состояний автомата М состоит из одного состоя­ния. Этим состоянием является состояние, соответствующее целевому символу грамматикиGF = {S}.

На этом построение автомата заканчивается.

Детерминированный и недетерминированный конечные автоматы

Детерминированный конечный автомат может разобрать строку в один проход из начала в конец, не используя дополнительной памяти кроме заранее заданных таблицы состояний и таблицы переходов между состояниями по событиям. В этой предсказуемости и линейной сложности разбора строки его главное преимущество. Например, в конце разбора строки автомат лексического анализатора приходит в состояние accepted либо в состояние error, что означает успешный или неуспешный разбор строки на токены соответственно.

Любой детерминированный конечный автомат имеет эквивалентное регулярное выражение, и эквивалетный язык регулярной грамматики, и наоборот. По сути это три разных формы представления одной сущности.

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

Метод сопоставления образцов

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

Постановка задачи

Имеется множество образцов, для каждого из которых определён кусок промежуточного представления, для которого он применим, вес и генерируемый код. Есть дерево промежуточного представления, представляющее собой фрагмент программы, для которой необходимо код сгенерировать. Целью является построение такого покрытия дерева промежуточного представления образцами, чтобы суммарный вес образцов был минимален.

Образцы — это ассемблерные команды и деревья разбора, которые им соответствуют. Про каждый образец известно время его выполнения (в тактах). С их помощью и будем генерировать оптимальный (по времени выполнения) код.

Примеры образцов

Построение покрытия

Теперь для каждой вершины (перебираем их в порядке от листьев к корню) будем генерировать оптимальный код для ее поддерева. Для этого просто переберем все образцы, применимые в данной вершине. Время выполнения при использовании конкретного образца будет складываться из времени вычисления его аргументов (а оптимальный код для их вычисления мы уже знаем благодаря порядку обхода дерева) и времени выполнения самого образца. Из всех полученных вариантов выбираем лучший — он и будет оптимальным кодом для поддерева данной вершины. В корне дерева получим оптимальный код для всего выражения.

Генерация кода

Код для всех вершин выписывать не обязательно — достаточно записать минимальное необходимое время и образец, которым нужно воспользоваться. Все остальное из этого легко восстанавливается.

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

Регулярные выражения в .Net

Как уже упоминалось выше, регулярные выражения широко используются практически во всех языках программирования. Каждый из языков накладывает свой отпечаток на синтаксис регулярных выражений, хотя суть и не меняется. Так, например, то, что в JScript пишется /a.c/, в VBScript, естественно, будет «a.c».

Microsoft всегда старается сделать все по-своему, поэтому синтаксис регулярных выражений .NET несколько расширен, и включает ряд новых возможностей – например, поиск справа налево. Пишущие по-арабски поймут, зачем это нужно.

Таблица 4. Метасимволы в .Net

Кстати, регулярные выражения в .Net умеют понимать русский язык. Особенно интересно и слегка непривычно то, что они делают это корректно. В Help’е сказано, например, что при поиске границы слова с использованием \b работают символы , однако верить этому не следует. На практике это не так. Русские буквы ищутся и находятся не хуже латиницы. Впрочем, может быть, к release-версии все будет приведено к соответствию с Help’ом.

Классы, определяющие регулярные выражения .NET – это часть библиотеки базовых классов Microsoft .NET Framework, что означает одинаковую реализацию регулярных выражений для всех языков и средств, работающих с CLR (Common Language Runtime) – естественно, за вычетом языковых особенностей, типа уже упоминавшихся escape-символов.

В .Net появились условные сравнения (conditional evaluation). Позволяет варьировать используемые шаблоны в зависимости от результатов поиска предыдущего подвыражения. Это заставит, например, пропустить правую скобку, если левая уже была найдена подвыражением. К сожалению, информация об этом пока слишком обрывочна, чтобы говорить об этом подробнее.

Положительный и отрицательный lookbehind. Последние версии Perl поддерживают такую возможность для строк фиксированной длины. У машины регулярных выражений .NET эта возможность не ограничена ничем, кроме здравого смысла.

Кроме перечисленных, есть еще и масса других, менее значительных дополнений и расширений, но перечислять их все нет ни сил, ни желания. Особенно учитывая, что всё может измениться без предупреждения.

Большая ложка дегтя

Увы, Microsoft традиционно пребывает в состоянии творческого безумия, и правая рука у него не знает, что делает левая (подробнее об этом см. «Средства программирования). Поэтому в саму среду Microsoft .Net встроена ДРУГАЯ библиотека регулярных выражений. Если они это изменят до выхода финальной версии (все, что вы здесь читаете, написано на базе beta 1), честь им и хвала. Если же не изменят (например, по забывчивости), разработчикам, скорее всего, придется работать по принципу «одним пользуемся, другое продаем».

Компиляция и повторное использование регулярных выражений

По умолчанию Regex компилирует регулярные выражения в последовательность внутренних байт-кодов регулярных выражений (это высокоуровневый код, отличный от Microsoft intermediate language (MSIL)). При исполнении регулярных выражений байт-код интерпретируется.

Если же конструировать объект Regex с опцией ‘с’, он компилирует регулярные выражения в MSIL-код вместо упомянутого байт-кода. Это позволяет JIT-компилятору Microsoft .NET Framework преобразовать выражение в родные машинные коды для повышения производительности.

Но сгенерированный MSIL нельзя выгрузить. Единственный способ выгрузить код – это выгрузить из памяти приложение целиком. Это значит, что занимаемые скомпилированным регулярным выражением ресурсы нельзя освободить, даже если сам объект Regex уже освобожден и уничтожен сборщиком мусора.

Из-за этого казуса приходится задумываться – стоит ли компилировать регулярные выражения с опцией ‘с’, и если да, то какие и сколько. Если приложение должно постоянно использовать множество регулярных выражений, придется обойтись интерпретацией. А вот если есть несколько постоянно используемых регулярных выражений, можно и скомпилировать их для ускорения работы.

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

Символьные классы — \d \w \s и .

\d соответствует одному символу, который является цифрой -> тест\w соответствует слову (может состоять из букв, цифр и подчёркивания) -> тест\s соответствует символу пробела (включая табуляцию и прерывание строки). соответствует любому символу -> тест

Используйте оператор с осторожностью, так как зачастую класс или отрицаемый класс символов (который мы рассмотрим далее) быстрее и точнее. У операторов , и также есть отрицания ― исоответственно

У операторов , и также есть отрицания ― исоответственно.

Например, оператор будет искать соответствия противоположенные .

\D соответствует одному символу, который не является цифрой -> тест

Некоторые символы, например , необходимо выделять обратным слешем .

\$\d соответствует строке, в которой после символа $ следует одна цифра -> тест

Непечатаемые символы также можно искать, например табуляцию , новую строку , возврат каретки .

Свойства регулярных языков

Множество называется замкнутым относительно некоторой операции, если в ре­зультате выполнения этой операции над любыми элементами, принадлежащими данному множеству, получается новый элемент, принадлежащий тому же мно­жеству.

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

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

Например, регулярные языки замкнуты относительно следующих операций:

· пересечения;

· объединения;

· дополнения;

· итерации;

· конкатенации;

· гомоморфизма (изменения имен символов и подстановки цепочек вместо сим­волов).

Поскольку регулярные множества замкнуты относительно операций пересечения, объединения и дополнения, то они представляют булеву алгебру множеств. Су­ществуют и другие операции, относительно которых замкнуты регулярные мно­жества. Вообще говоря, таких операций достаточно много.

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

Например, доказано, что разрешимыми являются следующие проблемы.

· Проблема эквивалентности. Даны два регулярных языка L1(V) и L2(V). Необхо­димо проверить, являются ли эти два языка эквивалентными.

· Проблема принадлежности цепочки языку. Дан регулярный язык L(V) и цепочка символов aÎV*. Необходимо проверить, принадлежит ли цепочка данному языку.

· Проблема пустоты языка. Дан регулярный язык L(V). Необходимо проверить, является ли этот язык пустым, то есть найти хотя бы одну цепочку a¹l, такую что aÎL(V).

Эти проблемы разрешимы вне зависимости от того, каким из трех способов за­дан регулярный язык. Следовательно, эти проблемы разрешимы для всех спосо­бов представления регулярных языков: регулярных множеств, регулярных грам­матик и конечных автоматов. На самом деле достаточно доказать разрешимость любой из этих проблем хотя бы для одного из способов представления языка, то­гда для остальных способов можно воспользоваться алгоритмами преобразова­ния, рассмотренными выше. (Возможны и другие способы представления регулярных множеств, а для них разреши­мость указанных проблем будет уже не очевидна.)

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

Обратные ссылки, Lookahead- и Lookbehind-условия

Обратные ссылки

Мы уже говорили об одной из важнейших возможностей регулярных выражений – способность сохранения части соответствий для дальнейшего использования. Кстати, избежать этого можно с помощью использования ‘?:’.

Например,

$test = "Today is monday the 18th.";
$test =~ m/(+)th/

сохранит «18» в $1, а

$test = "Today is monday the 18th.";
$test =~ m/+th/

ничего не станет сохранять – из-за отсутствия скобок.

$test = "Today is monday the 18th.";
$test =~ m/(?:+)th/

также ничего не станет сохранять благодаря использованию оператора ‘?:’.

Следующий пример демонстрирует, как можно использовать эту возможность в операции замены:

$test = "Today is monday the 18th.";
$test =~ s/ the (+)th/, and the day is $1/

приведет к записи «Today is monday, and the day is 18.» в переменную $test.

Можно ссылаться на подстроки, уже найденные данным запросом, используя \1, \2, …, \9. Следующее регулярное выражение удалит повторяющиеся слова:

$test = "the house is is big";
$test =~ s/\b(\S+)\b(\s+\1\b)+/$1/

записывает «the house is big» в $test.

Lookahead- и Lookbehind-условия

Иногда нужно сказать «найдите вот это, но только если перед ним не стоит вот этого», или «найдите вот это, но только если за ним не стоит вот этого». Пока речь идет об одиночном символе, достаточно воспользоваться .

В более сложном случае придется использовать так называемые lookahead-условия или lookbehind-условия. Не путайте Positive lookahead с оптимистичным взглядом в будущее. Всего есть четыре типа таких условий:

• Положительное lookahead-условие ‘(?=re)’
  Соответствует, только если за ним следует регулярное выражение re.
• Отрицательное lookahead-условие ‘(?!re)’
  Соответствует, только если за ним не следует регулярное выражение re.
• Положительное lookbehind-условие ‘(?<=re)’
  Соответствует, только если перед ним следует регулярное выражение re.
• Отрицательное lookbehind-условие ‘(?<!re)’
  Соответствует, только если перед ним не следует регулярное выражение re.

Примеры:

$test = "HTML is a document description-language and not a programming-language";
$test =~ m/(?<=description-)language/

Найдет первое «language» («description-language»), как предваряемое «description-«, а

$test = "HTML is a document description-language and not a programming-language";
$test =~ m/(?<!description-)language/

Найдет второе «language» («programming-language»).

Следующие примеры выполнены в .Net. Поиск осуществляется в следующем тексте:

void aaa
{
  if(...)
  {
    try { ... }
    catch(Exception e1)  {  MessageBox.Show(e1.ToString(), "Error");  }
    finally  {  listBox1.EndUpdate();  }
  }
}

Положительный Lookahead

Шаблон \{(?=*\}).*?\} находит самый глубоко вложенный блок, выделенный фигурными скобками. Результат выполнения:

1. { … }
2. { MessageBox.Show(e1.ToString(), «Error»); }
3. { listBox1.EndUpdate(); }

Положительный Lookbehind

Шаблон (?<=try\s*)\{(?=*\}).*?\} находит самый глубоко вложенный блок выделенный фигурными скобками, перед которым есть try. Результат выполнения: { … }.

Отрицательный Lookbehind

Шаблон (?<!try\s*)\{(?=*\}).*?\} находит самый глубоко вложенный блок выделенный фигурными скобками перед которым нет слова try. Результат выполнения:

1. { MessageBox.Show(e1.ToString(), «Error»); }
2. { listBox1.EndUpdate(); }

В этих примерах жирным выделены Lookahead- и Lookbehind-условия.

Еще примеры

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

Перестановка двух первых слов:

s/(\S+)(\s+)(\S+)/$3$2$1/

В других языках замена обычно делается отдельным методом, одним из параметров передается шаблон замены, где можно использовать переменные $1, $2, $3 и т.д.

m/(\w+)\s*=\s*(.*?)\s*$/

Здесь имя – в $1, а значение — в $2.

m/(\d{4})-(\d\d)-(\d\d)/

Теперь YYYY — в $1, MM — в $2, DD — в $3.

Выделение пути из имени файла:

m/^.*(\\|\/)

В «Y:\KS\regExp\!.Net\Compilation\ms-6D(1).tmp» такое выражение найдет «Y:\KS\regExp\!.Net\Compilation\»

Будучи примененным к файлу С++, выделяет комментарии, строки и идентификаторы «new», «static char» и «const». Работает и на старом RegExp:

("(\\"|\\\\|)*"|/\*.*\*/|//*|#\S+|\b(new|static char|const)\b)

Выделяет тег <a href=»…»> в HTML-коде:

<\s*a("*"|)*>