Простой сопоставитель регулярных выражений

Задача:

Даны регулярное выражение и текст. Нужно проверить допускает ли регулярное выражение данный текст.

Алгоритм

Введем обозначения:

[math]c[/math] — один любой буквенный символ

[math]\ldotp[/math] — один любой символ

[math]\wedge[/math] — символ начала текста

[math]\mathdollar[/math] — символ конца текста

[math]*[/math] — предыдущий символ встречается ноль или более раз

Псевдокод

function match(regexp: char*, text: char*): boolean  / поиск вхождения регулярного выражения в любом месте текста
    if (regexp[0] == '^')
        return matchHere(regexp + 1, text)
    do
        if (matchHere(regexp, text))
            return true
    while (*text++ != '\0')
    return false

function matchHere(regexp: char*, text: char*): boolean / поиск вхождения регулярного выражения в начале текста
    if (regexp[0] == '\0')
        return true
    if (regexp[1] == '*')
        return matchStar(regexp[0], regexp + 2, text)
    if (regexp[0] == '$' and regexp[1] == '\0')
        return *text == '\0';
    if (*text!='\0' and (regexp[0] == '.' or regexp[0] == *text))
        return matchHere(regexp + 1, text + 1)
    return false

function matchStar(c : char, regexp: char*, text: char*): boolean / сопоставление с регулярным выражением вида: c*
    do
        if (matchHere(regexp, text))
            return true
    while (*text != '\0' and (*text++ == c or c == '.'))  /Цикл do-while используется вместо while, так как * допускает пустую строку
    return false

Данный псевдокод использует указатели и арифметические операции над ними из языка C.

Функция [math]\mathrm{match(regexp, text)}[/math] проверяет есть ли вхождение регулярного выражения в любом месте в пределах текста. Если существует более одного вхождения, то найдется самое левое и самое короткое.

Логика функции [math]\mathrm{match}[/math] проста. Если [math]\wedge[/math] — первый символ регулярного выражения, то любое возможное вхождение должно начинаться в начале текста. Т.е. если [math]\wedge[/math][math]abc[/math] — регулярное выражение, то [math]abc[/math] должно входить в текст только с первой позиции текста, а не где-то в середине текста. Это проверяется путем сопоставления остатка регулярного выражения с текстом, начиная с первой позиции и нигде более.

В противном случае регулярное выражение может входить в текст в любой позиции. Это проверяется путем сопоставления регулярного выражения во всех позициях текста. Если регулярное выражение входит более одного раза в текст, то только самое левое вхождение будет распознано. Т.е. если [math]abc[/math] — регулярное выражение, то для него найдется самое левое вхождение в текст.

Основная часть работы сделана в [math]\mathrm{matchHere(regexp, text)}[/math], которая сопоставляет регулярное выражение с текстом в текущей позиции. Функция [math]\mathrm{matchHere}[/math] пытается сопоставить первый символ регулярного выражения с первым символом текста. В случае успеха мы можем сравнить следующий символ регулярного выражения со следующим символом текста, вызвав [math]\mathrm{matchHere}[/math] рекурсивно. Иначе нет совпадения с регулярным выражением в текущей позиции текста.

Рассмотрим возможные случаи:

1. Если в ходе рекурсии регулярное выражение осталось пустым [math](regexp[0] == \backslash0)[/math], то текст допускается этим регулярным выражением.
2. Если регулярное выражение имеет вид [math]c*[/math], то вызывается функция mathchStar, которая пытается сопоставить повторение символа [math]c[/math], начиная с нуля повторений и увеличивая их количество, пока не найдет совпадение с оставшимся текстом. Если совпадение не будет найдено, то регулярное выражение не допускает текст. Текущая реализация ищет "кратчайшее совпадение", которое хорошо подходит для сопоставления с образцом, как в grep, где нужно как можно быстрее найти совпадение. "Наидлиннейшее совпадение" более интуитивно и больше подходит для текстовых редакторов, где найденное заменят на что-то. Большинство современных библиотек для работы с регулярными выражениями предоставляют оба варианта.
3. Если регулярное выражение это [math]\mathdollar[/math], то оно допускает этот текст тогда и только тогда, когда текст закончился.
4. Если первый символ текста совпал с первым символом регулярного выражения, то нужно проверить совпадают ли следующий символ регулярного выражения со следующим символом текста, сделав рекурсивный вызов [math]\mathrm{matchHere}[/math].
5. Если все предыдущие попытки найти совпадения провалились, то никакая подстрока из текста не допускается регулярным выражением.

Данный алгоритм прост и лаконичен, но у него есть недостаток. Для регулярного выражения содержащего несколько [math].*[/math] подряд этот алгоритм может работать очень медленно. Рассмотрим время работы grep'а (наш алгоритм схож со стандартным grep'ом). Например команда: "[math]grep[/math] [math]a.*a.*a.*a.a[/math]" потребует 20 секунд, чтобы обработать текстовой файл размером 4MB на обычной машине. В то же время алгоритм, который конвертирует недетерминированный конечный автомат в детерминированный конечный автомат (например, egrep), потребует менее одной десятой доли секунды на обработку тех же данных.

Модификации

Немного изменим функцию [math]\mathrm{matchStar}[/math] для поиск самого левого и самого длинного вхождения [math]c*[/math]:

1. Найдем максимальную последовательность подряд идущих символов [math]c[/math]. Назовем ее [math]s[/math].
2. Сопоставим часть текста без [math]s[/math] с остатком регулярного выражения.
3. Если части совпали, то текст допускается этим регулярным выражением. Иначе, если [math]s[/math] пусто, то текст не допускается этим регулярным выражением, иначе убираем один символ из [math]s[/math] и повторяем шаг 2.

Псевдокод

function matchStar(c : char, regexp: char*, text: char*): boolean
    char *t
    for (t = text; *t != '\0' and (*t == c or c == '.'); t++)
    do
        if (matchHere(regexp, text))
            return true
    while (*text != '\0' and (*text++ == c or c == '.'))
    return false

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

Псевдокод

struct Token
    type: int  / тип элемента: STAR, QUESTION, PLUS, SYMBOL, ...
    c: char    / сам символ
    cs: char*  / для случая [...]
    ncs: bool  / для случая отрицания cs: [^...]

См. также

• Регулярные языки: два определения и их эквивалентность

Источники информации

• A Regular Expression Matcher