#regex #algorithm #theory #computation-theory
#регулярное выражение #алгоритм #теория #теория вычислений
Вопрос:
Я ищу что-то, что позволяет мне сортировать список регулярных выражений или какую-либо документацию и исследования,
в соответствии с их спецификой / строгостью
/[a-z] / // most strict
/[a-z0-9] /
/[a-z0-9èòà] / // less strict
/.*/
но как насчет
/[a-z] ABC/
/[a-z0-9] /
какой из них менее специфичен, чем другой?
заранее благодарю
Комментарии:
1. Эмм, без идеи? Более конкретно о чем? Как вы сравниваете два регулярных выражения? Они предназначены для сопоставления разных вещей или?
2. Вы можете определить специфику самостоятельно: я бы определил это следующим образом: Регулярное выражение 1 более специфично, чем регулярное выражение 2, если все строки, сопоставленные с регулярным выражением 1, также сопоставляются с регулярным выражением 2 (т. Е. Если L(regex1) является подмножеством L(regex2)). Если ни одно из подмножеств не является подмножеством другого, я бы назвал их «несравнимыми».
3. @phimuemue … что относится ко второму примеру.
Ответ №1:
Регулярное выражение можно приравнять к набору строк, которым оно соответствует (так называемый «обычный язык»).) Если у нашего регулярного выражения есть имя E , давайте назовем его соответствующие строки L(E) .
Строгость в том смысле, на который вы ссылаетесь выше, становится отношением подмножества: определите RE A как более строгое, чем RE B , если L(A) это правильное подмножество L(B) . Это устраняет двусмысленности, такие как синонимы для «того же» RE: они одинаковы именно потому, что у них один и тот же обычный язык.
Как указывает @yi_H, отношение подмножеств над языками RE (над некоторым общим алфавитом) формирует частичный порядок. Вы говорите так, как будто хотите полного упорядочения. Если это так, вы можете указать, что приемлемый общий порядок должен включать частичный порядок, представленный отношением подмножества.
У меня нет четкого ответа на вопрос, как построить этот общий порядок, но на ум приходят два подхода.
Первый — использовать лемму о перекачке. Оказывается, что для любого RE, если он соответствует достаточно длинной строке, то он также должен соответствовать более длинной строке, построенной с самого начала путем повторения некоторого подраздела. Вы могли бы спросить, какова длина самой длинной совпадающей строки, в которой нет таких повторяющихся сегментов, и сделать это своей метрикой. Может быть, это учитывает (встраивает) частичный порядок, а может и нет.
Другой способ — рассмотреть преобразования графа на конечном автомате RE. Я подозреваю (но у меня нет никаких ссылок), что если RE A является более строгим, чем RE B , то B автомат s будет вычисляться из A s путем свертывания состояний или какого-либо подобного упрощающего действия. Вы могли бы определить свою метрику как количество состояний в наименьшем автомате RE.
Комментарии:
1. Я полагаю, что существует серия статей Алмейды и других, в которых используется понятие Бжозовского о производных регулярных выражений для выполнения эффективного тестирования на равенство и порядок регулярных выражений. Я думаю, что это было бы лучшим решением для OP, потому что никто не хочет реализовывать алгоритмы NDA / DFA / REGEXP.
2. Потрясающе, похоже, кто-то еще уже продумал это. Ссылки на документы?
3. Ну, я не смог найти статью о включении, о которой я думал, но я полагаю, что в статье Алмейды «Проверка эквивалентности регулярных языков» и в статье Антимирова «Переписывание расширенных регулярных выражений» говорится о проверке эквивалентности и включения. Я думаю, что статья, о которой я думал, называлась «Частные производные …» Антимирова. В Hackage есть реализация на Haskell под названием regexpr-symbolic .
Ответ №2:
Как показывает ваш второй пример, вы не можете иметь полный порядок регулярных выражений, возможен только частичный порядок.
Что еще хуже, есть десятки способов написать одно и то же регулярное выражение: [ab]b vs (ab|bb) , aa* vs a . Так что даже решить, эквивалентны ли два регулярных выражения, непросто.
Комментарии:
1. Хороший комментарий, но это не ответ.
Ответ №3:
Предполагая, что вы говорите о чистых регулярных выражениях, а не о сумасшедшем материале perl, вы можете определить частичный порядок регулярных выражений, который соответствует вашему вопросу, на основе набора строк, которые они принимают (т. Е. Просматривать регулярное выражение как обычный язык).
Учитывая, что различия, пересечения и пустоты регулярных языков являются разрешимыми проблемами, это означает, что существуют алгоритмы, которые сообщат вам, принимает ли одно из ваших выражений все строки, которые принимает другое.