Определение специфичности регулярного выражения

Question

Учитывая следующие регулярные выражения:

- alice@[a-z]+\.[a-z]+ 
- [a-z]+@[a-z]+\.[a-z]+ 
- .* 

Строка alice@myprovider.com будет, очевидно, совпадают все три регулярные выражения. В приложении, которое я разрабатываю, нас интересует только «наиболее конкретный» матч. В этом случае это, очевидно, первый.
К сожалению, похоже, что нет способа сделать это. Мы используем PCRE, и я не нашел способ сделать это, и поиск в Интернете также не был плодотворным.
Возможным способом было бы сохранить регулярные выражения, отсортированные по нисходящей специфике, а затем просто взять первое совпадение. Конечно, следующий вопрос: как отсортировать массив регулярных выражений. Это не вариант, чтобы дать ответчику конечный пользователь, чтобы убедиться, что массив отсортирован. Итак, я надеюсь, вы, ребята, могли бы помочь мне здесь ...

Спасибо!

Пол

Answer 1

Моя интуиция говорит, что это не только сложная проблема, как с точки зрения вычислительных затрат и сложности реализации, но это может быть неразрешимой в любой реалистической манере. Рассмотрим два следующих регулярных выражений, чтобы принять строковое alice@myprovider.com

 
    alice@[a-z]+\.[a-z]+ 
    [a-z]+@myprovider.com

Какой из них более конкретно?

Answer 2

Я работаю над ответом на одной и те же проблемы, что я нашел до сих пор находится здесь: http://maple.cs.umbc.edu/~don/projects/ugrad-ht/dminer-ugradthesis.pdf

Это исследование уровня выпускницы бумага, используя PERL регулярного выражения, то есть работоспособное определение для «наиболее специфичных regex 'и вызывает предупреждение, если есть два выражения регулярных выражений с одинаковой специфичностью. Он частично основан на установочном файле SELinux, но имеет целью быть более быстрым и точным. Setfile оставляет его пользователю, чтобы совпадения переходили от наиболее специфических к наименее конкретным и принимали первое совпадение. Это может вызвать некоторые проблемы, которые исследовательский документ должен решить.

В принципе, наиболее конкретный матч - это тот, который не является надмножеством любого другого матча. Сложность решения заключается в определении того, какие множества являются надмножествами других множеств; конечно, ответ на это зависит от обстоятельств, для которых требуется регулярное выражение. Когда у вас есть список надмножеств, тогда это становится вопросом устранения совпадений. Таким образом, с выражениями регулярных выражений '^ /. *', '^/Usr /.*' и '^/home /.*', '^ /. *' Является надмножеством двух других, а остальные два взаимно эксклюзив. В правильной реализации, если два вторых не были взаимоисключающими (отсутствует «^»), и ни один из них не является надмножеством другого, пользователю или пользователю должно быть выдано предупреждение или ошибка. Для данной строки, чтобы проверить соответствие, сначала ее нужно проверить против любых надмножеств (в данном случае «^ /. *»), Если она не соответствует надмножеству, она не может соответствовать какому-либо конкретному шаблону. Если он соответствует, тогда должен выполняться тест против каждого из дочерних элементов надмножества (эти наборы также могут быть надмножествами дополнительных наборов). Если он не соответствует ни одному из детей, то наиболее конкретным регулярным выражением является надмножество ('^ /. *'). Если он соответствует одному из детей, то процесс должен повториться с ассоциированными внуками, пока не будет никаких конкретных наборов или ни один из конкретных наборов не будет соответствовать.

Может быть достаточно, чтобы не выдавать предупреждения о не взаимоисключающих не супер-наборах, если не выполняется попытка сопоставления строк, которая не может быть разрешена. Рассмотрим множество выражений регулярных выражений: '^ /. *', '/usr.*' и '/home.*'. Строка '/ home/usr' будет соответствовать всем трем, и попытка совпадения должна вызвать ошибку, так как неясно, если '/usr.*' или '/home.*' предназначено как наиболее конкретный регулярный выражение.

В зависимости от причин, требующих решения, верным списком регулярных выражений, которые не являются надмножествами любого другого подходящего регулярного выражения, может быть идеальным решением. В этом случае '/ home/usr' должен возвращать '/home.*' и '/usr.*', но не '^ /. *'.

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

Answer 3

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

Решение, однако, было бы просто отсортировать список регулярных выражений в порядке его длины строки.

Это не идеально, но просто удалив [] -группы, это будет намного ближе. На первом примере в этом вопросе было бы этот список:

- alice@[a-z]+\.[a-z]+ 
- [a-z]+@[a-z]+\.[a-z]+ 
- .* 

к этому, после удаления содержимого любого [] -группа:

- alice@+\.+ 
- +@+\.+ 
- .* 

То же самое касается второго примера в другом ответе, с [] -групп полностью удалены и сортируются по длине, так:

alice@[a-z]+\.[a-z]+ 
[a-z]+@myprovider.com 

стал бы отсортированный как:

+@myprovider.com 
alice@+\.+ 

Это решение, по крайней мере, для меня, если я его использую. Недостатком было бы накладные расходы на удаление всех групп [] перед сортировкой и применением сортировки в неизмененном списке регулярных выражений, но эй - вы не можете получить все.