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

ДКА является частным случаем НКА. В нем:

нет состояния с ε-переходами;

для каждого состояния S и входного символа а существует не более одной дуги, исходящей из S и помеченной а.

ДКА имеет лишь максимум один переход для любого входного символа из каждого состояния. Если для представления функции переходов ДКА использовать таблицу, то в каждой записи будет содержаться лишь одно состояние. Таким образом, легко проверить, допускает ли данный ДКА некоторую строчку, так как есть лишь один путь из стартового состояния, который помечен этой строкой.

На рисунке 3 показан граф переходов ДКА, допускающий тот же язык (a|b) * a(a|b)(a|b), что и НКА на рисунке 1.

Рисунок 3. ДКА, допускающий строку (a|b) * a(a|b)(a|b).

Детерминированный конечный автомат M, допускающий данный язык:

M = {{1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, D, 1, {3, 5, 6, 8}}

Функция переходов D определяется так:

Построение нка по регулярному выражению

1. Для ε НКА имеет следующий вид (0 – начальное состояние, 1 – конечное):

2. Для а, входящего в данный язык НКА:

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

Для регулярного выражения s|t составной НКА имеет следующий вид:

b. Для регулярного выражения st НКА:

с. Для выражения s* НКА имеет вид:

d. Для выражения в скобках (s) используется НКА N(s) как в пункте а.

Каждое новое состояние получает индивидуальное имя. Построение НКА N(r) имеет следующие свойства:

N(r) имеет количество состояний, которое не превышает количества символов более чем в 2 раза.

N(r) имеет ровно одно начальное и одно конечное состояние. Конечное состояние не имеет исходящих переходов.

Каждое состояние N(r) имеет либо 1 переход для символа из алфавита (), либо не более 2-й исходящих ε-переходов.

Преобразование нка в дка.

НКА на рисунке 1 имеет 2 перехода из состояния 0 для символа а: состояния 0 и 1. Такой переход неоднозначен, как и переход по ε. Моделирование таких НКА с помощью компьютерной программы значительно затрудняется. Определение допустимости утверждает, что должен существовать некоторый путь из начального состояния к конечному, но когда есть несколько путей для одной и той же входной строки, их надо рассматривать все, чтобы найти путь к заключительному состоянию или выяснить, что такого пути нет.

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

Рассмотрим подобное преобразование на конкретном примере. На рисунке 4 изображен еще один НКА, который допускает язык (a|b) * a(a|b)(a|b) (как и на рисунках 1 и 3).

Рисунок 4. НКА, допускающий язык (a|b) * a(a|b)(a|b)

Изображенный на рисунке переход из состояния 13 в состояние 14 может быть представлен аналогично переходу из 8-го в 13-е состояние.

Построим ДКА для данного языка. Стартовое состояние эквивалентного ДКА представляет собой состояние A ={0, 1, 2, 4, 7}, то есть те состояния, в которые можно попасть из 0 по ε.

Алфавит входных символов представляет собой {a, b}. Из начального состояния А можно вычислить состояние, достижимое по а. Назовем это состояние В = {1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14}.

Среди состояний в А только состояние 4 имеет переход по b в состояние 5, так что ДКА имеет переход по b из А в состояние С = {1, 2, 4, 5, 6, 7}.

Если продолжить этот процесс с состояниями В и С, все множества состояний НКА будут помечены. Таким образом будем иметь множества состояний:

A = {0, 1, 2, 4, 7}

В = {1, 2, 3, 4, 6, 7, 8, 9, 11, 13, 14}

С = {1, 2, 4, 5, 6, 7}

D = {10, 12, 13, 14}

Состояние А – начальное, а состояния B, D, E – заключительные.

Полностью таблица переходов приведена ниже.

Ниже на рисунке 5 приведен сам ДКА для этого языка.

Рисунок 5. ДКА, допускающий язык (a|b) * a(a|b)(a|b)

Список использованной литературы:

Пентус А. Е., Пентус М. Р. – Теория формальных языков

А. Ахо, Р. Сети, Д, Ульман – Компиляторы: принципы, технологии, инструменты.

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

Команда grep операционной системы Unix или аналогичные команды для поиска цепочек, которые можно встретить в Web-броузерах или системах форматирования текста. В таких системах РВ используются для описания шаблонов, которые пользователь ищет в файле. Различные поисковые системы преобразуют РВ либо в детерминированный конечный автомат (ДКА), либо недетерминированный конечный автомат (НКА) и применяют этот автомат к файлу, в котором производится поиск.
Генераторы лексических анализаторов. Лексические анализаторы являются компонентом компилятора, они разбивают исходную программу на логические единицы (лексемы), которые могут состоять из одного или нескольких символов и имеют определенный смысл. Генератор лексических анализаторов получает формальные описания лексем, являющиеся по существу РВ, и создает ДКА, который распознает, какая из лексем появляется на его входе.
РВ в языках программирования.

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

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

Конечный автомат (КА) - это преобразователь, который позволяет сопоставить входу соответствующий выход, причем выход этот может зависеть не только от текущего входа, но и от того, что происходило раньше, от предыстории работы конечного автомата. Даже поведение человека, а не только искусственных систем можно описать с помощью КА. Например, ваша реакция на то что ваш сосед слушает громко музыку по ночам, будет одной после первого такого случая и совершенно другой после нескольких таких случаев. Таких предысторий может быть бесконечное число, возникает вопрос: какой памятью должен обладать КА, чтобы вести себя по разному для каждой предыстроии? Понятно, что хранить бесконечное число предысторий невозможно. Поэтому автомат как бы разбивает все возможные предыстории на классы эквивалентности. Две истории являются эквивалентными, если они одинаково влияют на поведение автомата в дальнейшем. Класс эквивалентности к которому автомат отнес свою текущую предысторию, называют еще внутренним состоянием автомата.

Рассмотрим пример работы примитивного КА:

Данный КА состоит из:

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

Считывающее устройство может двигаться в одном направлении, как правило слева на право, тем самым считывая символы входной цепочки. За каждое такое движение оно может считать один символ. Далее, считанный символ передается блоку управлений. Блок управления изменяет состояние автомата на основе правил переходов. Если список правил переходов не содержит правила для считанного символа, то автомат «умирает».

Теперь рассмотрим, какими способами можно задать КА. Они могут задаваться в виде графов или в виде управляющих таблиц. В виде графа КА задается следующим способом:

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

В виде управляющей таблицы, так:

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

Пример КА в виде графа и в виде управляющей таблицы будет представлен ниже.

ДКА и НКА

Основное отличие ДКА и НКА состоит в том, что ДКА в процессе работы может находится только в одном состоянии, а НКА в нескольких состояниях одновременно. В качестве примера работы НКА можно привести идею американского физика Хью Эверетта от том, что любое событие разбивает мир на несколько миров, в каждом из которых это событие закончилось по-своему. Например, в одном мире Гитлер выиграл Вторую мировую войну, в другом – Ньютон вместо физики занялся бизнесом и открытие законов классической механики пришлось отложить лет на 50. Чтобы сделать какие-то выводы из работы автомата, следует изучить все «миры». После того как вся входная цепочка будет считана, мы полагаем, что НКА допускает данную цепочку, если он завершил работу в допускающем состоянии хотя бы в одном из множества «миров». Соответственно, автомат отвергает цепочку, если он завершил работу в недопускающем состоянии в каждом «мире». ДКА же принимает цепочку, это очевидно, если после считывания всей входной цепочки он оказывается в допускающем состоянии.

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

Построение минимального ДКА по регулярному выражению

Для начала приведем список операций РВ используемый в данной статье, в порядке их приоритетности:

итерация (замыкание Клини), с помощью символа "*"
конкатенация задается с помощью пробела или пустой строки (например: ab)
объединение, с помощью символа "|"

Рассмотрим пример, дано регулярное выражение:

Xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)

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

Для начала упростим данное РВ, используя правосторонний дистрибутивный закон конкатенации относительно объединения получаем следующее РВ:

(xy* | ab | (x | a*)) (x | y*)

Теперь строим автомат по данному РВ:

По правилу преобразования конкатенации (не будем приводить правила преобразования РВ в КА, так как они довольно очевидные), получаем следующий автомат:

По правилу преобразования объединения:

По правилу преобразования конкатенации:

И в конце применяем правило преобразования замыкания и получаем εНКА. Здесь нужно оговорится, что εНКА - это НКА, который содержит ε-переходы. В свою очередь ε-переход - это переход, при котором автомат не учитывает входную цепочку или другими словами переход по пустому символу.

Избавляемся от ε-переходов («звездочкой» обозначены конечные состояния):

В данном НКА состояния s3 и s5 эквивалентны, так как δ(s3, x) = δ(s5, x) = s1 и δ(s3, y) = δ(s5, y) = s5, s7. Переименовываем состояния s6 -> s5 и s7 -> s6:

Строим ДКА по НКА:

В данном ДКА состояния p1 и p5 эквивалентны, так как
δ(p1, x) = δ(p5, x) = p4 и δ(p1, y) = δ(p5, y) = p5. Переименовываем состояния p6 -> p5 и p7 -> p6:

Данный автомат является минимальным ДКА.

Пускай δ - функция переходов, то расширенную функцию переходов, построенную по δ, обозначим δ’, и ω - входная цепочка.

Допустим на вход подается цепочка ω = aaax, мы ожидаем, что автомат окажется в одном из допускающих состояний.

δ’(p0, ε) = p0
δ’(p0, a) = δ(δ’(p0, ε), a) = δ(p0, a) = p3
δ’(p0, aa) = δ(δ’(p0, a), a) = δ(p3, a) = p5
δ’(p0, aaa) = δ(δ’(p0, aa), a) = δ(p5, a) = p5
δ’(p0, aaax) = δ(δ’(p0, aaa), x) = δ(p5, x) = p4

P4 - допустимое конечное состояние, таким образом цепочка aaax является корректной для данного автомата.

Теперь допустим, что ω = xyyb:

δ’(p0, ε) = p0
δ’(p0, x) = δ(δ’(p0, ε), x) = δ(p0, x) = p1
δ’(p0, xy) = δ(δ’(p0, x), y) = δ(p1, y) = p1
δ’(p0, xyy) = δ(δ’(p0, xy), y) = δ(p1, y) = p1
δ’(p0, xyyb) = δ(δ’(p0, xyy), b) = δ(p1, b) = ∅

Здесь мы видим, что если подать на вход автомату символ b, когда он находится в состоянии p1, то данный автомат умрет, следовательно цепочка xyyb - некорректна.

P. S. В данной статье был рассмотрен алгоритм построение ДКА по РВ, но существуют более удобные алгоритмы, в частности для программирования, но это уже тема для другой статьи…

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

Конечный автомат это пятерка (S, S, d, S 0 , F)

S - конечное множество состояний.

S - конечное множество допустимых входных сигналов.

d - функция переходов. Она отражает множество Sх(SÈ{e}) в множество состояний недетерминированного конечного автомата. Для детерминированного автомата функция переходов отражает множество SхS во множество состояний автомата. Другими словами, в зависимости от состояния и входного символа, d определяет новое состояние автомата.

S 0 - начальное состояние конечного автомата, S 0 Î S.

F - множество конечных состояний автомата, F Î S.

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

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

1 Регулярное выражение “e” преобразуется в автомат из двух состояний и e -перехода между ними (рисунок 1).

Рисунок 1. – Автомат для e-перехода

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

Рисунок 2. – Автомат для перехода по символу а

3 Пусть есть регулярное выражение rs и уже построены конечные автоматы для выражения r и выражения s. Тогда два автомата соединяются последовательно. На рисунке 3 представлены исходные автоматы для языков r и s. На рисунке автомат для распознавания конкатенации этих языков.

Автомат для r Автомат для s

Рисунок 3. – Исходные автоматы

Рисунок 4. – Автомат для конкатенации языков

4 Пусть есть регулярное выражение r | s и уже построены конечные автоматы для выражения r и выражения s (рисунок 3). Тогда в результирующем автомате должна быть альтернатива выполнения одного из двух автоматов. То есть автомат для выражения r | s при автоматах для r и s с рисунка 3 имеет вид, представленный на рисунке 5.

Рисунок 5. – Автомат для объединения языков

5 Пусть есть регулярное выражение r* при построенном конечном автомате r. В этом случае вводятся два новых состояния для возможности обхода автомата выражения r, а также вводится e-переход между конечным и начальным состояниями для возможности многократного повторения автомата r. Если для регулярного выражения r построен автомат аналогичный рисунку 3, то регулярному выражению r* соответствует конечный автомат, представленный на рисунке 6.

Основные определения Регулярные выражения в алфавите Σ и регулярные множества, которые они обозначают, определяются рекурсивно следующим образом: 1) – регулярное выражение, обозначающее регулярное множество; 2) e – регулярное выражение, обозначающее регулярное множество {e}; 3) если a Σ, то a – регулярное выражение, обозначающее регулярное множество {a}; 4) если p и q – регулярные выражения, обозначающие регулярные множества P и Q, то а) (p+q) – регулярное выражение, обозначающее P Q; б) pq – регулярное выражение, обозначающее PQ; в) p* – регулярное выражение, обозначающее P*; 5) ничто другое не является регулярным выражением.

Основные определения Расстановка приоритетов: * (итерация) – наивысший приоритет; конкатенация; + (объединение). Таким образом, 0 + 10* = (0 + (1 (0*))). Примеры: 1. 01 означает {01}; 2. 0* – {0*}; 3. (0+1)* – {0, 1}*; 4. (0+1)* 011 – означает множество всех цепочек, составленных из 0 и 1 и оканчивающихся цепочкой 011; 5. (a+b) (a+b+0+1)* означает множество всех цепочек {0, 1, a, b}*, начинающихся с a или b.

Основные определения Леммы: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5) α(β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α

Связь РВ и РМ РМ – языки, порождаемые РВ. Например: x = a+b, y = c+d, x X = {a, b}, y Y = {c, d}, x + y X Y = {a, b, c, d}. Конкатенация: xy XY = {ac, ad, bc, bd}. к(и+о)т {к}{и, о}{т} = {кит, кот} или по леммам № 5 и № 6 к(и+о)т = кит + кот {кит, кот}. Итерация: x = a, x* X* = {e, a, aaa, …}, т. е. x* = e + xxx + …

Связь РВ и РМ Итерация конкатенации и объединения: (xy)* = e + xyxyxy + … (x + y)* = e + (x + y)(x + y) + … = = e + xx + xy + yx + yy + xxx + … Пример: 0 + 1(0+1)* {0} ({1} {0, 1}*) = {0, 1, 10, 11, 100, 101, 110, 111…}. Объединение коммутативно: x + y = y + x Конкатенация – нет: xy ≠ yx

Связь РВ и РМ Примеры на приоритет: x + yz {x, yz}, (x + y)z {xz, yz}, x + y* {e, x, y, yyy, yyyy, …}, (x + y)* {e, x, y, xx, xy, yx, yy, xxx, …}, (xy)* {e, xyxy, …}, xy* {x, xyy, xyyy, …}. Новые леммы: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; и т. д.

Регулярные системы уравнений Уравнение с регулярными коэффициентами X = a. X + b имеет решение (наименьшую неподвижную точку) a*b: aa*b + b = (aa* + e)b = a*b Система уравнений с регулярными коэффициентами: X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1 n. Xn X 2 = α 20 + α 21 X 1 + α 22 X 2 + … + α 2 n. Xn …………………………. . Xn = αn 0 + αn 1 X 1 + αn 2 X 2 + … + αnn. Xn Неизвестные – Δ = {X 1, X 2, …, Xn}.

Регулярные системы уравнений Алгоритм решения (метод Гаусса): Шаг 1. Положить i = 1. Шаг 2. Если i = n, перейти к шагу 4. Иначе записать уравнения для Xi в виде Xi = αXi + β (β = β 0 + βi+1 Xi+1 + … + βn. Xn). Затем в правых частях для уравнений Xi+1, …, Xn заменим Xi регулярным выражением α*β. Шаг 3. Увеличить i на 1 и вернуться к шагу 2. Шаг 4. Записать уравнение для Xn в виде Xn = αXn + β. Перейти к шагу 5 (при этом i = n). Шаг 5. Уравнение для Xi имеет вид Xi = αXi + β. Записать на выходе Xi = α*β, в уравнениях для Xi– 1, …, X 1 подставляя α*β вместо Xi. Шаг 6. Если i = 1, остановиться, в противном случае уменьшить i на 1 и вернуться к шагу 5.

Преобразование ДКА в РВ Для ДКА M = (Q, Σ, δ, q 0, F) составим систему с регулярными коэффициентами где Δ = Q: 1. полагаем αij: = ; 2. если δ(Xi, a) = Xj, a Σ, то αij: = αij + a; 3. если Xi F или δ(Xi,) = HALT, то αi 0: = e. После решения искомое РВ будет X 1 = q 0.

Преобразование ДКА в РВ Пример: для числа с фиксированной точкой получим систему q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 Здесь: s – знак числа, s = "+" + "–"; p – десятичная точка, p = ". "; d – цифры, d = "0" + "1" + … + "9".

Преобразование ДКА в РВ Решение: q 0 = *(sq 1 + pq 2 + dq 3 + q 4 +) = sq 1 + pq 2 + dq 3 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 = pq 2 + dq 3, q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4, q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = dq 3 + pq 4 + e, q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4 + e. Из третьего уравнения: q 3 = dq 3 + pq 4 + e = d*(pq 4 + e). Из четвертого уравнения: q 4 = dq 4 + e = d*.

Преобразование ДКА в РВ Обратный ход: q 3 = d*(pq 4 + e) = d*(pd* + e), q 2 = dq 4 = dd*, q 1 = pq 2 + dq 3 = pdd* + dd*(pd* + e), q 0 = sq 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Таким образом, данному ДКА соответствует РВ s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Упростим: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) = = spdd* + sdd*(pd* + e) + pdd* + dd*(pd* + e) = (s + e)(pdd* + dd*(pd* + e)) Для более короткой записи можно использовать положительную итерацию aa* = a*a = a+: (s + e)(pdd* + dd*(pd* + e)) = (s + e)(pd+ + d+pd* + d+)

Преобразование ДКА в РВ Сопоставление графа функции переходов ДКА основным операциям с регулярными выражениями: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*

Преобразование ДКА в РВ Более сложные комбинации операций: q 0 a q 1 b b b q 0 a q 2 q 1 (a + e)b c b q 0 q 2 ab(cab)* q 0 (a + b)* q 0 a q 1 aa* = a+ q 0 a q 1 a b a a a (ab)+ q 2 b q 1 c e + (a + b)c*

Преобразование ДКА в РВ Для РВ (s + e)(pd+ + d+(pd* + e)): q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d

Программирование РВ Регулярные выражения: Встроены во многие языки программирования (PHP, Java. Script, …); Реализованы в виде подключаемых компонентов (например, класс Regex для платформы. NET). Отличия в формах записи: x? = x + e x{1, 3} = x + xxx и т. д.

Программирование РВ Конструкции класса Regex (System. Text. Regular. Expressions): Символ Интерпретация Escape-последовательности b При использовании его в квадратных скобках соответствует символу «←» (u 0008) t, r, n, a, f, v Табуляция (u 0009), возврат каретки (u 000 D), новая строка (u 000 A) и т. д. c. X Управляющий символ (например, c. C – это Ctrl+C, u 0003) e Escape (u 001 B) ooo Символ ASCII в восьмеричной системе xhh Символ ASCII в шестнадцатеричной системе uhhhh Символ Unicode Следующий символ не является специальным символом РВ. Этим символом нужно экранировать все специальные символы Пример (в примере приведен шаблон и строка поиска, в строке найденные совпадения подчеркнуты): @"rnw+" – "rn. Здесь имеютсяnдве строки".

Программирование РВ Подмножества символов. Любой символ, кроме конца строки (n) Любой символ из множества [^xxx] Любой символ, кроме символов из множества Любой символ из диапазона ] Вычитание одного множества или диапазона из другого p{name} Любой символ, заданный категорией Unicode с именем name P{name} Любой символ, кроме заданных категорией Unicode с именем name w Множество символов, используемых при задании идентификаторов W Множество символов, не используемых при задании идентификаторов s Пробелы S Все, кроме пробелов d Цифры D Не цифры Примеры: @". +" – "rn. Здесь имеютсяnдве строки"; @"+" – "0 xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" – "0 xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0 xabcfx"; @"p{Lu}" – "City Lights"; // Lu – прописные буквы @"P{Lu}" – "City"; @"p{Is. Cyrillic}" – "ха. OS"; // Is. Cyrillic – русские буквы

Программирование РВ Привязка ^, A В начале строки $, Z В конце строки или до символа «n» в конце строки z В конце строки G В том месте, где заканчивается предыдущее соответствие b Граница слова B Любая позиция не на границе слова Примеры: @"G(d)" – "(1)(3)(5)(9) "; // три соответствия (1), (2) и (3) @"bnS*ionb" – "nation donation"; @"Bendw*b" – "end sends endure lender".

Программирование РВ Операции (кванторы) *, *? Итерация +, +? Положительная итерация? , ? ? Ноль или одно соответствие {n}, {n}? Точно n соответствий {n, }, {n, }? По меньшей мере, n соответствий {n, m}, {n, m}? От n до m соответствий Примеры (первые кванторы – жадные, ищут как можно большее число элементов, вторые – ленивые, ищут как можно меньшее число элементов): @"d{3, }" – "888 -5555"; @"^d{3}" – "913 -913"; @"-d{3}$" – "913 -913"; @"5+? 5" – "888 -5555"; // три совпадения – 55, 55 и 55 @"5+5" – "888 -5555".

Программирование РВ Группирование () Группа, автоматически получающая номер (? :) Не сохранять группу (?) или (? "имя") При обнаружении соответствия создается именованная группа (?) или Удаление ранее определенной группы и (? "имя– имя") сохранение в новой группе подстроки между ранее определенной группой и новой группой (? imnsx:) Включает или выключает в группе любую из пяти (? –imnsx:) возможных опций: i – нечувствительность к регистру; s – одна строка (тогда «. » – это любой символ); m – многострочный режим («^» , «$» – начало и конец каждой строки); n – не захватывать неименованные группы; x – исключить не преобразованные в escapeпоследовательность пробелы из шаблона и включить комментарии после знака номера (#) (? =) Положительное утверждение просмотра вперед нулевой длины

Программирование РВ (? !) Отрицательное утверждение просмотра вперед нулевой длины (?) Невозвращаемая (жадная) часть выражения Примеры: @"(an)+" – "bananas annals"; @"an+" – "bananas annals"; // сравните, три совпадения – an, an и ann @"(? i: an)+" – "ba. NAnas annals"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?

Src="https://сайт/presentation/-112203859_437213351/image-24.jpg" alt="Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";

Программирование РВ Подстановки $число Замещается часть строки, соответствующая группе с указанным номером ${имя} Замещается часть строки, соответствующая группе с указанным именем $$ Подставляется $ $& Замещение копией полного соответствия $` Замещение текста входной строки до соответствия $" Замещение текста входной строки после соответствия $+ Замещение последней захваченной группы $_ Замещение всей строки Комментарии (? #) Встроенный комментарий # Комментарий до конца строки

Программирование РВ Результаты работы Regex: Regex Matches() Match. Collection Match Groups() Group. Collection Group Captures() Capture. Collection Captures()

Программирование РВ Пример на языке C++ CLI (Visual C++/CLR/Консольное приложение CLR): int main() { Regex ^r = gcnew Regex(L"((\d)+)+"); Match ^m = r->Match(L"123 456"); int match. Count = 0; while (m->Success) { Console: : Write. Line(L"Соответствие {0}", ++match. Count); for (int i = 1; i Groups->Count; i++) { Group ^g = m->Groups[i]; Console: : Write. Line(L" Группа {0} = "{1}"", i, g->Value); for (int j = 0; j Captures->Count; j++) { Capture ^c = g->Captures[j]; Console: : Write. Line(L" Захват {0} = "{1}", позиция = {2}, длина = {3}", j, c, c->Index, c->Length); } } m = m->Next. Match(); } return 0; } System: : Text: : Regular. Expressions

Включение действий и поиск ошибок Ограничение количества значащих цифр в числе: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = d s + e = s? = (+|-)? pd* + e = (pd*)? = (. d*)? @"(+|-)? (. d+|d+(. d*)?)" или @"^(+|-)? (. d+|d+(. d*)?)$" Regex r = new Regex(@"^(+|-)? (. (? "digit"d)+|(? "digit"d)+(. (? "digit"d)*)?)$"); Match m = r. Match("+1. 23456789"); if (m. Success) { Group g = m. Groups["digit"]; if (g. Captures. Count

Включение действий и поиск ошибок Определение позиции ошибки: Regex r = new Regex(@"(+|-)? (. (? "digit"d)+|(? "digit"d)+(. (? "digit"d)*)?)"); string str = "+1. 2345!678"; Match m = r. Match(str); if (m. Success) { Group g = m. Groups["digit"]; if (g. Captures. Count 0) Console. Write. Line("Ошибка в позиции 1: неожиданный символ "{0}"", str); else if (m. Length

Включение действий и поиск ошибок Определение позиции ошибки: 1. первая позиция входной цепочки (1), если первое соответствие не начинается с позиции Index = 0; 2. позиция, следующая за последним соответствием (match. Length + 1), если она не совпадает с последней позицией входной цепочки; 3. позиция первого разрыва между соответствиями (match[i]. Index + match[i]. Length + 1), если символ, следующий за предыдущим соответствием, не является первым символом следующего соответствия.

Index) break; index = m[i]. Index + m[i]. Length; } Console. Write. Line("Ошибка в позиции {0} "{1}"", index + 1, str); } «abc. xyz. pqr» – правильно; «+abc. xyz. pqr» – ошибка в позиции 1 («+»); «abc. xyz. pqr!» – ошибка в позиции 12 («!»); «abc. xyz!. pqr» – ошибка в позиции 8 («!»).

Включение действий и поиск ошибок Но! «abc. xyz. +pqr» – ошибка в позиции 8 («. »). Новый вариант шаблона: @"w+(. w+)*(. (? !$))? " Проверка: «abc. xyz. +pqr» – ошибка в позиции 9 («+»); «abc. xyz. pqr. » – ошибка в позиции 12 («. »).

Сбалансированные определения: «(? "x")» добавляет в коллекцию с именем «x» один элемент; «(? "-x")» убирает из коллекции «x» один элемент; «(? (x)(? !))» проверяет, что в коллекции «x» не осталось элементов. Язык L, описывающий вложенные операторы языка Pascal «begin end; »: @"^s*((? "begins+)+(? "-begin"ends*; s*)+)*(? (begin)(? !))$".

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

Команда grep операционной системы Unix или аналогичные команды для поиска цепочек, которые можно встретить в Web-броузерах или системах форматирования текста. В таких системах РВ используются для описания шаблонов, которые пользователь ищет в файле. Различные поисковые системы преобразуют РВ либо в детерминированный конечный автомат (ДКА), либо недетерминированный конечный автомат (НКА) и применяют этот автомат к файлу, в котором производится поиск.
Генераторы лексических анализаторов. Лексические анализаторы являются компонентом компилятора, они разбивают исходную программу на логические единицы (лексемы), которые могут состоять из одного или нескольких символов и имеют определенный смысл. Генератор лексических анализаторов получает формальные описания лексем, являющиеся по существу РВ, и создает ДКА, который распознает, какая из лексем появляется на его входе.
РВ в языках программирования.