Регулярные выражения и NFA

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

Мы пишем такие регулярные выражения(a+|b)c, а затем используйте его для сопоставления строкиaacde,abcde, что это за процесс?

Некоторое время назад я пытался найти и изучить соответствующие материалы, и тут узнал следующее:

• В настоящее время существует два основных типа движков регулярных выражений:NFAа такжеDFA
• JavaScript использует движок NFA

Так что же такое NFA и чем он отличается от DFA? Как NFA реализует сопоставление регулярных выражений?

Далее я попытаюсь представить его по-своему, и я надеюсь, что это также поможет вам, кто в этом заинтересован.

NFA

NFA расшифровывается как Nondeterministic Finite Automaton, недетерминированный конечный автомат.

Это немного эзотерично, и я был сбит с толку, когда впервые увидел это, давайте не торопимся.

Давайте сначала поговорим о конечном автомате (автоматизации), давайте посмотрим на примерную диаграмму:

В конечном автомате есть некоторые элементы, которые описаны отдельно в соответствии с приведенным выше рисунком:

• Запуск состояния: круги представляют собой состояние, является «нет начала стрелки», указательное состояние, начальное состояние, приведенный выше пример является S1
• Конечное состояние: также называемое состоянием принятия, представленное двойными кружками на рисунке, также S1 в этом примере.
• Вход: в состоянии, когда символ/сигнал вводится в конечный автомат, разные входные данные заставляют конечный автомат производить разные изменения состояния.
• Переход: в состоянии, согласно определенному вводу, процесс перехода в определенное состояние является переходом

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

Функция конечного автомата на приведенном выше рисунке состоит в том, чтобы определить, содержит ли двоичное число четное количество нулей. Как видно из рисунка, на входе только 1 и 0. Из состояния S1 только вход 0 перейдет в состояние S2, а в состоянии S2 только вход 0 перейдет в состояние S1. Следовательно, после ввода двоичного числа, если конечное состояние удовлетворяется, то есть оно останавливается в состоянии S1 в конце, тогда входное двоичное число содержит четное количество нулей.

Все еще немного кружится голова, какое это имеет отношение к регулярным выражениям?

Регулярное выражение можно рассматривать как описание набора строк. Например(a+|b)cСоответствующий набор строк:

ac
bc
aac
aaac
aaaac
...

Конечный автомат также можно использовать для описания набора строк, который также является набором, описываемым регулярным выражением, представленным конечным автоматом, который может быть таким:

Диаграмма состояний NFA здесь нарисована на странице, которую я написал, что относительно просто, но я думаю, вы можете ее понять. ты сможешьздесь (луоботанг/нфа)Попробуйте сами, поддерживаются только простые регулярные выражения.

Кроме того, конечные автоматы могут «воплощать в жизнь", после того, как приведенный выше конечный автомат будет задан, его можно использовать для обнаружения входной строки. Если он наконец совпадет, это означает, что входная строка и регулярное выражение(a+|b)cсоответствовать.

Поэтому регулярные выражения в языках программирования обычно реализуются через конечные автоматы. Процесс сопоставления строк с регулярными выражениями можно разложить на:

• Регулярное выражение преобразовано в эквивалентный конечный автомат
• Выполнение входной строки конечного автомата

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

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

Например, для регулярных выраженийab|ac, соответствующий NFA может быть таким:

Как видите, здесь в состоянии 1, если ввестиa, на самом деле есть две возможности, если следующий символbТогда матч может быть успешным, следующий символcтакже может успешно совпадать. Таким образом, конечной машине, возможно, придется перепробовать все возможности во время своего выполнения. После неудачной попытки возможного сопоставления путей необходимо вернуться в предыдущее состояние и попробовать другие пути, т.е.отступление".

Но DFA устраняет эту неопределенность, поэтому вполне возможно, что он должен работать лучше, чем NFA, потому что не требуется обратного отслеживания.

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

Следующее регулярное выражение можно использовать для проверки того, является ли движок, используемый текущим языком программирования, NFA:

nfa|nfa not

Используйте приведенное выше регулярное выражение для проверки строкиnfa not, механизм NFA обнаруживает, чтоnfaвернет успешное совпадение, а DFA попытается продолжить поиск, а значит, получит "самый длинный матч".

От регулярных выражений к NFA

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

Алгоритм Томпсона

Алгоритм Томпсона используется для преобразования регулярных выражений в NFA, это не самый эффективный алгоритм, но он практичен и прост для понимания.

В алгоритме Томпсона используются два самых основных преобразования:

Обычный переход находится в одном состоянии, после ввода символа а он переходит в другое состояние, эпсилон-переход не требует ввода и осуществляет переход из одного состояния в другое состояние.

Различные операции в регулярных выражениях можно реализовать, комбинируя два вышеуказанных преобразования:

• Комбинаторные операцииRS:

• операция заменыR|S:

  

• Повторите операциюR*:

  

R и S на приведенном выше рисунке — это NFA с начальным и конечным состояниями.

с регулярным выражениемab|cНапример, включая две операции:

• abкомбинация
• abрезультат, сcзаменять

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

Прежде всего, нам нужно преобразовать регулярные выражения в удобный способ записи ввода и операций.

Регулярное выражение -> Постфиксное выражение

Постфиксное выражение — это выражение, удобное для записи ввода и операций, и оно уже включает в себя приоритет операций, также известный какОбратная польская запись(обратная польская нотация, сокращенно RPN).

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

регулярное выражениеab|cСоответствующее постфиксное выражениеab.c|.

Таким образом, постфиксное выражение можно решить, сканируя постфиксное выражение одно за другим и определяя в нем операторы, которые необходимо выполнить. Для регулярных выражений, после превращения их в постфиксные выражения, они дополнительно конструируются, и окончательный NFA получается в процессе «оценки».

Те, которые используются для создания постфиксных выражений,Алгоритм планирования поля.

Для сценария обработки регулярных выражений здесь алгоритм примерно описывается следующим образом:

Код находится в:regex2post() | nfa.js#L14 - luobotang/nfa

- 创建输出队列 output 和运算符栈 ops
- 依次读取输入字符串中每一个字符 ch
  - 如果 ch 是普通字符，追加到 output
  - 如果 ch 是运算符，只要 ops 栈顶的运算符优先级不低于 ch，依次出栈并追加到 output，最后将 ch 入栈 ops
  - 如果 ch 是“(”，入栈 ops
  - 如果 ch 是“)”，只要 ops 栈顶不是“(”，依次出栈并追加到 output
- 将 ops 中运算符依次出栈追加到 output
- 返回 output

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

Приоритет операторов следующий (от большего к меньшему):

• * ? +
• .
• |
• (

Постфиксное выражение -> NFA

Создание NFA на основе суффиксных выражений — это процесс непрерывного комбинирования простых NFA для получения сложных NFA.

Структура данных, используемая для представления состояния State:

// State
{
  id: String,
  type: String, // 'n' - normal, 'e' - epsilon, 'end'
  symbol: String, // 普通状态对应的输入字符
  out: State, // 允许的下一个状态
  out1: State // 允许的下一个状态
}

Каждое состояние может соответствовать не более чем двум состояниям выхода, напримерa|b|cвыражение, будет разложено на(a|b)|c, оператор '|' одновременно обрабатывает только два (под)выражения.

В процессе построения окончательной НКА каждый раз создается фрагмент Фрагмент НКА:

// Fragment
{
  start: State,
  out: State
}

Каким бы сложным ни был фрагмент NFA, он имеет только один вход (начальное состояние) и один выход (конечное состояние).

Эта часть кода находится в:post2nfa() | nfa.js#L90 - luobotang/nfa

Процесс обработки примерно такой:

- 创建用于记录 NFA 片段的栈 stack
- 依次读取输入的后缀表达式的每个字符 ch
  - 如果 ch 是运算符，从 stack 出栈所需数目的 NFA 片段，构建新的 NFA 片段后入栈 stack
  - 如果 ch 是普通字符，创建新的状态，并构建只包含此状态的 NFA 片段入栈 stack
- 返回 stack 栈顶的 NFA 片段，即最终结果

В качестве примера возьмем обработку комбинаторных операций:

const e2 = stack.pop()
const e1 = stack.pop()
e1.out.out = e2.start
stack.push(new Fragment(e1.start, e2.out))

Извлеките два фрагмента NFA из стека, затем соедините их встык, чтобы создать новый фрагмент NFA и поместить его обратно в стек.

Другие процедуры обработки подробно описываться не будут, если интересно, можете посмотреть код.

Реализация НФА

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

Однако из-за неопределенности NFA одновременно может быть несколько совпадающих состояний.

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

Код находится в:simulator.js - luobotang/nfa

Суммировать

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

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

Наконец, спасибо за чтение!

использованная литература

• Writing own regular expression parser - Amer Gerzic
• Regular Expression Matching Can Be Simple And Fast - Russ Cox
• Automata theory - wikipedia
• Nondeterministic finite automaton - wikipedia
• file-infix-to-postfix-regexp-js - gist.github.com
• Shunting-yard algorithm - wikipedia.com