Как работает двигатель RegEx

Изучая регулярные выражения, мне стало интересно, как работает основной движок. Вероятно, более конкретно, я хотел бы узнать больше о том, как он анализирует, приоритизирует и анализирует выражение. Я чувствую, что движок RegEx является черным ящиком для меня, и мне бы очень понравилось расшифровывать его.

Итак, я хотел бы спросить, есть ли какие-то большие ресурсы, которые я мог бы прочитать, обсуждая теорию двигателей RegEx.

* Примечание: мне не интересно создавать движок, просто изучая его внутреннюю работу.

Ответы

Ответ 1

Существует два основных класса двигателей регулярных выражений.

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

    Примеры двигателей на базе FSA:

    • Posix/GNU ERE/BRE — Используется в большинстве утилит unix, таких как grep, sed и awk.
    • Re2 — Относительно новый проект по попытке дать больше возможностей для метода Automata.
       

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

    Примеры двигателей, основанных на обратном слежении:

    • Perl — Оригинал. Большинство других движков этого типа пытаются реплицировать функциональность регулярных выражений на языке Perl.
    • PCRE — Наиболее успешная реализация. Эта библиотека является наиболее широко используемой реализацией. Он имеет богатый набор функций, некоторые из которых больше не могут считаться "Regular" .
    • Python, Ruby, Java, . NET — Другие реализации, которые я не намерен описывать дальше.

Для получения дополнительной информации:

Если вы хотите, чтобы я что-то расширил, опубликуйте комментарий.