Рефакторинг ЧСК для ДКА
Issue #76
duplicate
Originally reported on Google Code with ID 76 ``` Проблему составляют частично пересекающиеся и включенные символьные класса и метасимволы. Для её решения необходимо преобразовать их таким образом, чтобы из одного состояния небыло переходов по 2-м и более СК имеющим хотя бы один общепринимаемый символ. Ситуация полность совпадающих СК и метасимволов не вызывает проблем, но частичное пресечение или поглошение вызывает. Поглошение было решено, но это "костыль", и как мы убедилсь, он не всегда работает. Например, пусть дано выражение /\+.*abc\*, тогда ситуация с включением СК в метасимвол возникает не только между точкой и а, но и между точкой и b, c \*, хотя они и следуют за точкой не непосредственно.
Нужно: 1.Найти способ определения групп СК, которые должны быть разбиты до уникальных и выбрать момент для и место для этого разбиения. Впринципе можно все СК разбить до уникальных, но оправдано ли это? Например для выражения [abcd][bcde][cdef]*[defg] будет достаточно разбить два последних. 2.Найти способ разбивать эти группы до уникальных СК, в частности, в случае если их более двух и все они ЧСК, например: из [abcdefg]*[bcdefgh][cdefghj][defghjk][efghjkl] должно получиться что-то вроде (a|b|c|d|[efg])*(b|c|d|[efg]|h)(c|d|[efg]|h|j)(d|[efg]|h|j|k)([efg]|h|j|k|l) - по идее, можно разбивать попарно, но оптимальный ли это вариант? 3.Реализовать 1 и 2 в коде.
Есть идеи? Свои буду озвучивать по мере их появления. ```
Reported by `Xapuyc7` on 2011-12-12 14:45:51
Comments (11)
-
-
Account Deleted
``` Предлагаю вести сквозную нумерацию, чтобы было удобнее ссылаться. Идея Валерия имеет №1.
По поводу 1, имею два замечания. Во первых одного шага недостаточно, во вторых проблема не при следовании ЧСК один за другим, а в ситуации когда они могут оказаться в одной позиции в строке, т.е. [ab][bc] не проблема, а вот [ab]d|[bc]e [ab]?[bc] [ab]*[bc] [ab]+[bc] и т.п. это проблема. Например в случае [ab]d|[bc]e получив букву b ДКА сопоставит либо с [ab], тогда be не совпадет с регексом, либо с [bc], тогда bd не совпадет с регексом. в случаях с квантификатором, он либо будет жрать символы пока можно, что может помешать совпадения с дальнейшей частью регекса, если сожрать слишком много символов, либо перестанет их есть, как только будет совпадение с другим, что тоже проблема, ведь [ab]+[bc] и строка ababababbab, при первой b совпавшей с [bc] он найдет не максимальную длину совпадения, а при последней b совпавшей с [аb] он потребует еще одну b, хотя полное совпадение уже есть.
2. Не совсем так, но мысль интересная. Я скорее вижу этот вариант, как пустить волну из начального состояния и выполнить разбиения для всех фронтов волны (т.е. разбивать до уникальных СК находящиеся в одном фронте волны), но условия остановки заключается в том, что получены все возможные фронты волны, а это, как мне кажется, сложнопроверяемое условие. К тому же у меня есть сомнения на тему, а не окажутся в одном фронте волны в ДКА, СК, которые до детерминизации были в разных фронтах?
3. Либо можно пустить такую волну по карте следования символов, тогда, если ни для одного из всех возможных фронтов, два СК не окажутся в одном фронте, это будет доказательство того, что они не могут совпасть с символом в одной позиции строки, при условии, что ассерты будут учтены волной. Но критерий остановки остается тот же, и его проверка выглядит проблематично. ```
Reported by `Xapuyc7` on 2011-12-12 17:23:12
-
repo owner
``` Поскольку дело отложено до 2.2, предлагаю не заморачиваться воркараундами, а просто перписать по нормальному систему узлов и добавить к ней операции пересечения и вычитания (объединение надо?). Разве этого недостаточно? ```
Reported by `oasychev` on 2011-12-13 08:27:27
-
Account Deleted
``` Для решения проблемы 2 этого должно хватить. Но меня больше беспокоит проблема 1, а именно, определение групп СК и их состава, которые должны быть разбиты до уникальности и идентичности внутри своей группы. ```
Reported by `Xapuyc7` on 2011-12-13 08:40:04
-
repo owner
``` Разве недостаточно иметь возможность генерировать пересечения и разности двух листов и проверять, не получится ли пересечение (разность) пустым? Пустое игнорируем, по непустому - действуем... ```
Reported by `oasychev` on 2011-12-13 09:55:26
-
Account Deleted
``` Именно так! Внутри групп требующих разбиения. Проблема в том, как определить группу требующую разбиения? Hапример [abcd][bcde]+[cdef] последние два СКа составляют такую группу, и там мы по непустому действуем, а 1-й СК хоть и пересекается с двумя другими, но это не требует действий, т.к. 1-й СК совпадает с первым символом в матчинге и только с ним,тогда как 2-й СК совпадает (и будет на это проверяться) для всех символов начиная со второго, точно так же, 3-й СК проверяется для всех символов начиная с 3-го, и соответственно, когда мы сматчим 2 или больше символов, мы не будем знать, с каким СК нужно сравнивать следующий, а первый символ безпроблемен. Для выражения, например, (?:.\W\D\w\d){100}[abc]?[bcd] достаточно разбить только последние два СК, тогда как остальные ЧСК, коих тут 500 абсолютно безвредны и их разбиение необязательно, так как они высе твердо стоят на своих позициях. Так, что мне бы хотелось найти лучшее решение, нежели разбиение абсолютно всех ЧСК, хотя это и возможно. ```
Reported by `Xapuyc7` on 2011-12-13 17:51:39
-
repo owner
``` Можем обсудить в пятницу на встрече. Мне кажется разбивать надо на этапе построения/детерминизации автомата - там понятно, что надо - а что нет. Неужели типовые алгоритмы детерминизации этого не учитывают? ```
Reported by `oasychev` on 2011-12-14 10:52:13
-
``` Не знаю куда написать, поэтому напишу сюда. Проверял работу draw и наткнулся на ДКА такого вида. Это баг в рисовании, или действительно несколько одинаковых переходов выходят из 12 и 14 состояний? ```
Reported by `vostreltsov` on 2011-12-16 16:21:54
<hr>
-
Account Deleted
``` Это артефакт реализации, ДКА имеет несколько одинаковых переходов, которые можно было бы заменить одним, но незачем, это безвредно. ```
Reported by `Xapuyc7` on 2011-12-16 18:23:06
-
repo owner
``` Один из примером рассмотрения алгоритма построения ДКА (немного нестандартного) и его расширения на использование СК http://www.ccs.neu.edu/home/turon/re-deriv.pdf ```
Reported by `oasychev` on 2012-01-03 17:46:09
-
repo owner
``` Свожу вместе две задачи по сути об одной теме... ```
Reported by `oasychev` on 2012-09-23 21:48:05 - Status changed: `Duplicate` - Merged into:
#130 - Log in to comment
*){kind=link}
``` Можно сделать что-то подобное: для каждого перехода делать 1 шаг волны вперед (или сколько потребуется, в любом случае будет критерий остановки этого процесса) и получать пересечение этого перехода со следующими. После чего из текущего перехода вычесть все эти пересечения, собрать из пересечений альтернативу и пустить параллельно этому переходу. Как раз пригодится планируемое пересечение, вычитание листьев и т.д.
Если что-то такое в принципе реализуемо, это легко натягивается на наш единый формат автомата. Тогда перед детерминизацией будет вызываться это преобразование, а nfa оно не будет нужно... ```
Reported by `vostreltsov` on 2011-12-12 15:26:15