Есть набор регулярных выражений для разделения заданной строки по типам. Как автоматически распределить их по порядку, чтобы, например, "любые строки" точно проверялось в самом конце и не "перехватывало", например, "только строки с буквы Ц"?

Здравствуйте, The Lex, Вы писали:

TL>Есть набор регулярных выражений для разделения заданной строки по типам. Как автоматически распределить их по порядку, чтобы, например, "любые строки" точно проверялось в самом конце и не "перехватывало", например, "только строки с буквы Ц"?

По длине префикса? И я бы наложил какие-то ограничения на выражения, иначе может быть такое:

a(b + cde)(a+b+c+d+e)*
a(bde + c)(a+b+c+d+e)*

первое более подробно для строк ac*, второе для строк ab*, отсортировать их не получается. А вот если запретить операцию +, но добавить операцию "любой символ".. Из этого получатся 4 выражения, которые можно отсортировать по префиксу.

Здравствуйте, The Lex, Вы писали:

TL>Есть набор регулярных выражений для разделения заданной строки по типам. Как автоматически распределить их по порядку, чтобы, например, "любые строки" точно проверялось в самом конце и не "перехватывало", например, "только строки с буквы Ц"?

Если твои регекспы имеют вид /prefix.*/, то довольно просто отсортировать их по префиксу
— бОльшая длина имеет преимущество перед меньшей
— позитивное условие имеет преимущество перед негативным

А для регекспов общего вида, боюсь, решения нет.
Или оно есть, но через комбинаторный взрыв.

Здравствуйте, SergH, Вы писали:

SH>По длине префикса? И я бы наложил какие-то ограничения на выражения, иначе может быть такое:

Идет процесс проработки идеи — возможно ограничение будет "никаких вам регекспов!" (к) — или же прямая ручная ранжировка и если что — сами себе буратины.

SH>a(b + cde)(a+b+c+d+e)*
SH>a(bde + c)(a+b+c+d+e)*

SH>первое более подробно для строк ac*, второе для строк ab*, отсортировать их не получается. А вот если запретить операцию +, но добавить операцию "любой символ".. Из этого получатся 4 выражения, которые можно отсортировать по префиксу.

Тут вот наверное если "выделяемые" регекспом множества пересекаются... То обратно никак — "кто первый встал — того и тапки" (к)

Здравствуйте, Кодт, Вы писали:

К>А для регекспов общего вида, боюсь, решения нет.
К>Или оно есть, но через комбинаторный взрыв.

Рабочая версия: заставить ранжировать вручную при вводе — вероятнее всего будет именно так — потом может когда-нибудь приделать какие-то средства автоматизированного контроля на условия прохождения конкретных данных...

Стоп, а ведь это мысль: надо к "тестеру" приделать "средство контроля" — если все их, пользователей, контрольные наборы правильно "разложились куда надо" — значит фильтр они настроили правильно. А если нет — "будем искать!" (к)

Спасибо за идет в процессе!!!

Здравствуйте, The Lex, Вы писали:

TL>Есть набор регулярных выражений для разделения заданной строки по типам. Как автоматически распределить их по порядку, чтобы, например, "любые строки" точно проверялось в самом конце и не "перехватывало", например, "только строки с буквы Ц"?
1. Только ручное ранжирование. Иначе начнутся спецэффекты при небольших модификациях одного из правил.
2. Можно попытаться ввести на пространстве регексов отношения частичного порядка, типа regA < regB если для любого текста T, который матчится по regB, regA тоже гарантированно будет матчить. Тогда можно проверить ручное ранжирование на предмет этой упорядоченности, т.к. если "следующее" правило < "предыдущего", то "следующее" не сработает никогда.

Вопрос о вычислении этого частичного порядка, имхо, достаточно сложен. Простые примеры тут уже привели; но есть масса несложных примеров, когда это не сработает.

Здравствуйте, Sinclair, Вы писали:

S>2. Можно попытаться ввести на пространстве регексов отношения частичного порядка, типа regA < regB если для любого текста T, который матчится по regB, regA тоже гарантированно будет матчить. Тогда можно проверить ручное ранжирование на предмет этой упорядоченности, т.к. если "следующее" правило < "предыдущего", то "следующее" не сработает никогда.

S>Вопрос о вычислении этого частичного порядка, имхо, достаточно сложен. Простые примеры тут уже привели; но есть масса несложных примеров, когда это не сработает.

Задача об эквивалентности(а также "включенности", и поиска пересечения языков) двух КА (все равно (НКА или ДКА)/регеспов) полиномиален. Достаточно рассмотреть декартово произведение двух автоматов: состояние — упорядоченная пара <состояние автомата1, состояние автомата2>, переход из <a11, a21> в <a12, a22> по символу Х <=> имеется переход для автомата1 из a11 в a12 по Х, и имеется переход для автомата2 из a21 в а22 по Х.

Гарантируется, что состояние <старт1, страрт2> "достижимо". Далее каким-нибудь обходом графа (BFS/DFS) заполняется таблица достижимых состояний для произведения автоматов.

Если из того, что <X, Y> достижимо в новом автомате и X — заключительное состояние автомата1 следует, что Y — заключительное состояние автомата2, То автомат2 распознает как минимум язык автомата1. Для эквивалентности нужно еще и в другую сторону. И т.д.

Здравствуйте, The Lex, Вы писали:

TL>Есть набор регулярных выражений для разделения заданной строки по типам. Как автоматически распределить их по порядку, чтобы, например, "любые строки" точно проверялось в самом конце и не "перехватывало", например, "только строки с буквы Ц"?
Вроде в языках с pattern matching-ом решается похожая проблема.
Алгоритмы найти не трудно.

Ещё можно посмотреть на Flex, хотя там вроде бы ручное ранжирование.