Содержание

• Введение

• Виртуальная Машина Регулярных Выражений

• Интерфейс ВМ на Си

• Реализация на основе рекурсии с возвратом

• Реализация с возвратом без рекурсии

• Реализация Томпсона

• Отслеживание подвыражений

• Реализация Пайка

• Неоднозначность совпадений подвыражений

• Регулярные Выражения в дикой природе

• Отступление: подвыражения в POSIX

• Отступление: забытая техника

• Отступление: “Алгоритм Томпсона”

• Реализации

• Заключение

• Ссылки

---

Введение

Назовите самый используемый интерпретатор байт-кода или виртуальную машину (далее просто ВМ). JVM от SUN? Flash от Adobe? .NET и Mono? Perl? Python? PHP? Все они без сомнения популярны, но есть ещё одна ВМ, которая используется шире, чем все предыдущие вместе взятые. Этот интерпретатор байт-кода - библиотека регулярных выражений от Генри Спенсера (Henry Spencer) и её многочисленные наследники.

Первая статья из этой серии описывала два главных подхода к реализации поиска по регулярным выражениям: подход на основе конечных автоматов с линейной сложностью в худшем случае, который использовался в awk и egrep (а сейчас в большинстве реализаций grep); и подход на основе алгоритма с возвратом (бэктрекинг) с экспоненциальной сложностью в худшем случае, который используется почти везде, включая ed, sed, Perl, PCRE и Python.

Данная статья представляет эти два подхода как два разных пути реализации ВМ, которая выполняет регулярное выражение, которое было скомпилировано в байт-коды для поиска текста. Это похоже на .NET и Mono, которые являются разными способами реализовать ВМ, которая исполняет скомпилированную в CLI байт-коды программу.

Рассматривая поиск по регулярным выражениям, как работу специального устройства, мы получаем возможность добавлять новые возможности просто через добавление (и реализацию!) новых инструкций. В частности, мы можем добавить инструкции для работы с подвыражениями (submatching) таким образом, чтобы после сопоставления выражения со строкой aabbbb, программа могла понимать, что часть (на которую часто ссылаются через \1 или $1) соответствует строке aa, а часть соответствует строке bbbb. Сопоставление подвыражений может быть реализовано как для ВМ с возвратом (бэктрекингом), так и для ВМ на основе автоматов. (Код, реализующий это, датируется 1985 годом, но мне верится, что данная статья является первым написанным объяснением его работы.)

Виртуальная Машина Регулярных Выражений

Для начала мы определим виртуальную машину регулярных выражений (прямо как ВМ Java). ВМ исполняет один или более потоков, каждый из который выполняет программу регулярного выражения, которая представляет собой просто последовательность инструкций регулярного выражения. Каждый поток в процессе работы управляет двумя регистрами: PC (program counter - счётчик инструкций) и SP (string pointer - указатель на позицию входной строки).

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

• char c. Если символ, на который указывает регистр SP, отличается от c, то ВМ останавливает исполнение потока: произошла ошибка сопоставления. В противном случае инкрементируется значение SP (перейти к следующей позиции во входной строке) и инкрементируется значение PC (перейти к следующей инструкции).

• match. Остановить исполнение данного потока: найдено совпадение.

• jmp x. Перейти (jump - прыгнуть) к инструкции в позиции x (регистр PC после этого указывает на инструкцию x).

• split x, y. Расщепить (Split) исполнение: продолжить исполнение с инструкций по позициям x и y. Создаётся новый поток, для которого значение в регистре SP копируется из текущего потока. Один поток продолжает исполнение, начиная инструкции x. Другой поток продолжает исполнение, начиная с инструкции y. (Это подобно переходу к одновременному выполнению двух разных инструкций.)

ВМ начинает работу с исполнения одиночного потока, запущенного со значением в PC, указывающим на начало программы, и со значением SP, указывающим на начало входной строки. В процессе работы ВМ выполняет инструкцию, на которую указывает регистр PC потока. Выполнение этой инструкции меняет регистр PC, передвигая его к следующей инструкции. Процесс повторяется пока поток не остановится (по ошибке сопоставления или по совпадению). Строка соответствует регулярному выражению, если любой из потоков нашёл совпадение (достиг инструкции match).

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

• одиночный символ ,

• соединение по И (конкатенация)

• соединение по ИЛИ (операция выбора)

• повторение (нуль-или-одно), (нуль-или-более), (одно-или-более).

Одиночный символ компилируется в одиночную инструкцию char a. Конкатенация соединяет по И два скомпилированных подвыражения. Соединение по ИЛИ использует инструкцию split для того, чтобы осуществить выбор. Нуль-или-одно повторение использует инструкцию split, компилируя соединение по ИЛИ с пустой строкой. Повторения нуль-или-более () и одно-или-более () так же используют инструкцию split, чтобы выбрать либо сопоставление с выражением e, либо остановку проверки повторения.

Точные последовательности кода следующие:

char a

<codes for e1>
<codes for e2>

split L1, L2
L1: <codes for e1>
    jmp L3
L2: <codes for e2>
L3:

    split L1, L2
L1: <codes for e>
L2:

L1: split L2, L3
L2: <codes for e>
    jmp L1
L3:

L1: <codes for e>
    split L1, L3
L3:

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

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

0 char a
1 split 0, 2
2 char b
3 split 2, 4
4 match

Когда происходит сопоставление со строкой aab, реализация ВМ может исполнять программу следующим образом:

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

Интерфейс ВМ на Си

Остаток этой статьи посвящён серии реализаций ВМ, иллюстрируемых кодом на Си. Программа регулярного выражения представлена в виде массива структур Inst, определённых на Си следующим образом:

enum {    /* Inst.opcode */
    Char,
    Match,
    Jmp,
    Split
};

struct Inst {
    int opcode;
    int c;
    Inst *x;
    Inst *y;
};

Этот байт-код почти идентичен представлению НКА в виде графа переходов из первой статьи. Мы можем рассматривать байт-код в качестве закодированного в машинные инструкции графа переходов НКА. Или же мы можем рассматривать граф переходов НКА в качестве графа потока управления (control-flow) байт-кода. Каждое представление облегчает понимание различных аспектов. Что бы ни было из этого первичным, эта статья сосредотачивает внимание на представлении регулярных выражений в виде машинных инструкций.

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

int implementation(Inst *prog, char *input);

Реализация на основе рекурсии с возвратом

Простейшая возможная реализация ВМ вообще не моделирует работу потоков напрямую. Вместо этого, когда требуется запустить новый поток, происходит рекурсивный вызов, используя преимущество того факта, что параметры prog и input дублируют изначальные значения регистров PC и SP самого первого потока.

int
recursive(Inst *pc, char *sp)
{
    switch(pc->opcode){
    case Char:
        if(*sp != pc->c)
            return 0;
        return recursive(pc+1, sp+1);
    case Match:
        return 1;
    case Jmp:
        return recursive(pc->x, sp);
    case Split:
        if(recursive(pc->x, sp))
            return 1;
        return recursive(pc->y, sp);
    }
    assert(0);
    return -1;  /* not reached */
}

Вышеприведённая версия очень рекурсивная, и должна быть комфортной для программистов, хорошо знакомых с такими языками, как Lisp, ML и Erlang, которые широко используют рекурсию. Большинство компиляторов Си оптимизируют выражение return recursive(...);, превращая её в переход к началу функции (т.н. оптимизация хвостовой рекурсии), так что всё это компилируется во что-то вроде следующего кода, в котором имеется явный цикл:

int
recursiveloop(Inst *pc, char *sp)
{
    for(;;){
        switch(pc->opcode){
        case Char:
            if(*sp != pc->c)
                return 0;
            pc++;
            sp++;
            continue;
        case Match:
            return 1;
        case Jmp:
            pc = pc->x;
            continue;
        case Split:
            if(recursiveloop(pc->x, sp))
                return 1;
            pc = pc->y;
            continue;
        }
        assert(0);
        return -1;  /* not reached */
    }
}

Заметим, что этой версии всё ещё нужен один (не хвостовой) рекурсивный вызов в случае инструкции Split, чтобы проверить pc->x перед проверкой pc->y.

Эта реализация является сутью оригинальной библиотеки от Генри Спенсера, а так же реализаций с возвратом в Java, Perl, PCRE, Python, и оригинальных ed, sed и grep. Она работает очень быстро, когда выполняется возврат на небольшую глубину, но значительно замедляется, когда необходимо проверить множество возможных вариантов, как мы видели в предыдущей статье.

Конкретно эта реализация с возвратом имеет один недостаток, которого обычно нет в настоящих продакшн реализациях: регулярные выражения вроде могут вызывать бесконечные циклы в скомпилированной программе, и эта реализация ВМ не определяет их. На самом деле, эту проблему легко решить (детали далее в этой статье), но т.к. мы не фокусируемся на возврате, мы просто её игнорируем.

Реализация с возвратом без рекурсии

Рекурсивная реализация с возвратом исполняет один поток до тех пор, пока он не завершится, и затем запускает потоки в порядке, обратным их созданию (первыми запускаются самые новые потоки). Потоки, ожидающие запуска, не закодированы явным образом: вместо этого они представлены неявно в виде значений регистров PC и SP, сохранённых в стеке вызовов, когда код выполняет рекурсию. Если потоков, ожидающих выполнения, становится слишком много, стек вызовов функций на Си может переполниться, вызывая проблемы, которые отладить гораздо труднее, чем проблему с производительностью. Проблема чаще всего возникает в процессе обработки повторений типа , которые создают новые потоки после каждого символа (подобно тому, как происходило в случае из примера выше). Это серьёзная проблема в многопоточных программах, в которых часто размер стека ограничен, и нет аппаратной проверки его переполнения.

Мы можем избежать переполнения стека вызовов функций на Си, явно управляя стеком потоков. Для начала, мы определим структуру Thread и функцию thread, которая является простым конструктором для этой структуры:

struct Thread {
    Inst *pc;
    char *sp;
};

Thread thread(Inst *pc, char *sp);

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

int
backtrackingvm(Inst *prog, char *input)
{
    enum { MAXTHREAD = 1000 };
    Thread ready[MAXTHREAD];
    int nready;
    Inst *pc;
    char *sp;

    /* начальный поток помещается в очередь */
    ready[0] = thread(prog, input);
    nready = 1;
    
    /* запускаются потоки по очереди из стека */
    while(nready > 0){
        --nready;  /* выталкивается состояние для запуска следующего потока */
        pc = ready[nready].pc;
        sp = ready[nready].sp;
        for(;;){
            switch(pc->opcode){
            case Char:
                if(*sp != pc->c)
                    goto Dead;
                pc++;
                sp++;
                continue;
            case Match:
                return 1;
            case Jmp:
                pc = pc->x;
                continue;
            case Split:
                if(nready >= MAXTHREAD){
                    fprintf(stderr, "regexp overflow");
                    return -1;
                }
                /* queue new thread */
                ready[nready++] = thread(pc->y, sp);
                pc = pc->x;  /* продолжается выполнение текущего потока */
                continue;
            }
        }
    Dead:;
    }
    return 0;
}

Эта реализация ведёт себя так же, как и recursive и recursiveloop реализации. Но просто не использует стек вызовов Си. Сравним два случая с инструкцией Split:

/* recursiveloop */
case Split:
    if(recursiveloop(pc->x, sp))
        return 1;
    pc = pc->y;
    continue;

/* backtrackingvm */
case Split:
    if(nready >= MAXTHREAD){
        fprintf(stderr, "regexp overflow");
        return -1;
    }
    /* создаётся новый поток и помещается в очередь */
    ready[nready++] = thread(pc->y, sp);
    pc = pc->x;  /* продолжается выполнение текущего потока */
    continue;

Возврат всё ещё присутствует, но код backtrackingvm обязан явно делать то, что реализация с recursiveloop делала неявно: сохранять значения регистров PC и SP, которые будут использоваться после рекурсии так, чтобы с ними можно было бы проверить строку на совпадение, если текущий поток завершится с ошибкой сопоставления. Явное управление даёт возможность добавить проверку на переполнение.

Реализация Томпсона

Рассматривая поиск по регулярным выражениям в виде запущенных потоков внутри ВМ, мы можем представить альтернативную формулировку алгоритма Кена Томпсона (Ken Thompson), описанного в первой статье, которая ближе к машинному коду Томпсона для PDP-11.

Томпсон заметил, что возврат требует многократного сканирования отдельных частей входной строки. Чтобы этого избежать, он написал реализацию ВМ, которая запускала все потоки в lock step режиме: все потоки сначала обрабатывали первый символ строки, затем все потоки обрабатывали второй, и так далее. Это возможно благодаря тому, что вновь создаваемые потоки никогда не заглядывали назад по строке, поэтому их можно синхронизировать с существующими потоками.

Поскольку все потоки выполняются в lock step режиме, у них всех одно и тоже значение для указателя на строку, так что больше не было необходимости сохранять регистр SP в качестве части состояния потока:

struct Thread
{
    Inst *pc;
};
Thread thread(Inst *pc);

В нашем фреймворке реализация Томпсона имеет следующий вид:

int
thompsonvm(Inst *prog, char *input)
{
    int len;
    ThreadList *clist, *nlist;
    Inst *pc;
    char *sp;
    
    len = proglen(prog);  /* # of instructions */
    clist = threadlist(len);
    nlist = threadlist(len);

    addthread(clist, thread(prog));
    for(sp=input; *sp; sp++){
        for(i=0; i<clist.n; i++){
            pc = clist.t[i].pc;
            switch(pc->opcode){
            case Char:
                if(*sp != pc->c)
                    break;
                addthread(nlist, thread(pc+1));
                break;
            case Match:
                return 1;
            case Jmp:
                addthread(clist, thread(pc->x));
                break;
            case Split:
                addthread(clist, thread(pc->x));
                addthread(clist, thread(pc->y));
                break;
            }
        }
        swap(clist, nlist);
        clear(nlist);
    }
}

Допустим, что запускается программа регулярного выражения, состоящая из инструкций. Поскольку состояние потока состоит только из счётчика инструкций, возможно запустить только различных потоков, которые могут появиться в списке clist или nlist. Если функция addthread не добавляет поток в список, потому что идентичный (с таким же значением PC) поток уже в нём находится, то под списки с типом ThreadList требуется место лишь под возможных потоков, что исключает возможность переполнения.

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

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

Не так уж и редко приходится искать в мегабайтной строке текста совпадение с 20-байтным регулярным выражением. В таком случае, при n, равным самое большее, в 40, результирующее значение может достигать 40 миллионов. (А по сегодняшним меркам, мегабайт текста - это совсем мелочь!) Преимущество подхода Томпсона в том, что поскольку потоки выполняются в lock step режиме, то можно получить только запущенных потоков в любой момент времени. Этот подход значительно уменьшает накладные расходы (bookkeeping overhead), делая их независящими от длины текста.

Отслеживание подвыражений

Обращение с регулярными выражениями, как со скомпилированным байт-кодом, облегчает добавление новых возможностей, таких как отслеживание (трекинг) подвыражений, путём объявления новых инструкций и их реализации.

Чтобы добавить трекинг подвыражений, мы добавим в состояние потока массив сохранённых указателей на строку. Новая байт-кодовая инструкция save i сохраняет текущий указатель на строку в -ый слот массива текущего потока. При компиляции выражения , которое сохраняет границы для подвыражения , мы добавляем инструкции save вокруг кода для . Для -го набора круглых скобок ($k в нотации Perl) мы будем использовать слот 2*k для сохранения начальной позиции и слот 2*k + 1 для сохранения конечной позиции.

Для примера сравним скомпилированные выражения и :

0   char a
1   split 0, 2
2   char b
3   split 2, 4
4   match

0   save 2
1   char a
2   split 1, 3
3   save 3
4   save 4
5   char b
6   split 5, 7
7   save 5
8   match

Если мы хотим найти границы общего совпадения, мы можем обернуть сгенерированный байт-код в инструкции save 0 и save 1.

Реализация инструкции save в функции recursiveloop достаточно проста (saved[pc->i]=sp), за исключением того, что присвоение нужно откатить, если сопоставление завершилось ошибкой. Этим удачный поток изолируется от потоков, сопоставление в которых завершилось неудачей.

int
recursiveloop(Inst *pc, char *sp, char **saved)
{
    char *old;

    for(;;){
        switch(pc->opcode){
        case Char:
            if(*sp != pc->c)
                return 0;
            pc++;
            sp++;
            break;
        case Match:
            return 1;
        case Jmp:
            pc = pc->x;
            break;
        case Split:
            if(recursiveloop(pc->x, sp, saved))
                return 1;
            pc = pc->y;
            break;
        case Save:
            old = saved[pc->i];
            saved[pc->i] = sp;
            if(recursiveloop(pc+1, sp, saved))
                return 1;
            /* restore old if failed */
            saved[pc->i] = old;
            return 0;
        }
    }
}

Заметьте, что в ветке Save присутствует неизбежная рекурсия, прямо как в случае Split. Рекурсию с Save труднее скомпилировать, чем рекурсию со Split: для адаптации инструкции Save в реализации backtrackingvm требуется больше усилий. Разница в прилагаемых усилиях - одна из причин, почему можно предпочесть подход с рекурсией даже не смотря на возможные проблемы с переполнением стека.

Реализация Пайка

В реализации с потоками, подобной thompsonvm, приведённой выше, мы просто сделали набор указателей частью состояния потока. Роб Пайк (Rob Pike) впервые использовал этот подход в текстовом редакторе sam.

struct Thread
{
    Inst *pc;
    char *saved[20];  /* $0 through $9 */
};
Thread thread(Inst *pc, char **saved);

int
pikevm(Inst *prog, char *input, char **saved)
{
    int len;
    ThreadList *clist, *nlist;
    Inst *pc;
    char *sp;
    Thread t;
    
    len = proglen(prog);  /* # of instructions */
    clist = threadlist(len);
    nlist = threadlist(len);

    addthread(clist, thread(prog, saved));
    for(sp=input; *sp; sp++){
        for(i=0; i>clist.n; i++){
            t = clist.t[i];
            switch(pc->opcode){
            case Char:
                if(*sp != pc->c)
                    break;
                addthread(nlist, thread(t.pc+1, t.saved));
                break;
            case Match:
                memmove(saved, t.saved, sizeof t.saved);
                return 1;
            case Jmp:
                addthread(clist, thread(t.pc->x, t.saved));
                break;
            case Split:
                addthread(clist, thread(t.pc->x, t.saved));
                addthread(clist, thread(t.pc->y, t.saved));
                break;
            case Save:
                t.saved[t->pc.i] = sp;
                addthread(clist, thread(t.pc->x, t.saved));
                break;
            }
        }
        swap(clist, nlist);
        clear(nlist);
    }
}

Код в ветке Save в реализации pikevm проще, чем в реализации recursiveloop, потому что у каждого потока своя сохранённая копия и нет необходимости восстанавливать старое значение.

В ВМ от Томпсона функция addthread могла ограничивать размер списка с потоками до значения , соответствующего длине скомпилированной программы, держа только по одному потоку на каждое возможное значение регистра PC. В ВМ от Пайка состояние потока больше - оно включает в себя так же указатели на сохранённые границы подвыражений, но функция addthread всё ещё может поддерживать ограничение в один поток на каждое возможное значение регистра PC. Это обусловлено тем, что сохранённые указатели не влияют на ход исполнения в будущем, а только записывают результат прошлого исполнения. Два потока с одинаковым значением PC будут исполняться идентичным образом, даже если у них разные значения в сохранённых указателях. Таким образом достаточно хранить по одному потоку на каждое возможное значение PC.

Неоднозначность совпадений подвыражений

Иногда есть больше одного способа сопоставить строку с регулярным выражением. В качестве простого примера возьмём поиск выражения

в строке <html></html>. Должен ли найтись только фрагмент <html> или вся строка <html></html> целиком? Или другими словами, должно ли выражение найти просто html или html></html? В Perl, стандарте де-факто для реализаций регулярных выражений, происходит второе. В этом смысле оператор является "жадным": он находит столько, сколько может, сохраняя общее совпадение.

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

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

Точные последовательности кода следующие:

Жадные операторы (такие же, как были приведены выше)

    split L1, L2
L1: <codes for e>
L2:

L1: split L2, L3
L2: <codes for e>
    jmp L1
L3:

L1: <codes for e>
    split L1, L3
L3:

Нежадные операторы

    split L2, L1
L1: <codes for e>
L2:

L1: split L3, L2
L2: <codes for e>
    jmp L1
L3:

L1: <codes for e>
    split L3, L1
L3:

Реализации с возвратом, которые даны выше, уже приоритезируют результаты инструкции split тем способом, который определён выше, подтверждая тот факт, что они (реализации) требуют меньше усилий. Реализации recursive и recursiveloop просто проверяют результат pc->x перед проверкой pc->y.

/* recursive */
case Split:
    if(recursive(pc->x, sp))
        return 1;
    return recursive(pc->y, sp);

/* recursiveloop */
case Split:
    if(recursiveloop(pc->x, sp))
        return 1;
    pc = pc->y;
    continue;

Реализация backtrackingvm создаёт новый поток для низкоприоритетного pc->y и продолжает исполнение текущего потока с инструкции pc->x:

/* backtrackingvm */
case Split:
    if(nready >= MAXTHREAD){
        fprintf(stderr, "regexp overflow");
        return -1;
    }
    /* queue new thread */
    ready[nready++] = thread(pc->y, sp);
    pc = pc->x;  /* continue current thread */
    continue;

Поскольку потоки обрабатываются в стеке (LIFO - Last In, First Out), поток для pc->y не будет исполняться до тех пор, пока все потоки, созданные pc->x не будут проверены и не завершатся ошибкой. Все эти потоки имеют более высокий приоритет, чем поток pc->y.

Представленная выше реализация pikevm не полностью поддерживает приоритеты потоков, но её можно поправить. Чтобы сделать это, мы добавляем в функцию addthread обработку инструкций jmp, split и save с помощью рекурсивного вызова. При этом вместо этих инструкций добавляется их цель. (Это делает addthread почти идентичной функции addstate из предыдущей статьи.) Это изменение позволяет убедиться, что списки clist и nlist обрабатываются в порядке приоритета потоков, от наивысшего к наименьшему. Таким образом в основном цикле pikevm проверяются потоки в порядке приоритета, а агрессивная функция addthread гарантирует, что все потоки, созданные с определённым приоритетом, добавляются в nlist перед потоками с приоритетом следующего уровня.

Изменения в pikevm мотивированы тем, чтобы рекурсия соблюдала приоритет потоков. Новый код использует рекурсию при обработке одиночного символа так, чтобы nlist заполнялся в порядке приоритета, но потоки всё ещё обрабатываются в lock step режиме для того, чтобы поддерживать хорошее поведение в плане производительности. Поскольку nlist теперь заполняется в порядке приоритетов, эвристика "игнорировать поток, если потоки с таким PC уже есть" всё ещё безопасна: поток, встреченный ранее, имеет более высокий приоритет и его необходимо оставить.

В реализации pikevm требуется больше одного изменения: если совпадение найдено, потоки, которые встретятся позднее в списке clist (более низкоприоритетные) должны быть удалены, но потоки с более высоким приоритетом должны получить шанс на проверку более длинного совпадения. Новый основной цикл в pikevm выглядит следующим образом:

for(i=0; i<clist.n ;i++){
    pc = clist.t[i].pc;
    switch(pc->opcode){
    case Char:
        if(*sp != pc->c)
            break;
        addthread(nlist, thread(pc+1), sp+1);
        break;
    case Match:
        saved = t.saved;  // save end pointer
        matched = 1;
        clist.n = 0;
        break;
    }
}

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

Реализация может использовать другие критерии для отсева набора потоков, напрямую сравнивая множества совпадений с подвыражениями. Библиотека регулярных выражений восьмой редакции Unix использует в качестве такого критерия самое крайнее положение самого длинного совпадения, чтобы моделировать поведение инструментов на основе ДКА, таких как awk и egrep.

Регулярные выражения в реальном мире

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

Символьные классы (character classes). Символьные классы обычно реализуются через специальную инструкцию ВМ, а не через разворачивание их в последовательность соединений по ИЛИ. Пример кода, доступный по ссылке, реализует частный случай, используя инструкцию "любой байт" для метасимвола (точка).

Повторения (repetition). За повторениями часто следует символ, который в них не входит. Например, в выражении , первое подвыражение должно оканчиваться на нецифровой символ. Тут можно ввести в использование заглядывание (look ahead) на один байт вперёд для того, чтобы избавиться от накладных расходов на создание новых потоков в процессе обработки повторений. Этот приём наиболее часто можно увидеть в реализациях с возвратом, в которых иначе бы пришлось создавать по одному новому потоку на каждый символ. Если же потоки реализованы через рекурсию, тогда эта оптимизация просто необходима, чтобы избежать переполнения стека на простых выражениях.

Циклы в процесс возврата (backtracking loops). В начале статьи мы отметили, что наивная реализация алгоритма с возвратом может уходить в бесконечный цикл при поиске по выражению из-за повторяющегося пустого совпадения. Простой способ избежать таких циклов в процессе возврата - добавить инструкцию progress. Эта инструкция заставляет ВМ продвигаться вперёд.

Изменение структур программы для возврата. Другим способом избежать циклов являются изменения в наборе инструкций путём добавления инструкций для повторений. Реализация этих инструкций может вызывать участки регулярного выражения (subpieces) как подфункции (subroutines), что позволяет избежать проблемы с бесконечным циклом и делает более эффективным реализацию таких возможностей, как считанные повторения (counted repetition, определённое количество повторений) и утверждения (assertions, позиционные проверки). Не смотря на это, эти изменения сильно усложняют нерекурсивные реализации (в состоянии нужно хранить больше данных, а не просто "старый" указатель) и исключает использование техник с конечными автоматами, которые лежат в основе реализации ВМ от Пайка. Однако такая реализация может легко выйти из под контроля: достаточно взглянуть на Perl, PCRE или другую реализацию регулярных выражений с полным набором возможностей (full-featured).

Обратные ссылки (backreferences). Обратные ссылки являются тривиальными для реализаций с возвратом. Они могут адаптированы для ВМ от Пайка, за исключением того, что утверждение насчёт отбрасывания потоков с одинаковым значением регистра PC больше недействительно: два потока с одинаковым значением PC могут иметь различный набор групп захвата, и теперь эти группы захвата могут влиять на будущее исполнение. Так что реализации приходится хранить информацию обоих потоков, что может привести к экспоненциальному взрыву количества состояний. GNU grep комбинирует оба подхода: он переписывает обратные ссылки в примерное регулярное выражение, которое может быть использовано с ДКА (например (cat|dog)\1 превращается в выражение (cat|dog)(cat|dog), которое имеет более широкий охват, нежели оригинальное); а затем, после нахождения общего совпадения через ДКА, может быть проверено с помощью техники с возвратом.

Неякорный поиск (unanchored match). Для реализации неякорного поиска многие реализации сначала ищут совпадение в позиции 0, потом в позиции 1 и так далее. Если движок регулярных выражений сканирует входящий текст до самого конца не находит совпадения, то заключая такую проверку в цикл, мы получаем квадратичную от длины строки сложность. В реализациях на основе ВМ более эффективным способом является добавление скомпилированного выражения в начало программы. Это позволяет реализовать неякорный поиск в самой ВМ за один проход с линейной сложностью по времени.

Кодировки символов. Так как ВМ от Томпсона и Пайка работают в посимвольном режиме, никогда не возвращаясь назад и не имеют таблиц, размер которых пропорционален размеру набора символов, то легко поддерживать альтернативные кодировки и наборы символов, даже UTF-8: надо только декодировать очередной символ в цикле диспетчеризации перед выполнением очередного шага. Эти ВМ обладают тем свойством, что они декодируют каждый символ только один раз, что очень хорошо, когда декодирование является сложным (декодирование UTF-8 не ужасно затратное, но и не является просто разыменованием одиночного указателя).

Отступление: Подвыражения в POSIX

Комитет POSIX решил, что правила Perl для разрешения неоднозначности подвыражений были слишком сложны для объяснения, так что были выбраны новые правила, которые были проще в изложении, но оказались сложнее в реализации. (Так же эти правила оказались не совместимы с другими уже существующими реализациями регулярных выражений, и через них оказалось невозможно определить нежадные операторы, так что почти никто их не использует.) Излишне говорить, что правила POSIX не прижились.

POSIX определяет разрешение подвыражений следующим образом: первым выбирается совпадение, которое начинается в крайней слева позиции в строке (ближе к началу). (Это традиционное поведение в Perl, но далее начинаются различия.) Среди этих совпадений, начинающихся в крайней слева позиции в строке, выбирается самое длинное в целом. Если же всё ещё есть на выбор несколько вариантов, выбирается тот, который максимизирует длину следующего элемента регулярного выражения. И так далее. В реализациях на основе НКА это требует добавления дополнительных круглых скобок вокруг каждого выражения с конкатенацией различной длины. Затем можно объединить два потока, выбрав из них "лучший" согласно правилам POSIX. Кроме того, есть ещё правила для повторений: POSIX oпределяет, что представляет собой , где первый элемент максимально длинный, затем второй, и так далее. Возможно выдумать примеры, которые показывают, что НКА для корректного объединения потоков должен отдельно отслеживать каждое возможное в повторении. По этой причине объём состояния каждого потока, требуемый для поиска по регулярному выражению в прямом направлении, описанного указанным выше способом, потенциально не ограничен.

Например, когда происходит сопоставление строки abcdefg с выражением , то есть три возможных способа разбить строку по оператору :

• a bcdef g

• ab c d efg

• ab c d e fg

В Perl соединение по ИЛИ отдаёт предпочтение ранее указанным альтернативам, выбирая первый вариант разбиения: на первой итерации выбирается не ab, а a, потому что идёт первым. И поэтому записанным подвыражением для этих скобок оказывается g (после окончания поиска). В POSIX повторение отдаёт предпочтение самому длинному совпадению на каждом шаге, что приводит к выбору второго варианта разбиения: на первой итерации выбирается ab, а не a, а потом на четвёртой итерации выбирается efg, а не e. И таким образом записанным подвыражением для этих скобок оказывается efg. Глен Фаулер (Glenn Fowler) написал набор тестов для семантики регулярных выражений POSIX, а Крис Куклевич (Chris Kuklewicz) написал ещё более полный набор тестов, который находит ошибки в большинстве реализаций.

Чтобы избежать кажущегося неограниченным в пространстве трекинга подвыражений, подразумеваемого семантикой POSIX, есть два способа. Во-первых, оказывается, что сопоставление по регулярному выражению в обратном направлении ограничивает объём трекинга до линейной сложности от размера регулярного выражения. Эта программа демонстрирует данный приём. Во-вторых, Крис Куклевич обнаружил, что возможно исполнять автомат в прямом направлении в ограниченном объёме памяти, когда периодически сравниваются данные всех потоков и заменяются данные подвыражения, которые использовались бы в случае коллизии, согласно приоритету для каждого потока (от 1 до ). Его пакет regex-tdfa для языка Haskell реализует данный приём.

Отступление: Забытая Техника

Самой интересной техникой в данной статье является приём с сохранением информации о подвыражениях в состоянии потока регулярного выражения. Самое раннее применение этого приёма, о котором я знаю, было в движке регулярных выражений редактора sam от Роба Пайка, написанного около 1985 года. (Изменения для хранения подвыражений были внесены Брюсом Янсоном (Bruce Janson) через пару лет после первоначальной реализации.). Техника так же встречается в книге 1974 года, но затем, судя по всему, теряется до своего нового появления в sam.

В книге Ахо (Aho), Хопкофта (Hopcroft) и Ульмана (Ullman) "Создание и анализ компьютерных алгоритмов (The Design and Analysis of Computer Algorithms)" 1974 глава 9 называется "Алгоритмы поиска по образцу (Pattern Matching Algorithms)". В ней есть два интересных упражнения:

9.6. Пусть является заданной строкой, а - регулярным выражением. Измените Алгоритм 9.1 [Моделирование работы НКА] так, чтобы найти такое наименьшее , при котором существуют наименьшее (а) и наибольшее (б), такие, при которых строка принадлежит множеству, описываемому с помощью . [Подсказка: каждому состоянию в соответствует число ].

*9.7 Пусть и такие же, как в Упражнении 9.6. Измените Алгоритм 9.1 таким образом, чтобы найти наименьшее , при котором существует наибольшее , такое, что строка принадлежит множеству, описываемому с помощью .

В Упражнении 9.6 необходимо найти самое короткое совпадение среди тех, что заканчиваются в самой ранней возможной позиции в строке. В Упражнении 9.7 необходимо найти самое длинное совпадение среди тех, что начинаются в самой ранней возможной позиции в строке - теперь уже являющийся стандартным подход "самое первое самое длинное" совпадение. На самом деле приведённый ранее в главе текст (в разделе 9.2) практически не даёт ответа:

На основе Алгоритма 9.1 можно построить различные алгоритмы распознавания по образцу. Например, предположим, что дано регулярное выражение и текстовая строка , и необходимо найти такое наименьшее , при котором существует , и принадлежит множеству, описываемому с помощью . Используя Теорему 9.2 [Преобразование регулярных выражений в НКА], можно построить из НКА , который принимает язык . Чтобы найти такое наименьшее , при котором принадлежит , в Алгоритм 9.11 в конец блока строк 2-12 [выполняется после обработки каждого входного символа] мы можем вставить проверку на предмет того, что содержит состояние из множества (конечных состояний). По Теореме 9.2 мы можем считать, что является синглтоном, поэтому эта проверка не требует больших затрат времени: она выполняется за , где - количество состояний в . Если содержит состояние из , то происходит выход из основного цикла, так как является кратчайшим префиксом в .

Алгоритм 9.1 можно изменить таким образом, чтобы для каждого находилось наибольшее (или наименьшее ), такое, чтобы принадлежало множеству, описываемому с помощью . Для этого каждому состоянию во множествах назначается целочисленное значение. Это целочисленное значение, назначенное состоянию в , является флагом того, что данное наибольшее (или наименьшее ) является таким, что выполняется условие . Подробности того, как обновляются эти целочисленные значения в Алгоритме 9.1, оставлены в качестве упражнения.

Насколько я могу судить, техника, на которую намекается в данной главе и в упражнении, была забыта до использования в sam. И даже после этого оставалась незамеченной более десятка лет. В частности, ни упражнение, ни техника не упоминаются в более поздних учебниках Ахо, Хопрокфта или Ульмана, а в awk (в котором буква a - это от Ахо) для реализации поиска самых ранних самых длинных совпадений с регулярным выражением используется наивный алгоритм квадратичной сложности "цикл по ДКА".

Отступление: “Алгоритм Томпсона”

В первой статье было написано следующее:

Р. МакНотону (R.McNaughton), Х. Ямаде (H.Yamada) и Кену Томпсону (Ken Thompson) обычно приписывают создание первых конструкций для преобразования р.в. в НКА, даже не смотря на то, что ни одна из работ не упоминает тогда ещё зарождающуюся концепцию НКА. Конструкция МакНотона и Ямады создаёт ДКА, а конструкция Томпсона создаёт машинный код для IBM 7094. Читая между строк можно увидеть скрытые конструкции НКА, лежащие в основе обеих работ.

Было интересно проследить историю того, каким образом алгоритм конструирования НКА оказался приписан двум работам, в которых НКА не упоминается. Единственная отсылка к теории в работе Томпсона приводится в следующем предложении: "В терминах работы Брзозовски (Brzozowski) [1], этот алгоритм непрерывно потребляет левую производную заданного регулярного выражения с учётом текста, в котором производится поиск".

Книга Ахо, Хопкрофта и Ульмана "Создание и анализ компьютерных алгоритмов" (Design and Analysis of computer algorithms) 1974 года впервые приводит алгоритм в терминах автоматов для преобразования регулярного выражения в НКА и алгоритм для последующего исполнения этого НКА. Библиографические заметки в конце главы поясняют следующее: "Алгоритм поиска по образцу с помощью регулярного выражения (the regular expression pattern-matching algorithm) (Алгоритм 9.1) является абстракцией алгоритма Томпсона [1968]."

Книга Ахо и Ульмана "Принципы создания компиляторов" 1977 приводит алгоритм для конвертирования регулярных выражения в НКА без указания авторства. В последующем обсуждении исполнения регулярных выражений написано следующее:

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

Чтобы весь процесс сделать эффективным, мы обязаны уравновесить время, необходимое для обработки шаблона и время, затрачиваемое на поиск. Разумным компромиссом, предложенным Томпсоном [1968], является преобразование регулярного выражения в НКА. Процесс сканирования входного текста заключается в последующем моделировании работы НКА напрямую. По мере сканирования входной строки ведётся список "текущих" состояний, начиная с эпсилон-замыкания начального состояния. Если следующим символом входной строки является a, создаётся новый список всех состояний, в которые есть переход по a из списка старых состояний. Затем старый список отбрасывается, и вычисляется эпсилон-замыкание для нового списка. Если конечное состояние не находится в новом списке, то процесс повторяется для следующего символа входной строки.

Библиографическая заметка так же сообщает: "Томпсон [1968] описал алгоритм распознавания по регулярному выражения, используемый в текстовом редакторе QED".

Книга Ахо, Сети (Sethi) и Ульмана "Компиляторы: Принципы, Техники и Инструменты" (Книга Дракона) 1986 года приводит алгоритм для преобразования регулярного выражения в НКА как "Алгоритм 3.3. (Конструирование по Томпсону (Thompson's construction))". Алгоритм 3.4, "Моделирование работы НКА" приводится без авторства. В библиографических заметках приводится следующее: "Многие текстовые редакторы используют регулярные выражения для контекстного поиска. Томпсон [1968], например, описал алгоритм конструирования НКА из регулярного выражения (Алгоритм 3.3) в контексте работы текстового редактора QED.". Где книга 1974 года ссылается на процесс конструирования как на "абстракцию алгоритма Томпсона", Книга Дракона называет его просто "Конструированием по Томпсону". Эти два алгоритма легко различить. Если заглянуть в машинный код, чтобы разобраться в работе нижележащего НКА, то в работе Томпсона 1968 года используется по одному состоянию НКА на каждый символ, объединение или оператор звёздочки. В противоположность этому, приведённый в Книге Дракона алгоритм использует два состояния на каждый символ, объединение или оператор звёздочки, а затем отбрасывает одно состояние при соединении состояний (приведённый алгоритм в книге 1974 такой же, за исключением отсутствия оптимизации при соединении состояний). Введение всех этих дополнительных состояний делает доказательства проще, но в практических реализациях может удваивать число состояний, которыми нужно управлять. Я нашёл множество работ, в которых используется алгоритм конструирования из Книги Дракона, но при этом цитируется работа Томпсона. Я даже видел работы, в которых "оптимизируется" алгоритм Конструирования по Томпсону путём применения доработанного алгоритма из Книги Дракона, в котором удаляются необязательные состояния.

В книге Ахо и Ульмана "Основы Информатики" (Foundations of Computer Science) 1992 года в главе 10 "Шаблоны, Автоматы и Регулярные Выражения" приводятся теперь уже хорошо знакомые конструкции без указания авторства в основном тексте. При этом библиографические заметки сообщают: "Конструирование недетерминированного автомата из регулярного выражения, которое использовалось в разделе 10.8, взято из работы МакНотона и Ямады [1960]... Использование регулярных выражений, как способа описания шаблонов в строках, впервые появилось в системе QED Томпсона [1968], и те же самые идеи позже повлияли на многие команды в его системе UNIX.". Отсылка к работе МакНотона и Ямады интересна тем, что как и в работе Томпсона, в ней так же нет упоминания об НКА. При этом приводится алгоритм конструирования ДКА из регулярного выражения, и довольно ясно (ретроспективно), что этот ДКА является результатом применения к обычному НКА алгоритма конструирования подмножеств, но при этом сам по себе НКА никогда не упоминается.

В книге Хопкофта, Мотвани (Motwani) и Ульмана "Введение в теорию автоматов, языков и вычислений" (Introduction to Automata Theory, Languages, and Computation) 2001 года так же приводятся знакомые конструкции. Ссылка в главе 3 гласит: "Конструирование эпсилон-НКА из регулярного выражения, приведённое здесь, является 'Конструированием по МакНотону-Ямаде' из работы [McNaughton and Yamada, 1960]... Даже до разработки UNIX, К.Томпсон исследовал использование регулярных выражения в таких командах как grep, и его алгоритм для обработки в таких командах появляется в работе [Thompson, 1968]". В переиздании этой книги 2007 года эта глава осталась без изменений.

В книге Ахо, Лэма (Lam) и Ульмана "Компиляторы: Принципы, Техники и Инструменты (2ое издание)" 2007 года приводится наиболее аккуратная историческая отсылка. Там, где книга 1986 года описывала Алгоритм 3.3 как просто "Конструированием по Томпсону", издание 2007 описывает тот же самый алгоритм (теперь уже Алгоритм 3.23) как "Алгоритм МакНотона-Ямады-Томпсона для конвертирования регулярного выражения в НКА". Далее в разделе Ссылок для главы 3 приводится следующий текст:

МакНотон и Ямада [1960] впервые представили алгоритм для конвертирования регулярного выражения напрямую в конечный автомат. Алгоритм 3.36, описанный в разделе 3.9, был впервые использован Ахо при создании egrep - инструмента UNIX для поиска по регулярным выражениям. Этот алгоритм так же использовался в функциях поиска по регулярным выражениям в awk [Aho, Kernighan и Weinberger, 1988]. Подход с использованием недетерминированного автомата, как промежуточного звена, принадлежит Томпсону [1968]. Более поздняя работа так же содержит алгоритм прямого моделирования работы НКА (Алгоритм 3.22), который использовался Томпсоном в текстовом редакторе QED.

Но в любом случае, подход Брзозовского, процитированный Томпсоном, вышел из употребления и многие годы игнорировался, но в замечательной работе Оуэнса (Owens), Рипи (Reppy) и Тарона (Turon) "Regular-expression derivatives reexamined" (JFP, 19(2), Март 2009го) указывается, что данный подход в языках с хорошей поддержкой манипуляций с символами работает даже лучше, чем автоматы.

Реализации

Для ознакомления с подробной историей ознакомьтесь с предыдущей статьёй. Так же исходные тексты программ для этой статьи доступны по адресу http://code.google.com/p/re1/.

Обзор внутреннего устройства современного движка регулярных выражений на основе алгоритма с возвратом приведён в главе Генри Спенсера "A Regular-Expression Matcher" книги Дейла Шумахера (Dale Schumacher) "Software Solutions In C" (издательство Academic Press, 1994).

Заключение

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

Выражаю благодарность Алексу Хили (Alex Healy) и Крису Куклевичу (Chris Kuklewicz) за полезные обсуждения о семантике подвыражений в Perl и POSIX.

P.S. Если вам понравилась данная статья, вас так же может заинтересовать работа Роберто Иерусалимши (Roberto Ierusalimschy) "A Text Pattern-Matching Tool based on Parsing Expression Grammars", в которой используется похожий подход для сопоставления грамматик.

Следующая статья в серии "Поиск по регулярным выражениям в дикой природе" является туром по production реализациям.

Ссылки

[1] Rob Pike, “The text editor sam,” Software—Practice & Experience 17(11) (November 1987), pp. 813–845. http://plan9.bell-labs.com/sys/doc/sam/sam.html

[2] Ken Thompson, “Regular expression search algorithm,” Communications of the ACM 11(6) (June 1968), pp. 419–422. http://doi.acm.org/10.1145/363347.363387 (PDF)