Регулярные выражения
Страница 2. Три типа машин регулярных выражений
Страница 2 из 7
 

Три типа машин регулярных выражений

На практике применяются три типа машин регулярных выражений.

  1. DFA (Deterministic Finite-state Automaton – детерминированные конечные автоматы) машины работают линейно по времени, поскольку не нуждаются в откатах (и никогда не проверяют один символ дважды). Они могут гарантированно найти самую длинную строку из возможных. Однако, поскольку DFA содержит только конечное состояние, он не может найти образец с обратной ссылкой и, из-за отсутствия конструкций с явным расширением, не ловит подвыражений. Они используются, например, в awk, egrep или lex.
  2. Традиционные NFA-машины (NonDeterministic Finite-state Automaton – недетерминированные конечные автоматы) используют "жадный" алгоритм отката, проверяя все возможные расширения регулярного выражения в определенном порядке и выбирая первое подходящее значение. Поскольку традиционный NFA конструирует определенные расширения регулярного выражения для поиска соответствий, он может искать подвыражения и backreferences. Но из-за откатов традиционный NFA может проверять одно и то же место несколько раз. В результате работает он медленнее. Поскольку традиционный NFA принимает первое найденное соответствие, он может и не найти самое длинное из вхождений. Именно такие механизмы регулярных выражений используются в Perl, Python, Emacs, Tcl и .Net.
  3. POSIX NFA - машины похожи на традиционные NFA-машины, за исключением "терпеливости" – они продолжают поиск, пока не найдут самое длинное соответствие. Поэтому POSIX NFA-машины медленнее традиционных, и поэтому же нельзя заставить POSIX NFA предпочесть более короткое соответствие длинному. Одно из главных достоинств POSIX NFA-машины – наличие стандартной реализации.

Чаще всего программисты используют традиционные NFA-машины, поскольку они точнее, чем DFA или POSIX NFA. Хотя в наихудшем случае время их работы растет по экспоненте, использование образцов, снижающих уровень неоднозначности и ограничивающих глубину поиска с возвратом (backtracking), позволяет управлять их поведением, уменьшая время поиска до приемлемых значений.
 
« Предыдущая статья   Следующая статья »