☰

Есть ли способ выбрать самый короткий матч при чередовании?

tag-icon • tag-icon awk grep regular-expression
Есть ли способ выбрать самый короткий матч при чередовании?

У меня сложилось впечатление, что grep и awk используют машину регулярных выражений NFA (недетерминированную).
Изображение в середине этой страницы оСопоставление регулярных выражений может быть простым и быстрымподтверждают, что это так.

Известно, что реализация NFA может остановиться, когда совпадет первое чередование. Например, эта машина NFA из связанной статьиНапример, рассмотрим NFA для abab|abbb:

введите описание изображения здесь

Который соответствует регулярному выражению, abab|abbbдостигнет состояния соответствия справа со строкой ababbbbпри сопоставлении первого abab. В этой точке он остановится, поскольку дошел до конца, до состояния соответствия (S10). Нет необходимости проверять больше входных данных, даже если abbbвозможно другое сопоставление.

То есть, в этом коде:

echo 'catfish' | grep -Eo 'cat|catfish'

Результат должен быть, catно он есть catfish. Неважно, если поменять местами чередование, результат тот же.

Что заставляет движок регулярных выражений grep всегда находить самое длинное совпадение?

И возможно ли изменить это значение по умолчанию?

решение1

Я не думаю, что есть способ сделать это с помощью POSIX-совместимого grepили awk, поскольку стандарт действительно требует максимально длинного совпадения (см., например, regex(7)страницу руководства).

С помощью awkвы можете получить желаемый результат, изменив awkпрограмму и регулярное выражение, например

echo 'SetValue' | awk '{ if (match($0, /Set(Value)?/)) { print substr($0, RSTART, 3); }

В этой ситуации я бы воспользовался pcregrep(частью библиотеки регулярных выражений, совместимой с pcre perl), которая позволяет указать пронумерованную подгруппу с помощью -o:

echo SetValue | pcregrep -o1 '(Set)(Value)?'

или, поскольку pcre имеет синтаксис для нежадного сопоставления,

echo SetValue | pcregrep -o0 'Set(Value)??'

решение2

Насколько я могу понять, оказывается, что на самом деле существуютдве машины NFA:

  • Традиционный движок NFA
    Машина NFA, которая откатывается назад и для которойсамое длинное совпадение слева не всегда можно было учесть.

  • POSIX NFA-движок
    Невозвратный NFA-движок, который обрабатывает все состояния параллельно и может выбирать любое совпадение во входной строке. Выбор самого левого, самого длинного совпадения является требованием POSIX.

Однако машина обратного отслеживания DFA (Perl), которая можетвзорваться экспоненциально (2^n)управляется текстом (а не регулярным выражением) и может выбрать первый элемент из чередования (или нет).

Также говорят, чтоDFA распознает все возможные совпадения параллельно.

И, по словам автора статьи, ссылка на которую содержится в вопросе,Реализация re2 определяет чередование как: x|y ==> x или y (предпочтительно x), то есть: предпочесть первое из чередования.

Итак, в заключение следует сказать, что на самом деле невозможно связать NFA или DFA с тем, какая часть чередования будет выбрана, это зависит от конкретной реализации.

И нет, я не нашел способа указать конкретной реализации изменить ее значение по умолчанию.

Связанный:

Связанный контент