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

Август 24, 2022

Главная
Математика
Регулярные выражения

Содержание

2. Основные определения Регулярные выражения в алфавите Σ и регулярные множества, которые они обозначают, определяются рекурсивно следующим
3. Основные определения Расстановка приоритетов: * (итерация) – наивысший приоритет; конкатенация; + (объединение). Таким образом, 0 +
4. Основные определения Леммы: 1) α + β = β + α 2) ∅* = e 3)
5. Связь РВ и РМ РМ – языки, порождаемые РВ. Например: x = a+b, y = c+d,
6. Связь РВ и РМ Итерация конкатенации и объединения: (xy)* = e + xy + xyxy +
7. Связь РВ и РМ Примеры на приоритет: x + yz ⇔ {x, yz}, (x + y)z
8. Регулярные системы уравнений Уравнение с регулярными коэффициентами X = aX + b имеет решение (наименьшую неподвижную
9. Регулярные системы уравнений Алгоритм решения (метод Гаусса): Шаг 1. Положить i = 1. Шаг 2. Если
10. Преобразование ДКА в РВ Для ДКА M = (Q, Σ, δ, q0, F) составим систему с
11. Преобразование ДКА в РВ Пример: для числа с фиксированной точкой получим систему q0 = ∅ +
12. Преобразование ДКА в РВ Решение: q0 = ∅*(sq1 + pq2 + dq3 + ∅q4 + ∅)
13. Преобразование ДКА в РВ Обратный ход: q3 = d*(pq4 + e) = d*(pd* + e), q2
14. Преобразование ДКА в РВ Сопоставление графа функции переходов ДКА основным операциям с регулярными выражениями:
15. Преобразование ДКА в РВ Более сложные комбинации операций:
16. Преобразование ДКА в РВ Для РВ (s + e)(pd+ + d+(pd* + e)):
17. Программирование РВ Регулярные выражения: Встроены во многие языки программирования (PHP, JavaScript, …); Реализованы в виде подключаемых
18. Программирование РВ Конструкции класса Regex (System.Text.RegularExpressions):
19. Программирование РВ
20. Программирование РВ
21. Программирование РВ
22. Программирование РВ
23. Программирование РВ
24. Программирование РВ
25. Программирование РВ
26. Программирование РВ Результаты работы Regex:
27. Программирование РВ Пример на языке C#:
28. Программирование РВ Пример на языке C++ CLI (Visual C++/CLR/Консольное приложение CLR): System::Text::RegularExpressions
29. Включение действий и поиск ошибок Ограничение количества значащих цифр в числе: (s + e)(pd+ + d+(pd*
30. Включение действий и поиск ошибок Определение позиции ошибки: «+1.2345!678» – ошибка в позиции 8; «!1.2345678» –
31. Включение действий и поиск ошибок Определение позиции ошибки: 1. первая позиция входной цепочки (1), если первое
32. Включение действий и поиск ошибок «abc.xyz.pqr» – правильно; «+abc.xyz.pqr» – ошибка в позиции 1 («+»); «abc.xyz.pqr!»
33. Включение действий и поиск ошибок Но! «abc.xyz.+pqr» – ошибка в позиции 8 («.»). Новый вариант шаблона:
35. Скачать презентацию

Слайд 2

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

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

Слайд 3

Основные определения
Расстановка приоритетов:
* (итерация) – наивысший приоритет;
конкатенация;
+ (объединение).
Таким образом, 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.

Слайд 4

Основные определения
Леммы:
1) α + β = β + α
2) ∅* =

e
3) α + (β + γ) = (α + β) + γ
4) α(βγ) = (αβ)γ
5) α(β + γ) = αβ + αγ
6) (α + β)γ = αγ + βγ
7) αe = eα = α
8) α∅ = ∅α = ∅
9) α+α* = α*
10) (α*)* = α*
11) α+α = α
12) α+∅ = α

Слайд 5

Связь РВ и РМ
РМ – языки, порождаемые РВ. Например:
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 + …

Слайд 6

Связь РВ и РМ
Итерация конкатенации и объединения:
(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

Слайд 7

Связь РВ и РМ
Примеры на приоритет:
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;
и т.д.

Слайд 8

Регулярные системы уравнений
Уравнение с регулярными коэффициентами
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}.

Слайд 9

Регулярные системы уравнений
Алгоритм решения (метод Гаусса):
Шаг 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.

Слайд 10

Преобразование ДКА в РВ
Для ДКА M = (Q, Σ, δ, q0,

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

Слайд 11

Преобразование ДКА в РВ
Пример: для числа с фиксированной точкой получим систему
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'.

Слайд 12

Преобразование ДКА в РВ
Решение:
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*.

Слайд 13

Преобразование ДКА в РВ
Обратный ход:
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+)

Слайд 14

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

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

Слайд 15

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

Слайд 16

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

e)):

Слайд 17

Программирование РВ
Регулярные выражения:
Встроены во многие языки программирования (PHP, JavaScript, …);
Реализованы в

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

Слайд 18

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

Слайд 19

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

Слайд 20

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

Слайд 21

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

Слайд 22

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

Слайд 23

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

Слайд 24

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

Слайд 25

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

Слайд 26

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

Слайд 27

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

Слайд 28

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

Слайд 29

Включение действий и поиск ошибок
Ограничение количества значащих цифр в числе:
(s +

e)(pd+ + d+(pd* + e))
s = \+|-
p = \.
d = \d
s + e = s? = (\+|-)?
pd* + e = (pd*)? = (\.\d*)?
@"(\+|-)?(\.\d+|\d+(\.\d*)?)" или @"^(\+|-)?(\.\d+|\d+(\.\d*)?)$"

Слайд 30

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

8;
«!1.2345678» – ошибка в позиции 1

Слайд 31

Включение действий и поиск ошибок
Определение позиции ошибки:
1. первая позиция входной цепочки

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

Слайд 32

Включение действий и поиск ошибок
«abc.xyz.pqr» – правильно;
«+abc.xyz.pqr» – ошибка в позиции

1 («+»);
«abc.xyz.pqr!» – ошибка в позиции 12 («!»);
«abc.xyz!.pqr» – ошибка в позиции 8 («!»).

Слайд 33

Включение действий и поиск ошибок
Но! «abc.xyz.+pqr» – ошибка в позиции 8

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

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

Содержание

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

Основные определенияРасстановка приоритетов:* (итерация) – наивысший приоритет;конкатенация;+ (объединение).Таким образом, 0 +

Основные определенияЛеммы: 1) α + β = β + α 2) ∅* =

Связь РВ и РМРМ – языки, порождаемые РВ. Например:x = a+b,

Связь РВ и РМИтерация конкатенации и объединения:(xy)* = e + xy

Связь РВ и РМПримеры на приоритет:x + yz ⇔ {x, yz},(x

Регулярные системы уравненийУравнение с регулярными коэффициентамиX = aX + bимеет решение

Регулярные системы уравненийАлгоритм решения (метод Гаусса):Шаг 1. Положить i = 1.Шаг 2. Если i =

Преобразование ДКА в РВДля ДКА M = (Q, Σ, δ, q0,

Преобразование ДКА в РВПример: для числа с фиксированной точкой получим систему q0

Преобразование ДКА в РВРешение: q0 = ∅*(sq1 + pq2 + dq3 +

Преобразование ДКА в РВОбратный ход: q3 = d*(pq4 + e) = d*(pd*

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

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

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

Программирование РВРегулярные выражения:Встроены во многие языки программирования (PHP, JavaScript, …);Реализованы в

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

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

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

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

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

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

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

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

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

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

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

Включение действий и поиск ошибокОграничение количества значащих цифр в числе:(s +

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

Включение действий и поиск ошибокОпределение позиции ошибки:1. первая позиция входной цепочки

Включение действий и поиск ошибок«abc.xyz.pqr» – правильно;«+abc.xyz.pqr» – ошибка в позиции

Включение действий и поиск ошибокНо! «abc.xyz.+pqr» – ошибка в позиции 8

Похожие презентации

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

Основные определения
Расстановка приоритетов:
* (итерация) – наивысший приоритет;
конкатенация;
+ (объединение).
Таким образом, 0 +

Основные определения
Леммы:
1) α + β = β + α
2) ∅* =

Связь РВ и РМ
РМ – языки, порождаемые РВ. Например:
x = a+b,

Связь РВ и РМ
Итерация конкатенации и объединения:
(xy)* = e + xy

Связь РВ и РМ
Примеры на приоритет:
x + yz ⇔ {x, yz},
(x

Регулярные системы уравнений
Уравнение с регулярными коэффициентами
X = aX + b
имеет решение

Регулярные системы уравнений
Алгоритм решения (метод Гаусса):
Шаг 1. Положить i = 1.
Шаг 2. Если i =

Преобразование ДКА в РВ
Для ДКА M = (Q, Σ, δ, q0,

Преобразование ДКА в РВ
Пример: для числа с фиксированной точкой получим систему
q0

Преобразование ДКА в РВ
Решение:
q0 = ∅*(sq1 + pq2 + dq3 +

Преобразование ДКА в РВ
Обратный ход:
q3 = d(pq4 + e) = d(pd*

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

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

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

Программирование РВ
Регулярные выражения:
Встроены во многие языки программирования (PHP, JavaScript, …);
Реализованы в

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

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

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

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

Включение действий и поиск ошибок
Ограничение количества значащих цифр в числе:
(s +

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

Включение действий и поиск ошибок
Определение позиции ошибки:
1. первая позиция входной цепочки

Включение действий и поиск ошибок
«abc.xyz.pqr» – правильно;
«+abc.xyz.pqr» – ошибка в позиции

Включение действий и поиск ошибок
Но! «abc.xyz.+pqr» – ошибка в позиции 8