про регулярные выражения

[sab123]

Увидел нынче реализацию конструкции (A|B) в регулярном выраженни. Т.е. альтернативы из двух подвыражений A или B. Оно сделано так:

Каждое выражение можно изобразить в виде направленного графа, где вершины - стостояния (A1...AN, B1...BN), а ребра помечены символами, по которым производится переход из одного состояния в другое.

Мысленно вытягиваем каждый граф в цепочку, чтобы состояния шли по порядку: A1, A2, ... AN. Теперь делаем из них двумерную таблицу:

	A1	A2	A3	...	AN
B1
B2
B3
...
BN

Каждая клетка в таблице представляет собой комбинацию вершин в двух графах, и будет являться вершиной нового комбинированного графа. Теперь начинаем из клетки A1B1 (которая соответствует начальным вершинам обоих графов), и разрисовываем новые ребра, где старые ребра из A командуют перемещением по горизонтали, а из B - по вертикали. Например, если у нас для символа "x" было ребро A1-x->A3 и ребро B1-x->B5, то в результате мы получаем комбинированное ребро A1B1-x->A3B5. Вершины, которые были конечными для одного из графов, делаются конечными для комбинированного графа.

Понятно, что некоторые клетки останутся неиспользованными - они в результате выбрасываются. А использованные клетки перенумеруем по порядку.

Красиво, а? Вот не знаю, удалось ли бы мне такое придумать с пустого места просто из головы.

А вот еще интересное последствие: аналогичным способом можно устроить и "конъюнкцию" регулярных выражений. Ну, или через равенство (A&B)=!(!A|!B). Что она будет означать? Строку, которая соответствует обоим выражениям сразу. Например, "([^a]*a[^a]*a[^a]*)&([^b]*b[^b]*b[^b]*)" будет строчкой, которая содержит ровно две буквы "a" и ровно две буквы "b".

Заставляет задуматься о том, почему популярные реализации регулярных выражений дают нам дизъюнкцию, но не дают конъюнкцию. Было бы очень удобно. Или они дают, а я просто не в курсе? Гм, а дают ли они нам отрицание? Вроде тоже нет.

Comments

[juan-gandhi.livejournal.com]

В парсере алгола-68 был такой трюк, когда сохраняли не одно состояние, а множество состояний.

Хотелось бы найти пример, где нужна конъюнкция.

[sab123.livejournal.com]

Ну в Алголе-68 вообще вроде как был разбор недетерминированный.

А пример - вот он, чуть выше. Ибо изобразить руками в регулярном выражении строчку с ровно двумя буквами "а" и двумя буквами "б" - весьма нетривиальный фокус.