Изменения
Нет описания правки
'''function''' match(regexp: '''String''', text: '''String'''): '''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)[1:])
'''return''' ''true''
i++
'''function''' matchHere(regexp: '''String''', text: '''String'''): '''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''
'''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++
Рассмотрим возможные случаи:
# Если в ходе рекурсии регулярное выражение осталось пустым <tex>\mathrm{(regexp[0] == \backslash0)}</tex>, то текст допускается этим регулярным выражением.# Если регулярное выражение имеет вид <tex>c*</tex>, то вызывается функция mathchStar, которая пытается сопоставить повторение символа <tex>c</tex>, начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в '''grep'''<ref>[httpshttp://ru.wikipedia.org/wiki/Grep '''grep''']</ref>, где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
# Если регулярное выражение это <tex>\mathdollar</tex>, то оно допускает этот текст тогда и только тогда, когда текст закончился.
# Если первый символ текста совпал с первым символом регулярного выражения, то нужно проверить совпадают ли следующий символ регулярного выражения со следующим символом текста, сделав рекурсивный вызов <tex>\mathrm{matchHere}</tex>.
'''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--
== Источники информации ==
* [http://www.cs.princeton.edu/courses/archive/spr10/cos333/beautiful.html A Regular Expression Matcher]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
