perlreguts

СОДЕРЖАНИЕ

• НАЗВАНИЕ
• ОПИСАНИЕ
• ОБЗОР
  • Краткое замечание по терминам
  • Что такое движок регулярных выражений?
  • Структура программы регулярных выражений
    • Высокий уровень
    • Операции регулярных выражений
    • Какая операция регулярного выражения следующая?
• Обзор процесса
  • Компиляция
    • Граф вызовов парсера и грамматика
    • Сложности парсинга
    • Вывод отладки
    • Оптимизация и анализ "дыры"
  • Выполнение
    • Оптимизации начальной позиции и отсутствия совпадений
    • Выполнение программы
• РАЗНОЕ
  • Поддержка Юникода и локализации
  • Основные структуры
    • Структура pprivate Perl
• СМОТРИТЕ ТАКЖЕ
• АВТОР
• ЛИЦЕНЗИЯ
• СПИСОК ЛИТЕРАТУРЫ

НАЗВАНИЕ

perlreguts - Описание движка регулярных выражений Perl.

ОПИСАНИЕ

Этот документ пытается пролить свет на внутреннее устройство движка регулярных выражений и его работу. Движок регулярных выражений представляет собой значительную часть кодовой базы perl, но относительно плохо изучен. Этот документ является скромной попыткой решить эту проблему. Он основан на опыте автора, комментариях в исходном коде, других статьях о движке регулярных выражений, отзывах на список рассылки perl5-porters, и, без сомнения, на других источниках.

ПРИМЕЧАНИЕ! Следует четко понимать, что поведение и структуры, обсуждаемые в данном документе, отражают состояние движка, как его понимал автор на момент написания. Это НЕ определение API, это просто руководство по внутреннему устройству для тех, кто хочет взломать движок регулярных выражений или понять, как он работает. От читателей этого документа ожидается, что они хорошо понимают синтаксис регулярных выражений perl и их использование в деталях. Если вы хотите узнать о базовых принципах регулярных выражений Perl, см. perlre. А если вы хотите заменить движок регулярных выражений своим собственным, см. perlreapi.

ОБЗОР

Краткое замечание по терминам

Существует дискуссия о том, использовать ли термин "regexp" или "regex". В этом документе мы будем использовать термин "regex", если нет особой причины не использовать его, в противном случае мы объясним почему.

При обсуждении regex необходимо различать их форму исходного кода и внутреннюю форму. В этом документе мы будем использовать термин "шаблон", когда говорим о их текстовой форме исходного кода, и термин "программа", когда говорим об их внутренней представленности. Эти термины соответствуют терминам S-regex и B-regex, которые использует Марк Джейсон Доминус в своей статье о "Rx" ([1] в "СПИСК ЛИТЕРАТУРЫ").

Что такое движок регулярных выражений?

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

Проще говоря, первая часть задачи заключается в преобразовании шаблона во что-то, что компьютер может эффективно использовать для поиска точки совпадения в строке, а вторая часть — в самом поиске.

Для этого нам нужно сгенерировать программу, проанализировав текст. Затем нам нужно выполнить программу, чтобы найти точку в строке, которая соответствует шаблону. И нам нужно сделать все это эффективно.

Структура программы регулярных выражений

Высокий уровень

Хотя это немного запутанно, и некоторые люди возражают против терминологии, стоит взглянуть на комментарий, который присутствует в regexp.h на протяжении многих лет:

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

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

Таким образом, шаблон /foo(?:\w+|\d+|\s+)bar/ можно представить как следующую диаграмму:

     [start]
        |
      <foo>
        |
  +-----+-----+
  |     |     |
<\w+> <\d+> <\s+>
  |     |     |
  +-----+-----+
        |
      <bar>
        |
      [end]

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

Более точно, скажем, что программа регулярных выражений — это кодировка графа. Каждый узел в графе соответствует части исходного шаблона регулярного выражения, например, литеральной строке или ветви, и имеет указатель на узлы, представляющие следующий компонент для сопоставления. Поскольку "узел" и "операнд" уже имеют другие значения в исходном коде Perl, мы будем называть узлы в программе регулярного выражения "операции регулярных выражений" (regops).

Программа представлена массивом regnode структур, одна или несколько из которых представляют отдельную операцию регулярного выражения (regop) программы. Структура regnode является минимальной структурой, необходимой, и имеет структуру поля, которая используется всеми другими более крупными структурами. (Вне этого документа термин "regnode" иногда используется для обозначения "regop", что может быть неоднозначно.)

Указатели "следующий" всех операций regops, кроме BRANCH, реализуют конкатенацию; указатель "следующий" с BRANCH на обоих концах соединяет две альтернативы. [Здесь у нас есть одна из тонких синтаксических зависимостей: отдельная BRANCH (в отличие от набора из них) никогда не конкатенируется ни с чем из-за приоритета операторов.]

Операнд некоторых типов regop — это литеральная строка; для других — это regop, ведущий в подпрограмму. В частности, операнд узла BRANCH — это первая операция regop ветви.

ПРИМЕЧАНИЕ: Как подразумевает метафора железной дороги, это не структура дерева: хвост ветви соединяется с тем, что следует за набором BRANCH. Это как одиночная линия железнодорожных путей, которая разветвляется по мере входа на станцию или железнодорожную площадку и снова соединяется, когда выходит с другой стороны.

Операции регулярных выражений

Основная структура операции regop определена в regexp.h следующим образом:

struct regnode {
    U8  flags;    /* Various purposes, sometimes overridden */
    U8  type;     /* Opcode value as specified by regnodes.h */
    U16 next_off; /* Offset in size regnode */
};

В regcomp.h определены и другие более крупные структуры, похожие на regnode. Они почти как подклассы, так как имеют те же поля, что и regnode, с возможностью дополнительных полей, следующих за структурой, и в некоторых случаях конкретное значение (и имя) некоторых базовых полей переопределяется. Ниже приведено более полное описание.

regnode_1

regnode_2

Структуры regnode_1 имеют тот же заголовок, за которым следует один четырехбайтовый аргумент; структуры regnode_2 содержат два двухбайтовых аргумента вместо этого:

regnode_1                U32 arg1;
regnode_2                U16 arg1;  U16 arg2;

regnode_string

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

regnode_string           char string[1];
                         U8 str_len; /* overrides flags */

regnode_charclass

Скобочные классы символов представлены структурами regnode_charclass, которые имеют четырехбайтовый аргумент, а затем 32-байтовый (256-битовый) битмап, указывающий, какие символы в диапазоне Latin1 включены в класс.

regnode_charclass        U32 arg1;
                         char bitmap[ANYOF_BITMAP_SIZE];

Различные флаги, имена которых начинаются с ANYOF_, используются для особых ситуаций. Выше совпадения Latin1 и вещи, неизвестные до времени выполнения, хранятся в "Структуре pprivate Perl".

regnode_charclass_posixl

Также существует более крупная форма структуры класса символов, используемая для представления POSIX классов символов при соответствии /l, называемая regnode_charclass_posixl, которая имеет дополнительный 32-битовый битмап, указывающий, какие POSIX классы символов были включены.

regnode_charclass_posixl U32 arg1;
                         char bitmap[ANYOF_BITMAP_SIZE];
                         U32 classflags;

regnodes.h определяет массив regarglen[], который дает размер каждого операда в единицах size regnode (4 байта). Используется макрос для расчета размера узла EXACT на основе его поля str_len.

Операции regops определены в regnodes.h, который генерируется из regcomp.sym с помощью regcomp.pl. В настоящее время максимальное возможное количество различных операций regops ограничено 256, примерно четверть из них уже используется.

Набор макросов упрощает и делает более согласованным доступ к полям. Они включают OP(), который используется для определения типа структуры, подобной regnode; NEXT_OFF(), который представляет собой смещение до следующего узла (подробнее об этом позже); ARG(), ARG1(), ARG2(), ARG_SET(), и аналогичные для чтения и записи аргументов; и STR_LEN(), STRING() и OPERAND() для обработки строк и типов, содержащих операции regops.

Какая операция регулярного выражения следующая?

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

• Существует «следующий узел» от заданного узла, значение которого редко бывает полезным, за исключением случаев, когда оно совпадает по значению с одним из других узлов, и в некоторых случаях код предполагает, что это всегда так.

• Существует «следующая операция» от заданной операции/узла. Это операция, физически расположенная после текущей, определяемая размером текущей операции. Это часто бывает полезно, например, при выводе структуры, мы используем этот порядок для обхода. Иногда код предполагает, что «следующий узел» такой же, как «следующая операция», или, другими словами, предполагает, что размер заданного типа операции всегда будет равен одному узлу.

• Существует «следующая операция» от заданной операции. Это операция, к которой можно перейти, перейдя вперёд на значение NEXT_OFF(), или в некоторых случаях для длинных переходов на значение поля arg1 структуры regnode_1. Подпрограмма regnext() обрабатывает это прозрачно. Это логический преемник узла, который в некоторых случаях, например, в случае операции BRANCH, имеет специальное значение.

Обзор процесса

В общих чертах, выполнение сопоставления строки с шаблоном включает следующие шаги:

А. Компиляция

1. Разбор

2. Оптимизация и анализ «дырочного» типа

Б. Выполнение

3. Оптимизации начальной позиции и отсутствия совпадения

4. Выполнение программы

Местоположение этих шагов в фактическом выполнении программы Perl определяется тем, включает ли шаблон интерполяцию каких-либо строковых переменных. Если интерполяция происходит, компиляция выполняется во время выполнения. Если нет, компиляция выполняется во время компиляции. (Модификатор /o изменяет это, как и qr// в определённой степени.) Движок не слишком беспокоится об этом.

Компиляция

Этот код в основном находится в файле regcomp.c вместе с заголовочными файлами regcomp.h, regexp.h и regnodes.h.

Компиляция начинается с pregcomp(), что в основном является начальной обёрткой, которая перенаправляет работу на две другие подпрограммы для основной работы: первая — reg(), которая является точкой входа для разбора; вторая — study_chunk(), отвечает за оптимизацию.

Инициализация в pregcomp() в основном включает создание и заполнение специальной структуры RExC_state_t (определённой в regcomp.c). Практически все внутренние используемые подпрограммы в regcomp.h принимают указатель на одну из этих структур в качестве своего первого аргумента с именем pRExC_state. Эта структура используется для хранения состояния компиляции и содержит множество полей. Аналогичным образом существует множество макросов, которые работают с этой переменной: всё, что выглядит как RExC_xxxx — это макрос, который работает с этим указателем/структурой.

reg() — это начало процесса разбора. Он отвечает за разбор произвольного фрагмента шаблона до конца строки или до первой закрывающей скобки в шаблоне. Это означает, что он может быть использован для разбора регулярного выражения верхнего уровня или любого фрагмента внутри группирующих скобок. Он также обрабатывает «специальные скобки», которые есть в регулярных выражениях Perl. Например, при разборе /x(?:foo)y/, reg() в какой-то момент будет вызван для разбора от символа «?» до и включая «)».

Кроме того, reg() отвечает за разбор одной или нескольких ветвей из шаблона и за «завершение» их корректной установкой указателей на следующий узел. Для выполнения разбора он многократно вызывает regbranch(), который отвечает за обработку до первого символа |.

regbranch() в свою очередь вызывает regpiece(), который обрабатывает «вещи», за которыми следует квантификатор. Для разбора «вещей» вызывается regatom(). Это процедура самого низкого уровня, которая анализирует константные строки, классы символов и различные специальные символы, такие как $. Если regatom() встречает символ «(», он, в свою очередь, вызывает reg().

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

Однако может случиться, что разбор необходимо перезапустить с начала при возникновении различных обстоятельств. Пример — если программа оказывается настолько большой, что в ней есть переходы, которые не помещаются в обычные 16 бит. Существуют две специальные операции, которые могут хранить более длинные пункты назначения переходов — BRANCHJ и LONGBRANCH. Разбор перезапускается, и они используются вместо обычных более коротких. Всякий раз, когда требуется перезапуск разбора, функция возвращает ошибку и устанавливает флаг о том, что нужно сделать. Это передаётся в верхнюю процедуру, которая принимает соответствующее действие и перезапускает всё с нуля. В случае необходимости более длинных переходов устанавливается флаг RExC_use_BRANCHJ в структуре RExC_state_t, который функции знают, как проверить, прежде чем решать, как выполнить переходы.

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

Подпрограмма regtail() вызывается как reg(), так и regbranch() для правильной «установки указателя хвоста». При выполнении, когда мы доходим до конца ветви, мы должны перейти к узлу, следующему за группирующими скобками. Однако при разборе мы не знаем, где будет конец, пока не доберёмся до него, поэтому, когда мы это делаем, мы должны вернуться и обновить смещения соответствующим образом. regtail используется для упрощения этого.

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

Граф вызовов разбора и грамматика

Граф вызовов выглядит так:

reg()                        # parse a top level regex, or inside of
                             # parens
    regbranch()              # parse a single branch of an alternation
        regpiece()           # parse a pattern followed by a quantifier
            regatom()        # parse a simple pattern
                regclass()   #   used to handle a class
                reg()        #   used to handle a parenthesised
                             #   subpattern
                ....
        ...
        regtail()            # finish off the branch
    ...
    regtail()                # finish off the branch sequence. Tie each
                             # branch's tail to the tail of the
                             # sequence
                             # (NEW) In Debug mode this is
                             # regtail_study().

Форма грамматики может быть примерно такой:

atom  : constant | class
quant : '*' | '+' | '?' | '{min,max}'
_branch: piece
       | piece _branch
       | nothing
branch: _branch
      | _branch '|' branch
group : '(' branch ')'
_piece: atom | group
piece : _piece
      | _piece quant

Осложнения разбора

Следствие вышеизложенного описания состоит в том, что шаблон, содержащий вложенные скобки, приведёт к графу вызовов, который циклически проходит через reg(), regbranch(), regpiece(), regatom(), reg(), regbranch() и т.д., до тех пор, пока не будет достигнута самая глубокая вложенность. Все вышеперечисленные подпрограммы возвращают указатель на regnode, что обычно является последним узлом, добавленным в программу. Однако одна проблема заключается в том, что reg() возвращает NULL при разборе синтаксиса (?:) для встроенных модификаторов, устанавливая флаг TRYAGAIN. Флаг TRYAGAIN распространяется вверх до тех пор, пока не будет перехвачен в некоторых случаях regatom(), но в противном случае безусловно regbranch(). Следовательно, он никогда не будет возвращен функцией regbranch() функции reg(). Этот флаг позволяет обнаруживать такие шаблоны, как (?i)+ в качестве ошибок (Квантификатор следует за ничем в регулярном выражении; отмечено <-- ЗДЕСЬ в m/(?i)+ <-- ЗДЕСЬ /).

Другая проблема заключается в том, что представление, используемое для программы, отличается, если ему необходимо хранить Unicode, но точно узнать, необходимо ли ему это, всегда невозможно до середины процесса разбора. Представление Unicode для программы больше и не может быть эффективно сопоставлено. (Дополнительную информацию о причинах см. в разделе "Поддержка Unicode и локализации" ниже.) Если шаблон содержит литеральные Unicode-символы, очевидно, что программе необходимо хранить Unicode. В противном случае анализатор оптимистично предполагает, что можно использовать более эффективное представление, и начинает определять размер на этом основании. Однако, если он затем встретит в шаблоне то, что должно быть сохранено как Unicode, например, последовательность обратной косой черты \x{...} представляющую литеральный символ, это означает, что все ранее вычисленные размеры нужно пересчитать, используя значения, соответствующие представлению Unicode. Это ещё один случай, когда необходимо перезапустить разбор, и это делается немедленно. Функция возвращает ошибку и устанавливает флаг RESTART_UTF8 (инкапсулированный с помощью макроса REQUIRE_UTF8). Запрос на перезапуск передаётся вверх по цепочке вызовов аналогичным образом, пока не будет «перехвачен» в Perl_re_op_compile(), который отмечает шаблон как содержащий Unicode и перезапускает проход определения размера. Также возможно, что конструкции внутри блоков кода во время выполнения могут потребовать представления Unicode, что сигнализируется S_compile_runtime_code() возвращающим false в Perl_re_op_compile().

Перезапуск ранее был реализован с использованием longjmp в regatom() обратно к setjmp в Perl_re_op_compile(), но это оказалось проблематичным, так как последняя — большая функция, содержащая много автоматических переменных, которые плохо взаимодействуют с возникающим потоком управления setjmp.

Вывод отладки

Начиная с версии Perl 5.9.x, вы можете use re Debug => 'PARSE' для просмотра некоторых отладочных сведений о процессе разбора. Начнём с простых шаблонов и перейдём к более сложным.

Итак, при разборе /foo/ мы видим что-то вроде следующей таблицы. Слева показано, что разбирается, а число указывает, куда пойдёт следующая операция. Информация справа — это трассировка вывода графика. Имена выбраны короткими, чтобы не перегружать экран. «tsdy» — это специальная форма regtail(), которая выполняет дополнительный анализ.

>foo<             1    reg
                         brnc
                           piec
                             atom
><                4      tsdy~ EXACT <foo> (EXACT) (1)
                             ~ attach to END (3) offset to 2

Получившаяся программа выглядит следующим образом:

1: EXACT <foo>(3)
3: END(0)

Как видите, хотя мы и разобрали ветвь и фрагмент, в конечном счёте это была только атомная операция. Конечная программа показывает, как всё работает. У нас есть операция EXACT, за которой следует операция END. Число в скобках указывает, куда идёт regnext узла. regnext операции END не используется, так как операции END означают, что мы успешно выполнили сопоставление. Число слева указывает позицию операции в массиве узлов.

Теперь попробуем более сложный шаблон. Добавим квантификатор, так что теперь у нас есть шаблон /foo+/. Мы увидим, что regbranch() дважды вызывает regpiece().

>foo+<            1    reg
                         brnc
                           piec
                             atom
>o+<              3        piec
                             atom
><                6        tail~ EXACT <fo> (1)
                  7      tsdy~ EXACT <fo> (EXACT) (1)
                             ~ PLUS (END) (3)
                             ~ attach to END (6) offset to 3

И в итоге мы получаем программу:

1: EXACT <fo>(3)
3: PLUS(6)
4:   EXACT <o>(0)
6: END(0)

Теперь у нас есть особый случай. У EXACT regop есть regnext 0. Это потому, что если он соответствует, он должен попытаться снова сопоставить себя. PLUS regop обрабатывает фактическое неудачное выполнение EXACT regop и действует соответствующим образом (переходит к regnode 6, если EXACT сопоставился хотя бы один раз, или терпит неудачу, если этого не произошло).

Теперь для чего-то гораздо более сложного: /x(?:foo*|b[a][rR])(foo|bar)$/

>x(?:foo*|b...    1    reg
                         brnc
                           piec
                             atom
>(?:foo*|b[...    3        piec
                             atom
>?:foo*|b[a...                 reg
>foo*|b[a][...                   brnc
                                   piec
                                     atom
>o*|b[a][rR...    5                piec
                                     atom
>|b[a][rR])...    8                tail~ EXACT <fo> (3)
>b[a][rR])(...    9              brnc
                 10                piec
                                     atom
>[a][rR])(f...   12                piec
                                     atom
>a][rR])(fo...                         clas
>[rR])(foo|...   14                tail~ EXACT <b> (10)
                                   piec
                                     atom
>rR])(foo|b...                         clas
>)(foo|bar)...   25                tail~ EXACT <a> (12)
                                 tail~ BRANCH (3)
                 26              tsdy~ BRANCH (END) (9)
                                     ~ attach to TAIL (25) offset to 16
                                 tsdy~ EXACT <fo> (EXACT) (4)
                                     ~ STAR (END) (6)
                                     ~ attach to TAIL (25) offset to 19
                                 tsdy~ EXACT <b> (EXACT) (10)
                                     ~ EXACT <a> (EXACT) (12)
                                     ~ ANYOF[Rr] (END) (14)
                                     ~ attach to TAIL (25) offset to 11
>(foo|bar)$<               tail~ EXACT <x> (1)
                           piec
                             atom
>foo|bar)$<                    reg
                 28              brnc
                                   piec
                                     atom
>|bar)$<         31              tail~ OPEN1 (26)
>bar)$<                          brnc
                 32                piec
                                     atom
>)$<             34              tail~ BRANCH (28)
                 36              tsdy~ BRANCH (END) (31)
                                    ~ attach to CLOSE1 (34) offset to 3
                                 tsdy~ EXACT <foo> (EXACT) (29)
                                    ~ attach to CLOSE1 (34) offset to 5
                                 tsdy~ EXACT <bar> (EXACT) (32)
                                    ~ attach to CLOSE1 (34) offset to 2
>$<                        tail~ BRANCH (3)
                               ~ BRANCH (9)
                               ~ TAIL (25)
                           piec
                             atom
><               37        tail~ OPEN1 (26)
                               ~ BRANCH (28)
                               ~ BRANCH (31)
                               ~ CLOSE1 (34)
                 38      tsdy~ EXACT <x> (EXACT) (1)
                             ~ BRANCH (END) (3)
                             ~ BRANCH (END) (9)
                             ~ TAIL (END) (25)
                             ~ OPEN1 (END) (26)
                             ~ BRANCH (END) (28)
                             ~ BRANCH (END) (31)
                             ~ CLOSE1 (END) (34)
                             ~ EOL (END) (36)
                             ~ attach to END (37) offset to 1

Что приводит к программе

 1: EXACT <x>(3)
 3: BRANCH(9)
 4:   EXACT <fo>(6)
 6:   STAR(26)
 7:     EXACT <o>(0)
 9: BRANCH(25)
10:   EXACT <ba>(14)
12:   OPTIMIZED (2 nodes)
14:   ANYOF[Rr](26)
25: TAIL(26)
26: OPEN1(28)
28:   TRIE-EXACT(34)
      [StS:1 Wds:2 Cs:6 Uq:5 #Sts:7 Mn:3 Mx:3 Stcls:bf]
        <foo>
        <bar>
30:   OPTIMIZED (4 nodes)
34: CLOSE1(36)
36: EOL(37)
37: END(0)

Здесь мы можем увидеть гораздо более сложную программу с различными оптимизациями. В regnode 10 мы видим пример, где класс символов, содержащий только один символ, был преобразован в EXACT узел. Мы также можем увидеть, где целое альтернативное выражение было преобразовано в TRIE-EXACT узел. Вследствие этого некоторые regnode были помечены как оптимизированные. Мы можем видеть, что символ $ был преобразован в EOL regop, специальный фрагмент кода, который ищет \n или конец строки.

Следующая ссылка для BRANCH интересна тем, что она указывает на то, куда выполнение должно перейти, если ветвь терпит неудачу. При выполнении, если движок пытается перейти от ветви к regnext которая не является ветвью, то движок будет знать, что весь набор ветвей потерпел неудачу.

Оптимизация и анализ "смотрите-в-отверстие"

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

'ababababababababababab' =~ /(a|b)*z/

Часть (a|b)* может соответствовать каждому символу в строке, а затем каждый раз терпит неудачу, потому что в строке нет z. Поэтому, очевидно, мы можем избежать использования движка регулярных выражений, если в строке нет z. Аналогично, в шаблоне:

/foo(\w+)bar/

В этом случае мы знаем, что строка должна содержать foo, за которым должен следовать bar. Мы можем использовать быстрый алгоритм Бойера-Мура, как реализованный в fbm_instr(), чтобы найти расположение этих строк. Если они не существуют, то нам не нужно прибегать к гораздо более дорогостоящему движку регулярных выражений. Ещё лучше, если они существуют, то мы можем использовать их позиции для уменьшения области поиска, которую движку регулярных выражений нужно охватить, чтобы определить, соответствует ли весь шаблон.

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

• якорные фиксированные строки

• плавающие фиксированные строки

• требования к минимальной и максимальной длине

• начальный класс

• Позиции начала/конца строки

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

Ещё одна оптимизация, которая может произойти, — это "слияние EXACT", где два последовательных EXACT узла сливаются в один regop. Ещё более агрессивная форма этого заключается в том, что последовательность ветвей типа EXACT BRANCH ... EXACT может быть преобразована в TRIE-EXACT regop.

Всё это происходит в процедуре study_chunk(), которая использует специальную структуру scan_data_t для хранения выполненного анализа и выполняет оптимизации "смотрите-в-отверстие" по мере необходимости.

Код, связанный с study_chunk() крайне загадочен. Будьте осторожны. :-)

Выполнение

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

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

Две точки входа — re_intuit_start() и pregexec(). Эти процедуры имеют несколько близкие отношения с перекрытием функций, и pregexec() может даже вызвать re_intuit_start() самостоятельно. Тем не менее, другие части исходного кода perl могут вызвать либо ту, либо другую, или обе.

Выполнение самого интерпретатора раньше было рекурсивным, но благодаря усилиям Дэйва Митчелла в рамках разработки 5.9.x это изменилось: теперь на куче поддерживается внутренний стек, и процедура полностью итеративная. Это может быть сложным, так как код довольно консервативен в отношении того, какой состояние он сохраняет, в результате чего две последовательные строки кода фактически могут работать в совершенно разных контекстах из-за имитированной рекурсии.

Оптимизации начальной позиции и отсутствия совпадений

re_intuit_start() отвечает за обработку начальных точек и оптимизаций отсутствия совпадений, как определено результатами анализа, выполненного study_chunk() (и описанного в "Оптимизация и анализ смотрите-в-отверстие").

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

Она вызывает несколько других процедур, таких как fbm_instr(), которая выполняет быстрое сопоставление Бойера-Мура, и find_byclass(), которая отвечает за поиск начала с использованием первого обязательного regop в программе.

Когда критерии оптимизации удовлетворены, вызывается reg_try() для выполнения сопоставления.

Выполнение программы

pregexec() — главная точка входа для запуска регулярного выражения. Она содержит поддержку инициализации состояния интерпретатора регулярных выражений, вызов re_intuit_start() при необходимости и запуск интерпретатора для строки с различных начальных позиций по мере необходимости. Когда требуется использование интерпретатора регулярных выражений, pregexec() вызывает regtry().

regtry() — точка входа в интерпретатор регулярных выражений. Он ожидает в качестве аргументов указатель на структуру regmatch_info и указатель на строку. Он возвращает целое число 1 для успеха и 0 для неудачи. Он по сути является оберточным устройством для regmatch().

regmatch — основной «рекурсивный цикл» интерпретатора. По сути, это огромный оператор switch, реализующий конечный автомат, где возможными состояниями являются сами regop плюс ряд дополнительных промежуточных и ошибочных состояний. Некоторые состояния реализованы как подпрограммы, но основная часть — это встроенный код.

РАЗНОЕ

Поддержка Юникода и локализации

При работе со строками, содержащими символы, которые нельзя представить с помощью восьмибитного набора символов, perl использует внутреннее представление, которое является разрешительной версией кодировки UTF-8 Юникода[2]. Это использует одиночные байты для представления символов набора ASCII и последовательности из двух или более байтов для всех остальных символов. (См. perlunitut для получения дополнительной информации о взаимосвязи между UTF-8 и кодировкой perl, utf8. Разница не важна для этого обсуждения.)

Как бы вы ни взглянули на это, поддержка Юникода будет проблемой в движке регулярных выражений. Трюки, которые могут быть хороши при наличии 256 возможных символов, часто не будут масштабироваться для обработки размера набора символов UTF-8. Вещи, которые вы можете принять как должное с ASCII, могут не быть истинными с Unicode. Например, в ASCII можно предположить, что sizeof(char1) == sizeof(char2), но в UTF-8 это не так. Складывание Unicode в верхний регистр намного сложнее, чем простые правила ASCII, и даже когда не используется Unicode, а используются только локальные наборы символов с одним байтом, вещи могут стать сложными (например, БУКВА С ЗАОСТРЕННОЙ ЛИНИЕЙ (ЛАТИНСКИЙ МАЛЫЙ) (U+00DF, ß) должна соответствовать «SS» в локализованном регистронезависимом сопоставлении).

Усложняет ситуацию то, что поддержка UTF-8 была добавлена позже в движок регулярных выражений (как и в perl), и это неизбежно усложнило ситуацию. Очевидно, что разработать движок регулярных выражений с поддержкой Unicode с самого начала проще, чем переделать его в тот, который ею не обладал.

Практически все regop, которые включают в себя просмотр входной строки, имеют два случая: один для UTF-8 и один — нет. На самом деле, это часто сложнее, так как шаблон также может быть UTF-8.

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

Базовые структуры

Структура regexp, описанная в perlreapi, является общей для всех движков регулярных выражений. Два ее поля предназначены для частного использования движка регулярных выражений, который скомпилировал шаблон. Это члены intflags и pprivate. pprivate — указатель типа void на произвольную структуру, использование и управление которой возлагается на движок компиляции. perl никогда не будет изменять ни одно из этих значений. В случае стандартного движка структура, на которую указывает pprivate, называется regexp_internal.

Ее поля pprivate и intflags содержат данные, специфичные для каждого движка.

Существует две структуры, используемые для хранения скомпилированного регулярного выражения. Одна, структура regexp, описанная в perlreapi, заполняется используемым в настоящее время движком, а некоторые из ее полей читаются perl для реализации таких вещей, как форматирование qr//.

Другая структура указывается через поле regexp структуры pprivate и дополняет intflags в той же структуре, считается собственностью движка регулярных выражений, который скомпилировал регулярное выражение.

Структура regexp содержит все данные, которые perl нужно знать, чтобы правильно работать с регулярным выражением. Она включает в себя данные об оптимизациях, которые perl может использовать для определения того, нужно ли действительно использовать движок регулярных выражений, и различные другие контрольные данные, которые необходимы для правильного выполнения шаблонов в различных контекстах, таких как, например, является ли шаблон якорем каким-либо образом, или какие флаги использовались во время компиляции, или содержит ли программа специальные конструкции, о которых perl нужно знать.

Кроме того, он содержит два поля, предназначенные для внутреннего использования движка регулярных выражений, который скомпилировал шаблон. Это intflags и внутренние члены. pprivate — это указатель на произвольную структуру, использование и управление которой возлагается на движок компиляции. Perl никогда не будет изменять ни одно из этих значений.

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

Структура pprivate Perl

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

typedef struct regexp_internal {
        U32 *offsets;           /* offset annotations 20001228 MJD
                                 * data about mapping the program to
                                 * the string*/
        regnode *regstclass;    /* Optional startclass as identified or
                                 * constructed by the optimiser */
        struct reg_data *data;  /* Additional miscellaneous data used
                                 * by the program.  Used to make it
                                 * easier to clone and free arbitrary
                                 * data that the regops need. Often the
                                 * ARG field of a regop is an index
                                 * into this structure */
        regnode program[1];     /* Unwarranted chumminess with
                                 * compiler. */
} regexp_internal;

offsets

Offsets содержит отображение смещения в program на смещение в строке precomp. Это используется только отладчиком визуальных регулярных выражений ActiveState.

regstclass

Специальная regop, используемая re_intuit_start() для проверки, может ли шаблон совпасть в определенной позиции. Например, если движок регулярных выражений знает, что шаблон должен начинаться с 'Z', он может просматривать строку, пока не найдёт символ 'Z', и затем запустить движок регулярных выражений оттуда. Процедура, которая обрабатывает это, называется find_by_class(). Иногда это поле указывает на regop, встроенный в программу, а иногда — на независимую синтетическую regop, созданную оптимизатором.

data

Это поле указывает на структуру reg_data, которая определена следующим образом

struct reg_data {
    U32 count;
    U8 *what;
    void* data[1];
};

Эта структура используется для обработки структур данных, которые движку регулярных выражений необходимо обработать особым образом во время операции клонирования или освобождения скомпилированного продукта. Каждый элемент массива data имеет соответствующий элемент в массиве what. Во время компиляции regops, которые требуют хранения специальных структур, добавляют элемент в каждый массив, используя процедуру add_data(), а затем сохраняют индекс в regop.

program

Скомпилированная программа. Встроена в структуру, так что вся структура может рассматриваться как один блок.

См. также

perlreapi

perlre

perlunitut

Автор

Автор: Yves Orton, 2006.

С извлечениями из Perl и вкладами и предложениями Ronald J. Kimball, Dave Mitchell, Dominic Dunlop, Mark Jason Dominus, Stephen McCamant и David Landgren.

В настоящее время поддерживается разработчиками Perl 5.

Лицензия

Такие же условия, как и у Perl.

Ссылки

[1] https://perl.plover.com/Rx/paper/

[2] https://www.unicode.org/