java. regexp.
можно. показывай a и b - вспомним перловое детство 
если бы мне нужно было сравнить 2 конкретных регекспа, я бы не спрашивал
если бы я собирался сравнивать два конкретных регэкспа, я бы не ставил смайлик
Утверждается, что:
1. Каждому регулярному выражению соответствует регулярный язык
2. Для любого регулярного языка можно эффективно вычислить дополнительный
3. Для любых двух регулярных языков можно эффективно вычислить их пересечение
4. Можно эффективно проверить регулярный язык на пустоту.
Подробности в книжке
1. Каждому регулярному выражению соответствует регулярный язык
2. Для любого регулярного языка можно эффективно вычислить дополнительный
3. Для любых двух регулярных языков можно эффективно вычислить их пересечение
4. Можно эффективно проверить регулярный язык на пустоту.
Подробности в книжке
\\172.16.12.100\docs\ebooks\unsorted\CsAl_Algorithms\Hopcroft, Motwani, Ullman. Introduction to automata and algorithms (2ed. AW 2001T537s).djvuглава 4.2
Мощно. А в инете где эту книжку найти, не посоветуешь?
Либо осел/мул какой-нибудь, либо мыло в приват 
А у тебя сложные регекспы? Я знаю (технологичное ) решение для регекспов, в которых есть только конструкции
*, [], ., ну и буквы.
) решение для регекспов, в которых есть только конструкции*, [], ., ну и буквы.
у меня только буквы, "." и "*"
Короче смотри. Есть забубенный тул, называется Ragel. Это генератор конечных автоматов.
Пишешь значит ему вот такой файл test.rl:
К сожалению все буквы не в [] нужно взять в кавычки, как в примере для 'a'. Зато выяснилось что работают +, {m,n} и кое-что еще, надо документацию к Ragel-ю смотреть.
Так вот и запускаешь
ragel -d test.rl
Фтыкаешь на результат. Если видишь вот такое
значит все клево, ни одного финального состояния нет, то есть regexp1 мажорирует regexp2.
А если на выходе что-то посложнее типа
(это я в regexp2 `+` на `*` заменил то значит непустая разность. Ну как? Все вроде бы в легкую автоматизируется. Java-ой правда не пахнет, да ну и что. Лепишь на перле сервер и пусть в него Java по сокету ходит.
Пишешь значит ему вот такой файл test.rl:
%% xxx
{
regexp1 = [abcd]*'a'[abc]*
;
regexp2 = ([ad]*[abc])*('a'[bc])+
;
main := regexp2 - regexp1
;
}
К сожалению все буквы не в [] нужно взять в кавычки, как в примере для 'a'. Зато выяснилось что работают +, {m,n} и кое-что еще, надо документацию к Ragel-ю смотреть.
Так вот и запускаешь
ragel -d test.rl
Фтыкаешь на результат. Если видишь вот такое
DUMP of xxx
StartState: 0
Final States:
0 []
->
значит все клево, ни одного финального состояния нет, то есть regexp1 мажорирует regexp2.
А если на выходе что-то посложнее типа
DUMP of xxx
StartState: 0
Final States: 0 |
0 []
-> 97 2 [] | 98 0 [] | 99 0 [] | 100 1 [] |
1 []
-> 97 2 [] | 98 0 [] | 99 0 [] | 100 1 [] |
2 []
-> 97 2 [] | 98 2 [] | 99 2 [] | 100 1 [] |
(это я в regexp2 `+` на `*` заменил то значит непустая разность. Ну как? Все вроде бы в легкую автоматизируется. Java-ой правда не пахнет, да ну и что. Лепишь на перле сервер и пусть в него Java по сокету ходит.
Ой блин я ступил, у точки не тот смысл, надо вместо нее писать any. Ну ё маё! Есть правда еще такой синтаксис
тогда точка работает как положено, не нужны кавычки, но перестают работать обещаные выше +, {m,n} и самое тупое не работают
Ну вобщем идея так или иначе понятна, а дальше смотри. По-моему написать самому такое реально ну за пару недель не меньше, а то что я говорю можно довести до ума за пару дней...
regexp1 = /abc.*[de]../
тогда точка работает как положено, не нужны кавычки, но перестают работать обещаные выше +, {m,n} и самое тупое не работают
Ну вобщем идея так или иначе понятна, а дальше смотри. По-моему написать самому такое реально ну за пару недель не меньше, а то что я говорю можно довести до ума за пару дней...Оставить комментарий
IvladV71
есть регексп a и регексп b .можно ли узнать, является ли множество строк, удовлетворяющих a подмножеством множества строк, удовлетворяющих b ?