Изменения
Нет описания правки
:<tex>*</tex> {{---}} предыдущий символ встречается ноль или более раз.
Например, для <tex>\wedge ab*http://\ldotp*</tex>, очевидно, проще написать простой сопоставитель , чем строить НКА.
=== Псевдокод ===
'''int''' i = 0
'''while''' i <tex>\leqslant</tex> text.length
'''if''' matchHere(regexp, text[1i:])
'''return''' ''true''
i++
Рассмотрим возможные случаи:
# Если в ходе рекурсии регулярное выражение осталось пустым <tex>\mathrm{(regexp[0] == \backslash0)}</tex>, то текст допускается этим регулярным выражением.
# Если регулярное выражение имеет вид <tex>c*</tex>, то вызывается функция mathchStar, которая пытается сопоставить повторение символа <tex>c</tex>, начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в '''grep'''<ref>[http://ru.wikipedia.org/wiki/Grep '''Wikipedia {{---}} grep''']</ref>, где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
# Если регулярное выражение это <tex>\mathdollar</tex>, то оно допускает этот текст тогда и только тогда, когда текст закончился.
# Если первый символ текста совпал с первым символом регулярного выражения, то нужно проверить совпадают ли следующий символ регулярного выражения со следующим символом текста, сделав рекурсивный вызов <tex>\mathrm{matchHere}</tex>.
==См. также==
* [[Регулярные языки: два определения и их эквивалентность]]
==Примечания==
<references />
== Источники информации ==
