Действительно ли .NET использует NFA для механизма регулярных выражений?

Question

Статья Details of Regular Expression Behavior из MSDN говорит, что .NET разработчики решили использовать для регулярных выражений традиционных NFA двигателя, потому что это быстрее, чем POSIX NFA, но это мне не ясно, почему эта модель работает экспоненциально медленно, то ?

var regex = new Regex("(a|aa)*b"); 
var b = regex.IsMatch("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac"); 

Это простое сопоставление с образцом занять более 30 минут, чтобы выполнить. Но если .NET использует традиционный NFA, можно смоделировать его и найти совпадение в O (M * N) время в худшем случае, где M - длина рисунка, а N - длина текста, что, безусловно, неверно в этом дело.

Статья также объясняет, что откат является причиной медленного исполнения, но я до сих пор есть некоторые вопросы, которые не могут найти ответы

1. Что возвратов? это только с использованием уже подобранного шаблона, подобного этому (a|b)c/1?
2. Поддерживает ли традиционный NFA поддержки, если нет какой-либо модификации?
3. Если NFA поддерживает его, но требуется более медленный алгоритм для моделирования, почему .NET не может проверить, существует ли обратное отслеживание в шаблоне, и использовать один алгоритм и использовать другой, если это не так?

Answer 1

Вы можете скомпилировать регулярное выражение в NFA или DFA, хотя DFA, рассчитанный из NFA, может быть непрактично большим. Вы можете сопоставить NFA с обратным трассированием или без него, хотя схемы, которые работают без обратного отслеживания, обычно ставят больше ограничений на язык регулярных выражений и по которым встречаются совпадения, когда есть много возможных совпадений.

Ваш пример медленный, потому что помощник должен очень часто решать, следует ли совпадать с a или aa, и попробовать ли сопоставить последний b. Backtracking работает как работа с рекурсивной функцией, которая на каждом шаге делает рекурсивные вызовы для себя для каждой возможности - рекурсивно соответствует с a, а если это не рекурсивно совпадает с aa, и если это не рекурсивно совпадает с b.

Microsoft, похоже, говорит, что их обратная трассировка быстрее, чем POSIX, потому что POSIX backtracking организует рекурсивный поиск, который продолжается до тех пор, пока не будет уверен, что он нашел максимально возможное совпадение. Версия Microsoft по-прежнему отстает, но у нее нет дополнительных проверок, которые выполняются до тех пор, пока не будет гарантирована, что они найдут максимально возможное совпадение. Пример: http://msdn.microsoft.com/en-us/library/dsy130b4%28v=vs.110%29.aspx.

Регуляторы регулярных выражений без обратного отсчета могут работать, принимая входной символ за один раз и отслеживая, какие состояния в NFA живут в это время - таких состояний может быть много. Трудно сделать эту работу с обратными ссылками, потому что тогда состояние NFA не может быть описано, просто говоря, является ли состояние живым или нет.