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

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

Каждое регулярное выражение \(/r/\) описывает язык \(L(/r/)\). Регулярное выражение \(/r/\) рекурсивно строится на основе более простых, аналогично \(L(/r/)\) может быть описан в терминах языков, образуемых подвыражениями \(/r/\).

Введём индуктивное определение регулярных выражений над алфавитом \(\Sigma\), и соответствующих им языков.

Базис

\(/\varepsilon/\) (регулярное выражение, состоящее из пустой строки) – регулярное выражение. \(L(/\varepsilon/) = \{\varepsilon\}\).
Если \(a \in \Sigma\), то \(/a/\) – регулярное выражение, и \(L(/a/) = \{a\}\).

Индукция

Если \(/r/\) и \(/s/\) – регулярные выражения, то:

\(/r | s/\) – регулярное выражение, \(L(/r | s/) = L(/r/) \cup L(/s/)\)
\(/rs/\) (конкатенация r и s) – регулярное выражение, \(L(/rs/) = L(/r/) . L(/s/)\)
\(/r^*/\) – регулярное выражение, \(L(/r^*/) = L(/r/)^*\)
\(/(r)/\) – регулярное выражение, \(L(/(r)/) = L(/r/)\)

Оператор \(|\) назовём оператором альтернативы, \(*\) – оператором замыкания.

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

Оператор \(^*\) левоассоциативен и имеет наивысший приоритет.
Конкатенация левоассоциативна и имеет второй приоритет.
Оператор \(|\) левоассоциативен и имеет наименьший приоритет.

Для удобства записи регулярных выражений, введём понятие регулярных определений.

Регулярные определения: Для алфавита \(\Sigma\), регулярное определение представляет из себя последовательность определений вида \[\begin{align} d_1 & \to /r_1/ \\ d_2 & \to /r_2/ \\ & \ldots \\ d_n & \to /r_n/, \\ \end{align}\] где \(d_i \neq d_j\), если \(i\neq j\), \(d_i \notin \Sigma\) и \(/r_i/\) – регулярные выражения над \(\Sigma \cup \{ d_j\}\), \(i, j \in \{1, \ldots, n\}\).

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

Законы выводятся прямо из определений и свойств соответствующих операций над языками, но имеет смысл их привести.

Оператор \(|\) коммутативен: \(r | s = s | r\)
Оператор \(|\) ассоциативен: \(r|(s|t) = (r|s)|t = r|s|t\)
Альтернатива выражения с самим собой эквивалентна исходному выражению: \(r|r = r\)
Повторная альтернатива идемпотентна: \((r|s)|s = r|s\)
Конкатенация ассоциативна: \((rs)t = r(st) = rst\)
Конкатенация дистрибутивна над \(|\): \(r(s|t) = rs|rt\)
\(\varepsilon\) – нейтральный элемент конкатенации, \(\varepsilon r = r \varepsilon = r\)
\(\varepsilon\) гарантированно входит в замыкание: \(r^* = (r | \varepsilon)^* = r^*|\varepsilon\)
Оператор \(^*\) идемпотентен: \(r^{**} = r^*\)

Расширения регулярных выражений

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

Оператор позитивного замыкания: \(/r^+/ = /rr^*/\)
Оператор 0 или 1: \(/r?/ = /\varepsilon|r/\)
Классы символов. Для \(a_i \in \Sigma\), \(i\in\{1,\ldots, n\}\): \(/[a_1\ldots a_n]/=/(a_1|\ldots|a_n)/\)

Отдельно отметим, что если алфавит \(\Sigma\) упорядочен, то класс идущих подряд символов \([a_1\ldots a_n]\) этого алфавита можно записать через тире, как \([a_1 - a_n]\).

Конечные автоматы

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

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

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

Конечные автоматы разделяются на два класса:

Недетерминированные (НКА) не имеют ограничений на вид графа переходов. В том числе, из одного состояния могут вести несколько дуг, помеченных одним входным символом, или помеченных пустой строкой.
Детерминированные (ДКА) для каждого состояния и каждого символа входного алфавита имеют ровно одно выходящее ребро графа переходов. Рёбра, помеченные пустой строкой, запрещены.

НКА и ДКА являются равномощными, в том смысле, что они способны распознавать одинаковые множества языков, называемые регулярными языками. К понятию регулярных языков вернёмся позже.

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

НКА состоит из:

Множества состояний \(S\)
Входного алфавита \(\Sigma\). Считаем, что символ \(\varepsilon\), обозначающий пустую строку, не входит в \(\Sigma\).
Функции переходов \(T: (S, \Sigma \cup \{\varepsilon\}) \to S\)
Состояния \(s_0 \in S\), называемого начальным.
Подмножества состояний \(F \subset S\), называемых конечными или принимающими.

Алфавит \(\Sigma\) полагается конечным. В таком случае, функцию переходов \(T\) можно представить в виде таблицы, скажем, в строках которой будут отмечены состояния, а в столбцах – символы алфавита или \(\varepsilon\). Такую таблицу будем называть таблицей переходов.

Будем говорить, что НКА принимает входную строку, если в графе переходов существует путь от начального состояния до некого принимающего, причём такой, что конкатенация меток переходов (в порядке переходов!) образуют входную строку. Метки \(\varepsilon\) естественно отбрасываются в этом рассуждении, поскольку обозначают пустую строку.

Язык, определяемый (или принимаемый) НКА – это множество всех строк, которые принимает НКА.

Построение НКА на основе регулярных выражений

Произвольное регулярное выражение можно преобразовать к НКА, определяющему тот же язык.

Рассмотрим алгоритм МакНотона-Ямады-Томпсона. Это рекурсивный индуктивный алгоритм, построенный аналогично нашему определению регулярных выражений.

Базис

Включает два правила:

Для регулярного выражения \(/\varepsilon/\) строим НКА

где \(i\) – новое состояние, \(f\) – новое принимающее состояние.
Для регулярного выражения \(/a/,\) где \(a\in\Sigma\), строим НКА

где \(i\) – новое состояние, \(f\) – новое принимающее состояние.

Индукция

Пусть \(N(s)\) и \(N(t)\) – НКА для регулярных выражений \(s\) и \(t\) соответственно. Тогда:

Для \(r = /s|t/\), строим НКА

где \(i\) – новое состояние, \(f\) – новое принимающее состояние, переходы из \(i\) осуществляются к начальному состоянию \(N(s)\) и \(N(t)\), а переходы к \(f\) происходят из принимающих состояний \(N(s)\) и \(N(t)\).
Для \(r = /st/\), строим НКА

где \(i\) – новое состояние, \(f\) –новое принимающее состояние. На самом деле ε-переходы можно опустить, отождествив \(i\) с начальным состоянием \(N(s)\), принимающие состояния \(N(s)\) с начальным состоянием \(N(t)\) и принимающие состояния \(N(t)\) с \(f\).
Для \(r=/s*/\), строим НКА

где \(i\) – новое состояние, \(f\) –новое принимающее состояние.
Для \(r=/(s)/\), просто используем \(N(r)=N(s)\).

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

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

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

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

S = ε⁺(s₀);
c = nextChar();
while (c != eof) {
  S = ε⁺(move(S, c));
  c = nextChar();
}
if (S ∩ F != ∅) accept();
else reject();

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

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

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

Распознавание шаблонов при помощи НКА

Задача распознавания шаблонов состоит в том, чтобы выделить из входного потока лексемы и классифицировать их соответственно токенам.

Если построить НКА, соответствующий альтернативе всех шаблонов токенов, такой автомат сможет распознать одну лексему языка.

Чтобы выделить множество лексем, используется следующий подход. Из входного потока читаются символы, моделируется НКА, и запоминается последнее множество состояний, содержащее принимающие. В какой-то момент, НКА окажется в состоянии, из которого нет переходов. Это означает, что найден самый длинный префикс, в котором может быть лексема. Тогда последний шаг, на котором было хоть одно принимающее состояние, соответствует этой лексеме. Производится откат состояния моделирования к этому шагу, и возвращается токен, соответствующий принимающему состоянию. Если принимающих состояний несколько и они соответствуют разным токенам, то обычно выбирается какой-то один токен на основе эвристических приоритетов. Например, if может соответствовать токену ключевого слова и токену идентификатора, однако лексический анализатор, видимо, должен вернуть токен ключевого слова.

Регулярные выражения. Распознавание шаблонов на основе недетерминированного конечного автомата