про регулярные выражения
Jun. 25th, 2008 12:02 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sab123Увидел нынче реализацию конструкции (A|B) в регулярном выраженни. Т.е. альтернативы из двух подвыражений A или B. Оно сделано так:
Каждое выражение можно изобразить в виде направленного графа, где вершины - стостояния (A1...AN, B1...BN), а ребра помечены символами, по которым производится переход из одного состояния в другое.
Мысленно вытягиваем каждый граф в цепочку, чтобы состояния шли по порядку: A1, A2, ... AN. Теперь делаем из них двумерную таблицу:
Каждая клетка в таблице представляет собой комбинацию вершин в двух графах, и будет являться вершиной нового комбинированного графа. Теперь начинаем из клетки 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".
Заставляет задуматься о том, почему популярные реализации регулярных выражений дают нам дизъюнкцию, но не дают конъюнкцию. Было бы очень удобно. Или они дают, а я просто не в курсе? Гм, а дают ли они нам отрицание? Вроде тоже нет.
Каждое выражение можно изобразить в виде направленного графа, где вершины - стостояния (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".
Заставляет задуматься о том, почему популярные реализации регулярных выражений дают нам дизъюнкцию, но не дают конъюнкцию. Было бы очень удобно. Или они дают, а я просто не в курсе? Гм, а дают ли они нам отрицание? Вроде тоже нет.
