Regular Expressions
Типы выражений с регулярным выражением

NFA

Двигатель NFA (недетерминированный конечный автомат) управляется шаблоном .

Принцип

Шаблон регулярного выражения анализируется на дерево.

Текущий указатель позиции установлен на начало входной строки, и в этой позиции выполняется попытка совпадения. Если совпадение fais, позиция увеличивается до следующего символа в строке, а другое совпадение выполняется из этой позиции. Этот процесс повторяется до тех пор, пока не будет найдено совпадение или не будет достигнут конец входной строки.

Для каждой попытки матча

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

Если алгоритм встречается с узлом дерева, который не соответствует входной строке в текущей позиции, ему придется отступить . Это выполняется, возвращаясь к родительскому узлу в дереве, сбросив текущую позицию ввода до значения, которое оно имело при вводе родительского узла, и попробовав следующую альтернативную ветку.

Если алгоритму удается выйти из дерева, он сообщает об успешном совпадении. В противном случае, когда все возможности были опробованы, совпадение не выполняется.

Оптимизации

Двигатели Regex обычно применяют некоторые оптимизации для лучшей производительности. Например, если они определяют, что совпадение должно начинаться с заданного символа, они будут пытаться выполнить совпадение только в тех положениях входной строки, где отображается этот символ.

пример

Сопоставьте a(b|c)a с входной строкой abeacab :

Дерево шаблонов может выглядеть примерно так:

CONCATENATION
    EXACT: a
    ALTERNATION
        EXACT: b
        EXACT: c
    EXACT: a

Сопоставление выполняется следующим образом:

a(b|c)a      abeacab
^            ^

a находится во входной строке, потребляет ее и переходит к следующему элементу в дереве шаблонов: чередование. Попробуйте первую возможность: точную b .

a(b|c)a      abeacab
  ^           ^

b , поэтому чередование завершается успешно, потребляет его и переходит к следующему элементу в конкатенации: точный a :

a(b|c)a      abeacab
      ^        ^

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

a(b|c)a      abeacab
    ^         ^

c не находится в этом положении. Откат к конкатенации. На данный момент нет других возможностей попробовать, поэтому в начале строки нет совпадений.

Попытайтесь выполнить второе совпадение в следующей позиции ввода:

a(b|c)a      abeacab
^             ^

a не соответствует. Попытайтесь провести еще одно совпадение на следующей позиции:

a(b|c)a      abeacab
^              ^

Не повезло. Перейдите на следующую позицию.

a(b|c)a      abeacab
^               ^

матчи, поэтому потреблять его и ввести чередование:

a(b|c)a      abeacab
  ^              ^

b не соответствует. Попробуйте вторую альтернативу:

a(b|c)a      abeacab
    ^            ^

c , поэтому потребляйте его и переходите к следующему элементу в конкатенации:

a(b|c)a      abeacab
      ^           ^

a спички, и конец дерева были достигнуты. Сообщить об успешном матче:

a(b|c)a      abeacab
                \_/

DFA

Входной сигнал управляется двигателем DFA (детерминированный конечный автомат).

Принцип

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

Последствия

Время согласования ограничено размером входной строки. Отказов нет, и двигатель может найти несколько совпадений одновременно, даже совпадающих совпадений.

Основным недостатком этого метода является уменьшенный набор функций, который может поддерживаться двигателем по сравнению с типом двигателя NFA.

пример

Сопоставьте a(b|c)a против abadaca :

abadaca      a(b|c)a
^            ^        Attempt 1      ==> CONTINUE

abadaca      a(b|c)a
 ^           ^        Attempt 2      ==> FAIL
               ^      Attempt 1.1    ==> CONTINUE
                 ^    Attempt 1.2    ==> FAIL

abadaca      a(b|c)a
  ^          ^        Attempt 3      ==> CONTINUE
                   ^  Attempt 1.1    ==> MATCH

abadaca      a(b|c)a
   ^         ^        Attempt 4      ==> FAIL
               ^      Attempt 3.1    ==> FAIL
                 ^    Attempt 3.2    ==> FAIL

abadaca      a(b|c)a
    ^        ^        Attempt 5      ==> CONTINUE

abadaca      a(b|c)a
     ^       ^        Attempt 6      ==> FAIL
               ^      Attempt 5.1    ==> FAIL
                 ^    Attempt 5.2    ==> CONTINUE

abadaca      a(b|c)a
      ^      ^        Attempt 7      ==> CONTINUE
                   ^  Attempt 5.2    ==> MATCH

abadaca      a(b|c)a
       ^       ^      Attempt 7.1    ==> FAIL
                 ^    Attempt 7.2    ==> FAIL