Изменения

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

'''function''' match(regexp: '''char'''*, text: '''char'''*): '''boolean''' <font color=darkgreen>// поиск вхождения регулярного выражения в любом месте текста</font> '''if''' (regexp[0] == '^') '''return''' matchHere(regexp + 1, text) '''do''' '''if''' (matchHere(regexp, text)) '''return''' ''true'' '''while''' (*text++ != '\0') '''return''' ''false'' '''function''' matchHerematch(regexp: '''charString'''*, text: '''charString'''*): '''boolean''' <font color=darkgreen>/ поиск вхождения регулярного выражения в начале текста</font> '''if''' (regexp[0] == '\0^') '''return''' ''true'' '''if''' matchHere(regexp[1] == '*') '''return''' matchStar(regexp[0:], regexp + 2, text) '''if''' ( <font color=darkgreen>// regexp[0n:] == '$' '''and''' возвращает regexp[без первых n элементов за O(1] == '\0') '''return''' *text == '\0';</font> '''ifint''' (*text!i ='\0' '''and''' (regexp[0] == '.' '''or''' regexp[0] == *text)) '''return''' matchHere(regexp + 1, text + 1) '''return''' ''false'' '''function''' matchStar(c : '''char''', regexp: '''char'''*, text: '''char'''*): '''booleanwhile''' i <font color=darkgreentex>/ сопоставление с регулярным выражением вида: c*\leqslant</fonttex> '''do'''text.length '''if''' (matchHere(regexp, text)[i:])

'''while''' (*text != '\0' '''and''' (*text i++ == c '''or''' c == '.')) <font color=darkgreen>/Цикл '''do-while''' используется вместо '''while''', так как * допускает пустую строку</font>

Данный псевдокод использует указатели Функция <tex>\mathrm{match(regexp, text)}</tex> проверяет есть ли вхождение регулярного выражения в любом месте в пределах текста. Если существует более одного вхождения, то найдется самое левое и арифметические операции над ними из языка Cсамое короткое.

Функция Логика функции <tex>\mathrm{match(regexp, text)}</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> должно входить для него найдется самое левое вхождение в текст только с первой позиции текста, а не где-то в середине текста. Это проверяется путем сопоставления остатка регулярного выражения с текстом, начиная с первой позиции и нигде более.

В противном случае регулярное выражение может входить в текст в любой позиции. Это проверяется путем сопоставления <font color=darkgreen>// поиск вхождения регулярного выражения во всех позициях в начале текста. Если регулярное выражение входит более одного раза в текст</font> '''function''' matchHere(regexp: '''String''', то только самое левое вхождение будет распознано. Т.е. если text: '''String'''): '''boolean''' '''if''' regexp[0] == '\0' '''return''' ''true'' '''if''' regexp[1] == '*' <texfont color=darkgreen>abc// не будет выхода за пределы строки, так как в конце regexp и text всегда есть символ '\0'</texfont> {{---}} регулярное выражение '''return''' matchStar(regexp[0], regexp[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[1:], text[1:]) '''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>c</tex>. Назовем ее <tex>sS</tex>. # Сопоставим часть текста без <tex>sS</tex> с остатком регулярного выражения.# Если части совпали, то текст допускается этим регулярным выражением. Иначе, если <tex>sS</tex> пусто, то текст не допускается этим регулярным выражением, иначе убираем один символ из <tex>sS</tex> и повторяем шаг <tex>2</tex>.

'''function''' matchStar(c : '''char''', regexp: '''charString'''*, text: '''charString'''*): '''boolean''' '''charint''' *ti '''for''' (t i = 0; text; *t [i] != '\0' '''and''' (*t text[i] == c '''or''' c == '.'); ti++) '''dowhile'''i <tex>\geqslant</tex> 0 '''if''' (matchHere(regexp, text)[i:])