Что происходит, когда вы компилируете регулярные выражения?

Question

Мы все знаем, что вы можете скомпилировать ваши часто используемые регулярные выражения во что-то, что работает очень хорошо. Но что это за колдовство происходит за кулисами?

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

Answer 1

Детали компиляции регулярных выражений зависят от реализации. Например, компиляция в Python или re2 просто создает экземпляр объекта регулярного выражения. Конечный автомат этого объекта может быть смоделирован как граф или виртуальная машина. Без компиляции (пример: RE.match(expression, input)) новый объект регулярного выражения создается за кадром каждый раз, когда вызывается match. Это ненужная работа, если вы собираетесь использовать выражение более одного раза.

В C # одна из может произойти три вещи при компиляции :

1. Создается объект регулярного выражения (реализованный как виртуальная машина), аналогичный Python и re2.
2. Создается объект регулярного выражения, и его коды операций виртуальной машины на лету компилируются в инструкции IL в памяти.
3. Создается объект регулярного выражения, и его коды операций виртуальной машины компилируются на диск в виде инструкций IL.

Вы упомянули интерес к алгоритмам. Взгляните на прекрасные статьи Расс Кокса для двух подходов:

• Сопоставление регулярных выражений может быть простым и быстрым - описывает машину на основе графов
• Соответствие регулярных выражений: подход виртуальной машины - описывает реализацию виртуальной машины

Answer 2

Компиляция регулярного выражения аналогична компиляции кода Java или Python; регулярное выражение преобразуется в промежуточное представление, которое механизм RE затем интерпретирует для выполнения соответствующих операций над строкой.