🗊Презентация Регулярные выражения

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

Основные определения Регулярные выражения в алфавите Σ и регулярные множества, которые они обозначают, определяются рекурсивно следующим образом: 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, aa, aaa, …}, т.е. x* = e + x + xx + xxx + …

Связь РВ и РМ Итерация конкатенации и объединения: (xy)* = e + xy + xyxy + xyxyxy + … (x + y)* = e + (x + y) + (x + y)(x + y) + (x + y)(x + y)(x + y) + … = = e + x + 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, yy, yyy, yyyy, …}, (x + y)*  {e, x, y, xx, xy, yx, yy, xxx, …}, (xy)*  {e, xy, xyxy, …}, xy*  {x, xy, xyy, xyyy, …}. Новые леммы: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; и т.д.

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

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

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

Преобразование ДКА в РВ Пример: для числа с фиксированной точкой получим систему q0 =  + q0 + sq1 + pq2 + dq3 + q4 q1 =  + q0 + q1 + pq2 + dq3 + q4 q2 =  + q0 + q1 + q2 + q3 + dq4 q3 = e + q0 + q1 + q2 + dq3 + pq4 q4 = e + q0 + q1 + q2 + q3 + dq4 Здесь: s – знак числа, s = '+' + '–'; p – десятичная точка, p = '.'; d – цифры, d = '0' + '1' + … + '9'.

Преобразование ДКА в РВ Решение: q0 = *(sq1 + pq2 + dq3 + q4 + ) = sq1 + pq2 + dq3  q1 =  + q0 + q1 + pq2 + dq3 + q4 = pq2 + dq3, q2 =  + q0 + q1 + q2 + q3 + dq4 = dq4, q3 = e + q0 + q1 + q2 + dq3 + pq4 = dq3 + pq4 + e, q4 = e + q0 + q1 + q2 + q3 + dq4 = dq4 + e. Из третьего уравнения: q3 = dq3 + pq4 + e = d*(pq4 + e). Из четвертого уравнения: q4 = dq4 + e = d*e = d*.

Преобразование ДКА в РВ Обратный ход: q3 = d*(pq4 + e) = d*(pd* + e), q2 = dq4 = dd*, q1 = pq2 + dq3 = pdd* + dd*(pd* + e), q0 = sq1 + pq2 + dq3 = 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* + e)) = (s + e)(pd+ + d+pd* + d+)

Преобразование ДКА в РВ Сопоставление графа функции переходов ДКА основным операциям с регулярными выражениями:

Преобразование ДКА в РВ Более сложные комбинации операций:

Преобразование ДКА в РВ Для РВ (s + e)(pd+ + d+(pd* + e)):

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

Программирование РВ Конструкции класса Regex (System.Text.RegularExpressions):

Программирование РВ

Программирование РВ

Программирование РВ

Программирование РВ

Программирование РВ

Программирование РВ

Программирование РВ

Программирование РВ Результаты работы Regex:

Программирование РВ Пример на языке C#:

Программирование РВ Пример на языке C++ CLI (Visual C++/CLR/Консольное приложение CLR): System::Text::RegularExpressions

Включение действий и поиск ошибок Ограничение количества значащих цифр в числе: (s + e)(pd+ + d+(pd* + e)) s = \+|- p = \. d = \d s + e = s? = (\+|-)? pd* + e = (pd*)? = (\.\d*)? @"(\+|-)?(\.\d+|\d+(\.\d*)?)" или @"^(\+|-)?(\.\d+|\d+(\.\d*)?)$"

Включение действий и поиск ошибок Определение позиции ошибки: «+1.2345!678» – ошибка в позиции 8; «!1.2345678» – ошибка в позиции 1

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

Включение действий и поиск ошибок «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*((?'begin'begin\s+)+(?'-begin'end\s*;\s*)+)*(?(begin)(?!))$".