Регулярные выражения: различия между версиями

* NFA (Nondeterministic Finite State Machine; [[w:Конечный автомат|Недетерминированные Конечные Автоматы]]) используют «жадный» алгоритм отката, проверяя все возможные расширения регулярного выражения в определённом порядке и выбирая первое подходящее значение. NFA может обрабатывать подвыражения и обратные ссылки. Но из-за алгоритма отката традиционный NFA может проверять одно и то же место несколько раз, что отрицательно сказывается на скорости работы. Поскольку традиционный NFA принимает первое найденное соответствие, он может и не найти самое длинное из вхождений (этого требует стандарт [[w:POSIX|POSIX]], и существуют модификации NFA, выполняющие это требование  — [[w:sed|GNU sed]]). Именно такой механизм регулярных выражений используется, например, в [[w:Perl|Perl]], [[w:Tcl|Tcl]] и [[w:.NET|.NET]].

* DFA (Deterministic Finite-state Automaton; [[w:Конечный автомат|Детерминированные Конечные Автоматы]]) работают линейно по времени, поскольку не используют откаты и никогда не проверяют какую-либо часть текста дважды. Они могут гарантированно найти самую длинную строку из возможных. DFA содержит только конечное состояние, следовательно, не обрабатывает обратных ссылок, а также не поддерживает конструкций с явным расширением, то есть, не способен обработать и подвыражения. DFA используется, например, в [[w:lex|lex]] и [[w:egrep|egrep]].