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

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:11:09Z

rollbackEdits.php mass rollback

185.220.100.252 в 06:05, 1 сентября 2022

2022-09-01T06:05:31Z

94.19.239.249: /* Модификации */

2018-03-14T06:22:50Z

‎Модификации

Ponomarev: /* Алгоритм */

2018-03-10T18:15:14Z

‎Алгоритм

Ponomarev: /* Модификации */

2018-03-10T18:07:13Z

‎Модификации

Shersh: /* Алгоритм */

2016-12-05T19:40:22Z

‎Алгоритм

194.85.161.2 в 19:35, 5 декабря 2016

2016-12-05T19:35:37Z

194.85.161.2 в 18:52, 5 декабря 2016

2016-12-05T18:52:30Z

194.85.161.2: /* Алгоритм */

2016-12-05T16:13:24Z

‎Алгоритм

194.85.161.2 в 20:45, 4 декабря 2016

2016-12-04T20:45:59Z

← Предыдущая		Версия 16:11, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Задача		{{Задача
	\|definition =		\|definition =

← Предыдущая		Версия 06:05, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Задача		{{Задача
	\|definition =		\|definition =

@@ Строка 66: / Строка 66: @@
 # Найдем максимальную последовательность подряд идущих символов <tex>c</tex>. Назовем ее <tex>S</tex>.
 # Сопоставим часть текста без <tex>S</tex> с остатком регулярного выражения.
-# Если части совпали, то текст допускается этим регулярным выражением. Иначе, если <tex>S</tex> пусто, то текст не допускается этим регулярным выражением, иначе убираем один символ из <tex>S</tex> и повторяем шаг 2.
+# Если части совпали, то текст допускается этим регулярным выражением. Иначе, если <tex>S</tex> пусто, то текст не допускается этим регулярным выражением, иначе убираем один символ из <tex>S</tex> и повторяем шаг <tex>2</tex>.
 === Псевдокод ===

@@ Строка 9: / Строка 9: @@
 :<tex>\ldotp</tex> {{---}} один любой символ,
 :<tex>\wedge</tex> {{---}} символ начала текста,
-:<tex>\mathdollar</tex> {{---}} символ конца текста,
+:<tex>$</tex> {{---}} символ конца текста,
 :<tex>*</tex> {{---}} предыдущий символ встречается ноль или более раз.
@@ Строка 28: / Строка 28: @@
 Функция <tex>\mathrm{match(regexp, text)}</tex> проверяет есть ли вхождение регулярного выражения в любом месте в пределах текста. Если существует более одного вхождения, то найдется самое левое и самое короткое.
-Логика функции <tex>\mathrm{match}</tex> проста. Если <tex>\wedge</tex> {{---}} первый символ регулярного выражения, то любое возможное вхождение должно начинаться в начале текста. Т.е. если <tex>\wedge</tex><tex>abc</tex> {{---}} регулярное выражение, то <tex>abc</tex> должно входить в текст только с первой позиции текста, а не где-то в середине текста. Это проверяется путем сопоставления остатка регулярного выражения с текстом, начиная с первой позиции и нигде более.
+Логика функции <tex>\mathrm{match}</tex> проста. Если <tex>\wedge</tex> {{---}} первый символ регулярного выражения, то любое возможное вхождение должно начинаться в начале текста. То есть если <tex>\wedge</tex><tex>abc</tex> {{---}} регулярное выражение, то <tex>abc</tex> должно входить в текст только с первой позиции текста, а не где-то в середине текста. Это проверяется путем сопоставления остатка регулярного выражения с текстом, начиная с первой позиции и нигде более.
-В противном случае регулярное выражение может входить в текст в любой позиции. Это проверяется путем сопоставления регулярного выражения во всех позициях текста. Если регулярное выражение входит более одного раза в текст, то только самое левое вхождение будет распознано. Т.е. если <tex>abc</tex> {{---}} регулярное выражение, то для него найдется самое левое вхождение в текст.
+В противном случае регулярное выражение может входить в текст в любой позиции. Это проверяется путем сопоставления регулярного выражения во всех позициях текста. Если регулярное выражение входит более одного раза в текст, то только самое левое вхождение будет распознано. То есть если <tex>abc</tex> {{---}} регулярное выражение, то для него найдется самое левое вхождение в текст.
   <font color=darkgreen>// поиск вхождения регулярного выражения в начале текста</font>
@@ Строка 56: / Строка 56: @@
 Рассмотрим возможные случаи:
-# Если в ходе рекурсии регулярное выражение осталось пустым <tex>\mathrm{(regexp[0] == \backslash0)}</tex>, то текст допускается этим регулярным выражением.
+# Если в ходе рекурсии регулярное выражение осталось пустым <tex>\mathrm{(regexp[0] == \backslash0)},\,</tex> то текст допускается этим регулярным выражением.
-# Если регулярное выражение имеет вид <tex>c*</tex>, то вызывается функция mathchStar, которая пытается сопоставить повторение символа <tex>c</tex>, начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в '''grep'''<ref>[http://ru.wikipedia.org/wiki/Grep Wikipedia {{---}} grep]</ref>, где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
+# Если регулярное выражение имеет вид <tex>c*</tex>, то вызывается функция <tex>\mathrm{mathchStar},\,</tex> которая пытается сопоставить повторение символа <tex>c</tex>, начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в '''grep'''<ref>[http://ru.wikipedia.org/wiki/Grep Wikipedia {{---}} grep]</ref>, где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
-# Если регулярное выражение это <tex>\mathdollar</tex>, то оно допускает этот текст тогда и только тогда, когда текст закончился.
+# Если регулярное выражение это <tex>$</tex>, то оно допускает этот текст тогда и только тогда, когда текст закончился.
 # Если первый символ текста совпал с первым символом регулярного выражения, то нужно проверить совпадают ли следующий символ регулярного выражения со следующим символом текста, сделав рекурсивный вызов <tex>\mathrm{matchHere}</tex>.
 # Если все предыдущие попытки найти совпадения провалились, то никакая подстрока из текста не допускается регулярным выражением.

@@ Строка 64: / Строка 64: @@
 ===Модификации===
 Немного изменим функцию <tex>\mathrm{matchStar}</tex> для поиск самого левого и самого длинного вхождения <tex>c*</tex>:
-# Найдем максимальную последовательность подряд идущих символов <tex>c</tex>. Назовем ее <tex>s</tex>.
+# Найдем максимальную последовательность подряд идущих символов <tex>c</tex>. Назовем ее <tex>S</tex>.
-# Сопоставим часть текста без <tex>s</tex> с остатком регулярного выражения.
+# Сопоставим часть текста без <tex>S</tex> с остатком регулярного выражения.
-# Если части совпали, то текст допускается этим регулярным выражением. Иначе, если <tex>s</tex> пусто, то текст не допускается этим регулярным выражением, иначе убираем один символ из <tex>s</tex> и повторяем шаг 2.
+# Если части совпали, то текст допускается этим регулярным выражением. Иначе, если <tex>S</tex> пусто, то текст не допускается этим регулярным выражением, иначе убираем один символ из <tex>S</tex> и повторяем шаг 2.
 === Псевдокод ===

@@ Строка 12: / Строка 12: @@
 :<tex>*</tex> {{---}} предыдущий символ встречается ноль или более раз.
-Например, для <tex>http://\ldotp*</tex>, очевидно, проще написать простой сопоставитель, чем строить НКА.
+Например, для <tex>\mathtt{http://\ldotp*wiki\ldotp*com}</tex>, очевидно, проще написать простой сопоставитель, чем строить НКА.
 === Псевдокод ===

@@ Строка 12: / Строка 12: @@
 :<tex>*</tex> {{---}} предыдущий символ встречается ноль или более раз.
-Например, для <tex>\wedge ab*\ldotp*</tex>, очевидно, проще написать простой сопоставитель чем строить НКА.
+Например, для <tex>http://\ldotp*</tex>, очевидно, проще написать простой сопоставитель, чем строить НКА.
 === Псевдокод ===
@@ Строка 21: / Строка 21: @@
       '''int''' i = 0
       '''while''' i <tex>\leqslant</tex> text.length
-          '''if''' matchHere(regexp, text[1:])
+          '''if''' matchHere(regexp, text[i:])
               '''return''' ''true''
           i++
@@ Строка 57: / Строка 57: @@
 Рассмотрим возможные случаи:
 # Если в ходе рекурсии регулярное выражение осталось пустым <tex>\mathrm{(regexp[0] == \backslash0)}</tex>, то текст допускается этим регулярным выражением.
-# Если регулярное выражение имеет вид <tex>c*</tex>, то вызывается функция mathchStar, которая пытается сопоставить повторение символа <tex>c</tex>, начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в [http://ru.wikipedia.org/wiki/Grep '''grep'''], где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
+# Если регулярное выражение имеет вид <tex>c*</tex>, то вызывается функция mathchStar, которая пытается сопоставить повторение символа <tex>c</tex>, начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в '''grep'''<ref>[http://ru.wikipedia.org/wiki/Grep Wikipedia {{---}} grep]</ref>, где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
 # Если регулярное выражение это <tex>\mathdollar</tex>, то оно допускает этот текст тогда и только тогда, когда текст закончился.
 # Если первый символ текста совпал с первым символом регулярного выражения, то нужно проверить совпадают ли следующий символ регулярного выражения со следующим символом текста, сделав рекурсивный вызов <tex>\mathrm{matchHere}</tex>.
@@ Строка 80: / Строка 80: @@
 ==См. также==
 * [[Регулярные языки: два определения и их эквивалентность]]
 == Источники информации ==

← Предыдущая		Версия 18:52, 5 декабря 2016
Строка 86:		Строка 86:
	[[Категория: Теория формальных языков]]		[[Категория: Теория формальных языков]]
	[[Категория: Автоматы и регулярные языки]]		[[Категория: Автоматы и регулярные языки]]
		+	[[Категория: Регулярные языки и ДКА]]

@@ Строка 5: / Строка 5: @@
 ==Алгоритм==
-Если требуется сопоставить простое регулярное выражение с текстом, то проще использовать текущий алгоритм, чем использовать [[Недетерминированные конечные автоматы| недетерминированный конечный автомат]], построенный по [[Теорема Клини (совпадение классов автоматных и регулярных языков)| теореме Клини]], так как он прост в написании, требует меньше памяти и на простых регулярных выражениях работает не сильно хуже.
+Данный алгоритм работает быстрее [[Недетерминированные конечные автоматы|недетерминированного конечного автомата]], построенного по [[Теорема Клини (совпадение классов автоматных и регулярных языков)| теореме Клини]], но только для регулярных выражений, состоящих из символов:
 :<tex>c</tex> {{---}} один любой буквенный символ,
 :<tex>\ldotp</tex> {{---}} один любой символ,
@@ Строка 14: / Строка 12: @@
 :<tex>*</tex> {{---}} предыдущий символ встречается ноль или более раз.
-Данный алгоритм можно использовать для регулярных выражений вида: <tex>\wedge? (c | \ldotp | c^* | \ldotp^*)^* \mathdollar?</tex>
+Например, для <tex>\wedge ab*\ldotp*</tex>, очевидно, проще написать простой сопоставитель чем строить НКА.
 === Псевдокод ===

@@ Строка 20: / Строка 20: @@
   '''function''' match(regexp: '''String''', text: '''String'''): '''boolean'''
       '''if''' regexp[0] == '^'
-          '''return''' matchHere(regexp.drop(1), text)  <font color=darkgreen>// drop(n) возвращает строку без первых n элементов</font>
+          '''return''' matchHere(regexp[1:], text)  <font color=darkgreen>// regexp[n:] возвращает regexp без первых n элементов за O(1)</font>
       '''int''' i = 0
       '''while''' i <tex>\leqslant</tex> text.length
-          '''if''' matchHere(regexp, text.drop(i))
+          '''if''' matchHere(regexp, text[1:])
               '''return''' ''true''
           i++
@@ Строка 37: / Строка 37: @@
   '''function''' matchHere(regexp: '''String''', text: '''String'''): '''boolean'''
       '''if''' regexp[0] == '\0'
           '''return''' ''true''
-      '''if''' regexp[1] == '*'
+      '''if''' regexp[1] == '*'  <font color=darkgreen>// не будет выхода за пределы строки, так как в конце regexp и text всегда есть символ '\0'</font>
-          '''return''' matchStar(regexp[0], regexp.drop(2), text)
+          '''return''' matchStar(regexp[0], regexp[2:], text)
       '''if''' regexp[0] == '$' '''and''' regexp[1] == '\0'
-          '''return''' text == '\0';
+          '''return''' text == '\0'
       '''if''' text[0] != '\0' '''and''' (regexp[0] == '.' '''or''' regexp[0] == text[0])
-          '''return''' matchHere(regexp.drop(1), text.drop(1))
+          '''return''' matchHere(regexp[1:], text[1:])
       '''return''' ''false''
@@ Строка 52: / Строка 52: @@
       '''int''' i = 0
       '''while''' i <tex>\leqslant</tex> text.length '''and''' (text[i] == c '''or''' c == '.')
-          '''if''' matchHere(regexp, text.drop(i))
+          '''if''' matchHere(regexp, text[i:])
               '''return''' ''true''
           i++
@@ Строка 58: / Строка 58: @@
 Рассмотрим возможные случаи:
-# Если в ходе рекурсии регулярное выражение осталось пустым <tex>(regexp[0] == \backslash0)</tex>, то текст допускается этим регулярным выражением.
+# Если в ходе рекурсии регулярное выражение осталось пустым <tex>\mathrm{(regexp[0] == \backslash0)}</tex>, то текст допускается этим регулярным выражением.
-# Если регулярное выражение имеет вид <tex>c*</tex>, то вызывается функция mathchStar, которая пытается сопоставить повторение символа <tex>c</tex>, начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в '''grep'''<ref>[https://ru.wikipedia.org/wiki/Grep grep]</ref>, где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
+# Если регулярное выражение имеет вид <tex>c*</tex>, то вызывается функция mathchStar, которая пытается сопоставить повторение символа <tex>c</tex>, начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в [http://ru.wikipedia.org/wiki/Grep '''grep'''], где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
 # Если регулярное выражение это <tex>\mathdollar</tex>, то оно допускает этот текст тогда и только тогда, когда текст закончился.
 # Если первый символ текста совпал с первым символом регулярного выражения, то нужно проверить совпадают ли следующий символ регулярного выражения со следующим символом текста, сделав рекурсивный вызов <tex>\mathrm{matchHere}</tex>.
@@ Строка 75: / Строка 75: @@
       '''for''' (i = 0; text[i] != '\0' '''and''' (text[i] == c '''or''' c == '.'); i++)
       '''while''' i <tex>\geqslant</tex> 0
-          '''if''' matchHere(regexp, text.drop(i))
+          '''if''' matchHere(regexp, text[i:])
               '''return''' ''true''
           i--
@@ Строка 85: / Строка 85: @@
 == Источники информации ==
 * [http://www.cs.princeton.edu/courses/archive/spr10/cos333/beautiful.html A Regular Expression Matcher]
 [[Категория: Теория формальных языков]]
 [[Категория: Автоматы и регулярные языки]]