Regex engine internals as a library. Part 3

Тип данных - НКА

Если внутри крейта regex и был центральный тип данных, то, по всей вероятности, это был бы НКА. Если точнее, это НКА Томпсона, что означает, что он был построен алгоритмом, схожим с Томпсоновским алгоритмом конструирования. Этот алгоритм строит НКА из структурированного представления р.в. за время O(m), где m пропорционально размеру р.в. после подсчёта повторений, которые разворачиваются. (Например, a{5} - это aaaaa.) Алгоритм работает, отображая каждый тип р.в. в мини-НКа, а затем определяя правила для комбинирования этих мини-НКА в один большой НКА.

НКА - центральный тип данных, потому что он используется напрямую, как есть, для реализации движка р.в. Но НКА так же могут быть преобразован в другие типы (такие, как ДКА), которые в свою очередь используются для реализации разных движков р.в. По сути, в данный момент, если вам хочется построить движок р.в. с помощью крейта regex-automata, то вам придётся начать с НКА Томпсона.

Перед тем, как разбираться с НКА более детально, взглянем на простой пример.

Простой пример НКА

Так же как и в случае извлечения литералов, regex-cli может нам быть полезным, позволяя выводить отладочное представление НКА заданного р.в.:

$ regex-cli debug thompson 'a'
        parse time:  9.856µs
    translate time:  3.005µs
  compile nfa time:  18.51µs
            memory:  700
            states:  6
       pattern len:  1
       capture len:  1
        has empty?:  false
          is utf8?:  true
       is reverse?:  false
   line terminator:  "\n"
       lookset any:  ∅
lookset prefix any:  ∅
lookset prefix all:  ∅

thompson::NFA(
>000000: binary-union(2, 1)
 000001: \x00-\xFF => 0
^000002: capture(pid=0, group=0, slot=0) => 3
 000003: a => 4
 000004: capture(pid=0, group=0, slot=1) => 5
 000005: MATCH(0)

transition equivalence classes: ByteClasses(0 => [\x00-`], 1 => [a], 2 => [b-\xFF], 3 => [EOI])
)

Далее я буду сокращать вывод только до самого НКА. Так что объясню, что тут значит остальной вывод:

• Тайминги парсинга и трансляции - тоже самое, что и в случае извлечения литералов. Напомню, что это время построения значений Ast и Hir.

• compile nfa time - время построения структуры данных NFA из значения Hir.

• memory - объём кучи, используемой НКА

• states - количество состояний в НКА

• pattern len - количество шаблонов в НКА

• capture len - количество групп захвата (далее - г.з.), скомпилированных в НКА. Когда г.з. задействованы (по-умолчанию это так), тогда в НКА будет как минимум одна г.з., соответствующая всему совпадению.

• has empty? - может ли НКА вернуть пустую строку в качестве совпадения или нет.

• is utf8? - гарантирует ли НКА то, что он никогда не вернёт в качестве совпадения невалидную UTF-8 строку. Это так же включает в себя ограничение на сопоставление пустой строки между code units в UTF-8 codepoint. Например,