Изменения
Нет описания правки
==Алгоритм==
Если требуется сопоставить простое регулярное выражение с текстом, то проще использовать текущий алгоритм, чем использовать [[Недетерминированные конечные автоматы| недетерминированный конечный автомат]], построенный по [[Теорема Клини (совпадение классов автоматных и регулярных языков)| теореме Клини]], так как он прост в написании, требует меньше памяти и на простых регулярных выражениях работает не сильно хуже.
Введем обозначения:
:<tex>c</tex> {{---}} один любой буквенный символ
:<tex>\mathdollar</tex> {{---}} символ конца текста
:<tex>*</tex> {{---}} предыдущий символ встречается ноль или более раз
Данный алгоритм можно использовать для регулярных выражений вида: <tex>\wedge? (c | \ldotp | c^* | \ldotp^*)^* \mathdollar?</tex>
=== Псевдокод ===
<font color=darkgreen>// поиск вхождения регулярного выражения в любом месте текста</font>
'''function''' match(regexp: '''stringString''', text: '''stringString'''): '''boolean'''
'''if''' regexp[0] == '^'
'''return''' matchHere(regexp.drop(1), text) <font color=darkgreen>// drop(n) возвращает строку без первых n элементов</font>
i++
'''return''' ''false''
<font color=darkgreen>// поиск вхождения регулярного выражения в начале текста</font>
'''function''' matchHere(regexp: '''stringString''', text: '''stringString'''): '''boolean'''
'''if''' regexp[0] == '\0'
'''return''' ''true''
'''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 == '.')
i++
'''return''' ''false''
Рассмотрим возможные случаи:
# Если первый символ текста совпал с первым символом регулярного выражения, то нужно проверить совпадают ли следующий символ регулярного выражения со следующим символом текста, сделав рекурсивный вызов <tex>\mathrm{matchHere}</tex>.
# Если все предыдущие попытки найти совпадения провалились, то никакая подстрока из текста не допускается регулярным выражением.
Данный алгоритм прост и лаконичен, но у него есть недостаток. Для регулярного выражения содержащего несколько <tex>.*</tex> подряд этот алгоритм может работать очень медленно. Рассмотрим время работы '''grep'а''' (наш алгоритм схож со стандартным '''grep'ом'''). Например команда: "<tex>grep</tex> <tex>a.*a.*a.*a.a</tex>" потребует 20 секунд, чтобы обработать текстовой файл размером 4MB на обычной машине. В то же время алгоритм, который конвертирует [[Недетерминированные конечные автоматы|недетерминированный конечный автомат]] в [[Детерминированные конечные автоматы|детерминированный конечный автомат]] (например, '''egrep'''<ref>[https://ru.wikipedia.org/wiki/Grep egrep]</ref>), потребует менее одной десятой доли секунды на обработку тех же данных.
=== Псевдокод ===
'''function''' matchStar(c : '''char''', regexp: '''stringString''', text: '''stringString'''): '''boolean'''
'''int''' i
'''for''' (i = 0; text[i] != '\0' '''and''' (text[i] == c '''or''' c == '.'); i++)
