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