Изменения

Если требуется сопоставить простое регулярное выражение с текстом, то проще использовать текущий Данный алгоритм, чем использовать работает быстрее [[Недетерминированные конечные автоматы| недетерминированный конечный автоматнедетерминированного конечного автомата]], построенный построенного по [[Теорема Клини (совпадение классов автоматных и регулярных языков)| теореме Клини]], так как он прост в написаниино только для регулярных выражений, требует меньше памяти и на простых регулярных выражениях работает не сильно хуже.  Введем обозначениясостоящих из символов:

:<tex>\mathdollar$</tex> {{---}} символ конца текста,

Данный алгоритм можно использовать Например, для регулярных выражений вида: <tex>\wedge? (c | mathtt{http://\ldotp | c^* | wiki\ldotp^*)^* \mathdollar?com}</tex>, очевидно, проще написать простой сопоставитель, чем строить НКА.

'''if''' matchHere(regexp, text[1i:])

Логика функции <tex>\mathrm{match}</tex> проста. Если <tex>\wedge</tex> {{---}} первый символ регулярного выражения, то любое возможное вхождение должно начинаться в начале текста. Т.е. То есть если <tex>\wedge</tex><tex>abc</tex> {{---}} регулярное выражение, то <tex>abc</tex> должно входить в текст только с первой позиции текста, а не где-то в середине текста. Это проверяется путем сопоставления остатка регулярного выражения с текстом, начиная с первой позиции и нигде более.

В противном случае регулярное выражение может входить в текст в любой позиции. Это проверяется путем сопоставления регулярного выражения во всех позициях текста. Если регулярное выражение входит более одного раза в текст, то только самое левое вхождение будет распознано. Т.е. То есть если <tex>abc</tex> {{---}} регулярное выражение, то для него найдется самое левое вхождение в текст.

# Если в ходе рекурсии регулярное выражение осталось пустым <tex>\mathrm{(regexp[0] == \backslash0)},\,</tex>, то текст допускается этим регулярным выражением.# Если регулярное выражение имеет вид <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>c</tex>. Назовем ее <tex>sS</tex>. # Сопоставим часть текста без <tex>sS</tex> с остатком регулярного выражения.# Если части совпали, то текст допускается этим регулярным выражением. Иначе, если <tex>sS</tex> пусто, то текст не допускается этим регулярным выражением, иначе убираем один символ из <tex>sS</tex> и повторяем шаг <tex>2</tex>.