perlreguts

СОДЕРЖАНИЕ

• ИМЯ
• ОПИСАНИЕ
• ОБЗОР
  • Краткое замечание о терминах
  • Что такое движок регулярных выражений?
  • Структура программы регулярного выражения
    • Высокий уровень
    • Regops
    • Какой regop следует дальше?
• Обзор процесса
  • Компиляция
    • Разбор по размеру
    • Разбор для построения
    • Граф вызовов разбора и грамматика
    • Осложнения при разборе
    • Вывод отладки
    • Оптимизация и анализ «дырочного» прохода
  • Выполнение
    • Оптимизации начальной позиции и отсутствия совпадения
    • Выполнение программы
• РАЗНОЕ
  • Поддержка Unicode и локализации
  • Основные структуры
    • Структура 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:

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

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

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

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

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

Более точно, скажем, что программа regex представляет собой кодирование графа. Каждый узел в графе соответствует части исходного шаблона regex, например, литеральной строке или ветви, и указывает на узлы, представляющие следующий компонент для сопоставления. Поскольку «узел» и «оператор кода» уже имеют другие значения в исходном коде perl, мы будем называть узлы в программе regex «regops».

Программа представлена массивом regnode структур, одна или несколько из которых представляют один regop программы. Структура regnode является наименьшей необходимой структурой и имеет структуру поля, которая используется всеми другими более крупными структурами.

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

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

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

Regops

Базовая структура 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() для обработки строк и типов regop.

Какой regop следует дальше?

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

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

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

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

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

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

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

1. Разбор для определения размера

2. Разбор для построения

3. Оптимизация и анализ "дырочных" выражений

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

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

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

Местоположение этих шагов в реальном выполнении программы 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, — это макрос, который работает с этим указателем/структурой.

Разбор для определения размера

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

Этот этап контролируется установкой макроса SIZE_ONLY.

Процесс разбора происходит почти точно так же, как и в фазе построения, за исключением того, что большинство подпрограмм коротко замыкаются, чтобы изменить поле размера RExC_size и ничего более не делать.

Разбор для построения

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

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

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

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

Подпрограмма 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)+ (Квантификатор следует за чем-то в регулярном выражении; отмечено <-- HERE в m/(?i)+ <-- HERE /).

Ещё одно осложнение заключается в том, что представление программы отличается, если ей необходимо хранить Unicode, но всегда нельзя быть уверенным, нужно ли это до середины процесса разбора. Представление Unicode для программы больше и не может быть обработано так же эффективно. (См. "Поддержка Unicode и локализации" ниже для получения более подробной информации о причинах.) Если шаблон содержит литеральные Unicode-символы, очевидно, что программе необходимо хранить Unicode. В противном случае анализатор оптимистично предполагает, что можно использовать более эффективное представление, и начинает вычислять размер на этой основе. Однако, если затем в шаблоне встречается что-то, что должно храниться как Unicode, например, последовательность экранирования \x{...}, представляющая литеральный символ, это означает, что все ранее рассчитанные размеры должны быть пересчитаны с использованием значений, соответствующих представлению Unicode. В настоящее время все конструкции регулярных выражений, которые могут вызвать это, разбираются кодом в regatom().

Чтобы избежать ненужной работы при необходимости перезапуска, этап определения размера отменяется — regatom() немедленно возвращает NULL, устанавливая флаг 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 означают, что мы успешно выполнили сопоставление. Число слева указывает позицию операции в массиве regnode.

Теперь давайте попробуем более сложный шаблон. Мы добавим квантификатор, так что теперь у нас есть шаблон /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 значение regnext равно 0. Это означает, что если совпадение произошло, то оно должно попытаться сопоставить себя снова. Операция PLUS обрабатывает фактическую неудачу операции EXACT и действует соответствующим образом (переходит в узел 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 были помечены как оптимизированные. Мы видим, что символ $ был преобразован в regop EOL, специальный фрагмент кода, который ищет \n или конец строки.

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

Оптимизация и анализ «смотреть в окошко»

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

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

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

/foo(\w+)bar/

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

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

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

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

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

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

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

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

Ещё одна оптимизация — «слияние EXACT», где два последовательных узла EXACT объединяются в один regop. Ещё более агрессивный вариант — это преобразование последовательности ветвей вида EXACT BRANCH ... EXACT в regop TRIE-EXACT. Всё это происходит в процедуре 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 — основной «рекурсивный цикл» интерпретатора. В основном это гигантское операторное выражение case, которое реализует автомат, где возможные состояния — это сами regops, плюс ряд дополнительных промежуточных и состояний ошибки. Несколько состояний реализованы в виде подпрограмм, но основная часть — это встроенный код.

РАЗНОЕ

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

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

Как бы вы ни посмотрели на это, поддержка Unicode будет проблемой для движка регулярных выражений. Приёмы, которые могут быть хороши при наличии 256 возможных символов, часто не масштабируются для обработки размера набора символов UTF-8. Вещи, которые вы можете принять как должное при использовании ASCII, могут быть неверными для Unicode. Например, в ASCII можно предположить, что sizeof(char1) == sizeof(char2), но в UTF-8 это не так. Сворачивание регистра Unicode значительно сложнее, чем простые правила ASCII, и даже когда не используется Unicode, а используются только локальные кодировки с одним байтом, вещи могут стать сложными (например, LATIN SMALL LETTER SHARP S (U+00DF, ß) должно соответствовать «SS» в локализованном регистронезависимом поиске).

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

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

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

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

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

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

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

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

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

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

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

Структура Perl's pprivate

Следующая структура используется в качестве структуры 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. Во время компиляции regop, которым требуются специальные структуры, добавляет элементы в каждый массив с помощью функции 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.

ССЫЛКИ

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

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