Разработка компиляторов
Использование регулярных выражений .NET
Для решения некоторых локальных задач лексического анализа удобно использовать механизм регулярных выражений, предоставляемый .NET (см. классы Regex, Match в пространстве имен System.Text.RegularExpressions).
Класс Regex реализует максимальный по функциональности механизм регулярных выражений. Этот механизм представляет собой недетерминированный поиск регулярных выражений в строке, основанный на "жадном" алгоритме с возвратами (аналогичные механизмы используются в Perl и Python). При таком подходе входная строка в определенном порядке проверяется на наличие любого варианта заданного регулярного выражения и в качестве результата принимается первое же совпадение. У такого подхода есть некоторые недостатки. Во-первых, в связи с тем, что механизм подразумевает возвраты, теоретически мы можем побывать в одном и том же состоянии многократно; таким образом, в худшем случае алгоритм может отработать за экспоненциальное время. Во-вторых, так как алгоритм останавливается на первой же найденной подходящей подстроке, этот алгоритм потенциально может не найти более длинные совпадения с данным регулярным выражением.
Традиционные детерминированные алгоритмы поиска регулярных выражений в строке, реализованные в Lex и awk, лишены таких недостатков. Тем не менее, на практике недетерминированные алгоритмы вполне удовлетворительны, так как среднее время их работы можно сделать линейным или полиномиальным путем использования простых вариантов или отсечения излишних возвратов, а выразительность недетерминированных алгоритмов значительно выше засчет возможности ссылок на разобранные группы, заглядывания вперед и назад, поиска подвыражений и т.п.
