Как именно ленивые квантификаторы работают в PCRE?

Немного предыстории: я реализую механизм сопоставления регулярных выражений (NFA), и он должен поддерживать режим совместимости с PCRE (я имею в виду, что он должен захватывать подвыражения с теми же смещениями, что и PCRE).

В PCRE testinput1 есть тест, который я не могу полностью понять. Он проверяет ленивые кванторы.

Итак, регулярное выражение

/<a[\s]+href[\s]*=[\s]*          # find <a href=
 ([\"\'])?                       # find single or double quote
 (?(1) (.*?)\1 | ([^\s]+))       # if quote found, match up to next matching
                                 # quote, otherwise match up to next space
/isx

И строка

<a href="abcd xyz pqr" cats

Соответствие PCRE:

<a href="abcd xyz pqr"

и, очевидно, использует ленивый квантификатор.

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

<a href="abcd

который использует отрицательную ветвь условного подшаблона, без ленивых кванторов.

Итак, я ищу объяснение поведения этого PCRE или какие-либо детали / предложения, почему ленивый квантификатор соответствует в этом тесте. Спасибо!

EDIT: я также проверил, как работает библиотека TRE. Это POSIX-совместимый движок NFA. Я немного изменил исходное регулярное выражение в соответствии с синтаксисом TRE:

#include <stdlib.h>
#include <stdio.h>
#include <tre/tre.h>

int main()
{
    regex_t preg;
    const char * regex = "<a[ ]+href[ ]*=[ ]*(?:(')(.*?)'|[^ ]+)";
    const char * string = "<a href='abcd xyz pqr' cats";
    int cflags = REG_EXTENDED;
    int eflags = 0;
    size_t nmatch = 3;
    regmatch_t pmatch[100];

    tre_regcomp(&preg, regex, cflags);
    tre_regexec(&preg, string, nmatch, pmatch, eflags);

    for (int i = 0; i < nmatch; i++) {
        printf("%d: (%d, %d)\n", i, pmatch[i].rm_so, pmatch[i].rm_eo - pmatch[i].rm_so);
    }

    return 0;
}

и вывод (с использованием длины вместо конечных смещений):

0: (0, 22)
1: (8, 1)
2: (9, 12)

Так что предположение о специфическом для PCRE поведении с возвратом, скорее всего, неверно ...


regex nfa
person Valeriy Streltsov    schedule 16.01.2014    source источник
comment
Однажды я совершил ошибку, взглянув на то, как это делается. СТРАШНО! Насколько я понимаю, для полной PCRE требуется модель оценки стека, а не теоретико-автоматная. Наиболее близким к автоматным подходам, вероятно, является механизм RE, используемый в PostgreSQL и Tcl, но это действительно очень сложно.   -  person Donal Fellows    schedule 16.01.2014
comment
Спасибо за быстрый ответ. Но, похоже, это не является специфическим поведением для обратного отслеживания (см. Редактирование) и может быть реализовано с использованием автоматов (хотя я знаю, что TRE не проходит некоторые тесты на соответствие POSIX из репозитория тестовых данных AT&T, и, таким образом, такое поведение может быть ошибкой) .   -  person Valeriy Streltsov    schedule 16.01.2014

Ответы (2)


arrow_upward
1
arrow_downward

Во-первых, я новичок в мире REGEX. Прошу прощения, если этот ответ неверен или я неправильно понял вопрос.

Читая это определение, взятое из этой книги Справочник по регулярным выражениям:

(? (1) then | else) - это условие, которое проверяет, соответствует ли уже первая группа захвата что-либо. Если да, то механизм регулярных выражений пытается найти соответствие. Если группа захвата до сих пор не участвовала в попытке сопоставления, выполняется попытка части else.

  • С этой темой: <a href="abcd xyz pqr" cats

    Первая группа захвата соответствует первому символу ". Итак, ожидаемое поведение - попытка сопоставить тогдашнюю часть. Второй группе захвата в части then удается сопоставить строку abcd xyz pqr с (.*?), и, наконец, часть then удается сопоставить abcd xyz pqr" с (.*?)\1. REGEX может завершиться успешно.

    Таким образом, часть else с ее квантификатором greddy не требуется, на самом деле она не используется. Как будто квантификатора Гредди никогда не существовало.

  • С этой темой: <a href="abcd

    Первая группа захвата соответствует символу ". Теперь части then удается сопоставить строку abcd с (.*?), но она никогда не будет соответствовать последнему символу ", потому что в конце темы нет такого символа. Условие не выполняется.

    Механизм REGEX на этом не останавливается, вы использовали ([\"\'])?, поэтому механизм может повторить попытку, потому что символ " является необязательным и продолжает работать, как если бы первая группа захвата не совпала (действительно, есть обратный путь). Итак, теперь движок достигает условного условия без совпадения для первой группы захвата, выполняется попытка части else, и ему удается сопоставить строку "abcd (символ " не соответствует первой группе захвата из-за возврата, и теперь он соответствует третьей группе захвата в части else) REGEX может завершиться успешно.

PS: Я ради забавы изучаю регулярные выражения, поэтому, вероятно, этот ответ полностью неверен. Ждите лучшего ответа.

person Gooseman    schedule 16.01.2014

arrow_upward
0
arrow_downward

Я не совсем понимаю ваш вопрос здесь, но не жадный квантификатор позволяет искать до первого вхождения шаблона. Используя pcretest, вы также пробуете использовать жадные и нежадные формы для одного и того же ввода.

Нежадная форма:

  re> /<a[\s]+href[\s]*=[\s]*([\"\'])?(?(1)(.*?)\1|([^\s]+))/i
  data> <a href="ab"cd"
    0: <a href="ab"
    1: "
    2: ab

Жадная форма:

 re> /<a[\s]+href[\s]*=[\s]*([\"\'])?(?(1)(.*)\1|([^\s]+))/i
 data> <a href="ab"cd"
    0: <a href="ab"cd"
    1: "
    2: ab"cd
person dark100    schedule 17.01.2014