Как выяснить, использует ли реализация регулярного выражения DFA или NFA?

Question

Я сталкиваюсь с вопросом, базируется ли определенная реализация regex на DFA или NFA.

Каковы исходные точки для меня, чтобы понять это.Можно также спросить: Что я ищу?Каковы основные модели и / или характеристики?Хорошая и пояснительная ссылка или небольшие сравнения (даже если они не предназначены непосредственно для регулярных выражений) - это прекрасно.

Answer 1

Если это черный ящик, то дайте ему некоторую информацию и измерьте его временные характеристики с патологическим случаем, со ссылкой на графики в этом обсуждении реализаций регулярного выражения NFS против обратного отслеживания .(обратите внимание, что граф NFS - это микросекунды, а не секунды).

Кроме того, если это чистый NFA, то у него не будет некоторых нерегулярных функций, которые можно найти - это парсеры 'регулярных выражений', которые требуют обратного отслеживания.

В качестве альтернативы посмотрите документацию класса RxParser;документация, по-видимому, недоступна в Интернете, и для ее просмотра требуется скрипучая среда выполнения.

Answer 2

Я думаю, что вы имеете в виду «реализацию регулярных выражений», а не алгоритм (в обычном смысле).

Вы можете проверить с известными выражениями, которые, как известно, вызывают проблемы с тем или иным подходом.Также ищите функции, которые легче реализовать в одном или другом (это ненадежный подход - разработчики движков regex находят новые способы реализации ранее сложных вещей).

Обычно ответом является чтениедокументацию или посмотрите в известной справке ( «Освоение регулярных выражений» документирует многие популярные случаи).Наконец, почему бы не спросить авторов?