Поддержка прямых вперед-смотрящих утверждений

[Oleg Sychev]

Originally reported on Google Code with ID 4

Реализовать все виды assertion - включая \b и т.д.
* negative lookahead
* positive lookbehind
* negative lookbehind
* \b\B\A\z\Z\G

Reported by oasychev on 2010-09-20 09:10:17

[Oleg Sychev]

``` Я не знаю, в какой мере DFA позволяет реализовать lookbehind assertion, но negative lookahead очень важны для поддержки некоторых пользовательских функций и должны быть реализованы как можно скорее (по ходу рефакторинга или сразу после него). ```

Reported by `oasychev` on 2010-10-25 11:11:30

[Former user]

``` Я думаю, что ассерты просмотра назад можно реализовать, если сопостовлять с ассертом подсроку от начала до позиции предшествующей ассерту, как заякоренную с конца $. А вот с отрицательными ассертами есть проблема. Если он совпадет, как определить следующий символ и индекс конца совпадения? К тому же символ для следующей позиции должен будет совпадать с основным выражением. Для этого потребуется изменить механизм определения индекса последнего правильного символа и символа подходящего на следующее место. ```

Reported by `Xapuyc7` on 2010-10-25 11:55:38

[Oleg Sychev]

``` Для отрицательных ассертов просмотра вперед я больших проблем не вижу: конец совпадения будет перед началом ассерта, следующий символ - любой, не дающий начала совпадения с ассертом, но совпадающий с тем что идет далее за ассертом (кстати, как волна взаимодействует с ассертами?).

Для отрицательных ассертов просмотра назад концом совпадения выражения будет первый символ совпавший с выражением в ассерте, со следующим будет чуток похуже - нужно чтобы он уложился в подходящее место регулярного выражения и при этом не вызывал совпадения с отрицательным ассертом.

Но это все только после рефакторинга - прежде всего нужно восстановить работоспособность матчера.

Еще при тестировании нужно делать примеры на случаи, когда все выражение состоит из одних ассертов и длина совпадения равна нулю (что совсем не означает, что есть оно или нет - это одно и тоже). ```

Reported by `oasychev` on 2010-10-25 12:12:52

[Former user]

``` Возможна ситуация когда не существует 1-го символа, который бы не совпал, напирмер (?!.*a), тогда в подсказке, нужно заменить 1-е вхождение "а", а попытка найти 1-й символ дающий не совпадение сам по себе ничего не даст. Кстати, нужно будет исправить определение следующего символа для положительного ассерта, сейчас просто выбирается символ подходящий для ассерта, без учета его приемлимости для основного выражения. Но все это только после восстановления работоспосбности матчера. ```

Reported by `Xapuyc7` on 2010-10-25 16:31:15

[Oleg Sychev]

``` Если возможно, параллельно с восстановлением работоспособности матчера попробуйте составить набор "нехороших" утверждений (пока вперед смотрящих, как позитивных, так и негативных) - подумаем над ними вместе. Ситуация же осложняется еще и возможным наличием после утверждения продолжения регулярного выражения, их взаимодействие тоже может подкинуть сюрпризы. ```

Reported by `oasychev` on 2010-10-25 17:07:47

[Oleg Sychev]

``` Мне кажется (?!.*a) - не проблема. Нас выручит именно поиск подходящего следующего символа - до первого "а" в ответе таких символов просто не будет (если считать что мы заменяем этот символ, оставляя хвост, конечно, что не совсем сходится с нашей текущей логикой - но в случае негативного ассерта это позволяет легко и универсально найти символ, исправление которого разрушает совпадение с содержимым ассерта), т.к. под точку подходит любой (т.е. мы должны смотреть на отрицание относительно содержимого ассерта, а отрицание точки - пустое, т.к. перевод строки мы не рассматриваем). Когда мы дойдем до первого "а" у нас появиться возможность задать корректный следующий символ (или пустоту, тут уж смотря что в выражении за ассертом стоит) - это и можно считать границей правильного совпадения, по-моему.

Главная проблема - необходимо одновременно следить и за ассертом и за дальнейшим выражением (да еще, в общем случае, и то и другое могут содержать дополнительные ассерты...). Вот тут нужно построить сложные тесты...

P.S. Я не предлагаю всегда при поиске следующего символа считать, что "хвост" остается. Это, видимо, прием, полезный только при анализе негативных ассертов... ```

Reported by `oasychev` on 2010-10-28 19:16:35

[Oleg Sychev]

``` Если нет возражений, то в соответствии с идеей, высказанной в рефакторинге, поддержку ассертов лучше всего реализовывать слиянием автоматов (с совмещением стартового состояния для впередсмотрящего ассерта и конечного для назад смотрящего). Это дает простой и логичный путь для нахождения кратчайшего пути к завершению и следующего символа без проблем.

Вопрос состоит в том, будете ли вы это делать в ближайшее время или мне выдать эту задачу на КНПО кому-нибудь другому? Семестр как раз скоро начинается... ```

Reported by `oasychev` on 2011-01-26 12:16:57

[Former user]

``` Это был бы хороший вариант, но возможность такого слияния вызывает у меня сомнения, ведь нам нужно паралельное сравнение с регексом и с ассертом, значит нужно объединять их состояние так чтобы состояния объединенного автомата накладывали на символ такие же требования как регекс+ассерт, но у этих автоматов будет разная направленность переходов и у разных автоматов для одного символа могут быть разные текущие состояния для разных последовательностей предыдущих символ, тогда объединение будет не просто объединением соответствующих состояний, но объединением всех их возможных комбинаций и формированиеам новых переходов вместо старых. В результате чего автомат увеличится в размере (и я боюсь что довольно сильно) и потребуется немалое время на его построение, ведь построение автоматов это самая медленная часть сравнения, и я ожидаю того же от их преобразования. А алгоритмическая сложность потребует времени на исполнение. Всё это вызывает у меня сомнения: а не прибегнуть ли к старому способу работы с ассертами, да он некрасив, но не требует преобразований автоматов(опасно тормозами) и может быть написано быстрее. ```

Reported by `Xapuyc7` on 2011-01-27 17:03:06

[Oleg Sychev]

``` Автомат может получится большим, хотя его наверняка можно будет упростить. Я стал несколько меньше бояться тормозов когда увидел, за какое время проходят наши 400 ассертов в юнит-тестах, которые строят не один автомат и сравнил с временем генерации формы с данными. А в перспективе мы вообще хотим автомат строить при сохранении вопроса. Так что потенциально эти проблемы решаемы.

А вот при мысли о поиске кратчайшего пути/следующего символа при наличии основного регекса и трех-четырех действующих в данной точке ассертов разного типа: позитивных/негативных, вперед/назад смотрящих - мне становится плохо. Я не уверен, что эта задача в общем случае разрешима. Мы ведь выше обсуждали проблемы только поиска символа для ассерта как такового, не учитывая того, что найденный символ может противоречить основному регексу. А в общем случае в некоей точке строки может действовать не один, а любое количество ассертов. И как их всех согласовывать по следующему символу - неясно. Если можете предложить метод с меньшей алгоритмической сложностью чем слияние автоматов, и работающий для всех типов ассертов, а также потенциально расширяемый на условные подмаски и т.д. - буду обеими руками за.

Пока мне кажется, что слияние автоматов выйдет проще. И делать его можно реже.

P.S. Но прежде всего надо закончить рефакторинг. ```

Reported by `oasychev` on 2011-01-27 18:30:52

[Oleg Sychev]

``` Алгоритм этот существует, известен под названием пересечения конечных автоматов.

Кстати, автомат ведь представляется графом - чем не тема для работы по экстремальным задачам на графах? ```

Reported by `oasychev` on 2011-02-09 19:26:01

[Former user]

``` Для "прицепления" к экстремальным задачам на графах нужно сформулировать это в графовых терминах, как это будет звучать? Ну понятно, что автомат будет нагруженным орграфом, но будет ли пересечение автоматов называться пересением нагруженных орграфов или как-то по другому? ```

Reported by `Xapuyc7` on 2011-03-11 00:32:46

[Oleg Sychev]

``` А нельзя сказать "два автомата, заданные графами состояний" или что-нибудь в этом роде? ```

Reported by `oasychev` on 2011-03-11 07:53:32

[Oleg Sychev]

``` Все-таки если вы делаете как семестровку не стоит ее сильно откладывать, чтобы там не попасть.

http://www.cs.nyu.edu/~mohri/pub/amb.pdf содержит алгоритм пересечения, с описанием ситуации борьбы с эпсилон-переходами. Только обобщите его на случай пересекаемых множеств символов для переходов.

В нашем случае дело осложняется наличием ассертов простых, которые, как и эпсилон-переходы, не съедают символы. \b и \B можно заменить на сложные ассерты, например \b это (?!^\w|\w\W|\W\w|\w$) если я правильно понимают. Со штуками типа ^ и $ хуже. Можно сделать "спецсимволы" начала и конца строки, добавляемые в строку при матчинге, при этом при отсутствии якорения считать совпадения без этих "спецсимволов" тоже полными.

Еще один момент связан с тем, что мы пересекаем не с начала, а с произвольной вершины. В этом случае надо сделать копию всех достижимых из нее вершин, направить ссылки из нее туда и эту копию пересекать. А оригинал для копии разорвать от этой вершины, но оставить как был на случай если в него входят дуги из других путей, минующих вершину-ассерт. ```

Reported by `oasychev` on 2011-04-29 21:35:09

[Oleg Sychev]

``` Насчет \b я погорячился - там надо использовать комбинацию вперед- и назад-смотрящих ассертов, т.к. он находится посередине.

Обсужденная нами идея о слиянии состояний-ассертов со следующими состояниями, съедающими символ, для ^ и $ может быть плодотворной. ```

Reported by `oasychev` on 2011-05-04 21:42:40

[Oleg Sychev]

``` Еще одна мелкая ловушка возникает в ситуации когда пересекаемые автоматы (или один из них) конечны (т.е. не содержат циклов) и имеют разную длину (алгоритм пересечения обрезает по самому короткому автомату) - в этом случае короткий автомат надо дополнить переходами-точками - любой символ - (циклом с точками в случае одного зацикленного автомата?) до нужной длины. ```

Reported by `oasychev` on 2011-05-06 22:41:44

[Oleg Sychev]

``` Реализовал возможность наличия в узле слитых с ним ассертов.

По хорошему начать лучше именно со слияния ассертов, т.к. это предварительное действие перед слиянием автоматов (если есть время). Ассерты сливаются со следующим переходом, т.к. одинаковая точка проверки (проверить в случае ассерта в конце выражения) - нужно подумать над ситуацией, когда следующего узла нет ($ или \b в конце выражения).

Жду вас с рисунками как слияния ассертов, так и автоматов вообще, и возникшими вопроса. Подойти можно в понедельник до моих занятий. ```

Reported by `oasychev` on 2011-05-20 11:15:17

[Former user]

``` Я реализовал слияние для положительного ассерта просмотра вперёд, я произвожу слияние карт следования символов, т.к. на них нет проблем определения того где какой символ. Остальное похже, на этой неделе я буду сильно занят получением допусков к приближающимся экзаменам. Изменения в клоне. ```

Reported by `Xapuyc7` on 2011-06-05 14:28:24

[Oleg Sychev]

``` Как там сдача экзаменов?

Всероссийский конкурс научно-исследовательских работ студентов и аспирантов в области информатики и информационных технологий в рамках Всероссийского фестиваля науки http://www.rsci.ru/grants/grant_news/299/229876.php

Если за июль реализовать таки ассерты всерьез, будет неплохая возможность подать работу на этот конкурс. ```

Reported by `oasychev` on 2011-06-16 18:55:19

[Former user]

``` Самое страшное позади, осталось то что понятно. Надо обдумать ситуацию с несколькими ассертами в выражении, подумать что делать с смотрящими назад, остальное дело техники, постараюсь за июль успеть. ```

Reported by `Xapuyc7` on 2011-06-16 23:59:15

[Oleg Sychev]

``` Давайте делать вещи по-порядку. Во-первых - подчистим завершение рефакторинга и организуем слияние простых ассертов с обычными листьями (и генерацию следующего символа).

Затем - нужно будет разобраться с отрицательными ассертами - т.е. генерацией противоположного автомата (для DFA это легко, насчет карты надо смотреть).

Потом уже - назад смотрящие (там нужно совмещать конец автомата, а не начало). Несколько ассертов не должно быть проблемой - просто сливать их по-очереди.

И, конечно, обсуждение каждого этапа надо начинать с юнит-тестов. P.S. Кстати, где юнит-тест и issue на трекере про обнаруженную вами ошибку с символьными классами? Надо же ее извести...

А так неплохо бы за июль сделать простые ассерты и оба вида впередсмотрящих - уже можно будет исследовательскую часть работы на этот конкурс выставлять... ```

Reported by `oasychev` on 2011-06-17 00:20:53

[Oleg Sychev]

``` У меня на кафедре лежит ксерокопия вашей публикации с конкурса для вас. Если можете зайти в четверг, 30.06, к 11-50 я вам отдам. Понадобится вам чтобы в разных случаях вставлять ссылки на нее... ```

Reported by `oasychev` on 2011-06-28 19:50:13

[Oleg Sychev]

Задача нашла нового владельца для НКА-матчера.

Reported by oasychev on 2013-07-25 22:36:44 - Blocked on: #3 - No longer blocked on: #3

[Oleg Sychev]

Будем реализовывать каждый вид утверждений в отдельном issue.

Reported by oasychev on 2015-03-01 22:40:56

[Oleg Sychev]

Решена.