Поддержка ассертов границы слова (\b \B)

[GoogleCodeExporter]

Обсуждение лучше вести в отдельной задаче.

eklepilkina:
Возникли вопросы по поводу мержинга \b. С 
раскрытием понятно, а вот как избавляться 
от полученных \w и \W. Ведь они захватывают 
символы. Мне нарисовали, как должно быть в 
регулярном выражении, но там смотрящие в 
разные стороны ассерты. Я не представляю, 
как это представляется в автомате.

Лена - мержинг \b и \B подчиняется тем же 
законам, что и мержинг сложных ассертов, с 
которого вы начали на НКПО. Т.е. переходы 
пересекаются, если не с чем пересекать в 
основном автомате - образуют 
дополнительные "ассертные" переходы, 
специально помеченные.
Разница в том, что здесь для добавляемого 
автомата (раскрытого \b) пересечение 
начинается не с начала и не с конца, а с 
середины; причем это 4 узла сразу - зато 
влево и вправо от каждого из этих узлов 
ведет ровно по одной дуге. Поэтому алгоритм 
мержинга лучше построить отдельный; по 
смыслу же он ничем ни отличается от 
пересечения автоматов для мержинга 
сложных ассертов. Такие же пересечения дуг 
из разных автоматов с теми же 
последствиями.

Original issue reported on code.google.com by oasyc...@gmail.com on 3 Oct 2013 at 1:06

[GoogleCodeExporter]

Все равно остались вопросы.
1. Первый автомат для пересечения - это 
автомат с полученной развилкой в 4 узла 
вместо \b, а второй какой? По тому какое 
регулярное выражение должно получаться по 
идее должны пересекаться части автомата, 
полученные от развертывания и 
существовавшие раннее в разные стороны. 
Так должно получаться на совсем простых 
автоматах как на картинках?
2. \B оно же разворачиваться должно по 
другому. Что-то \w-\w и \W-\W.

Original comment by eklepilkina@gmail.com on 3 Oct 2013 at 2:54

Attachments:

• b.png
• bResult.png
• ex.png
• exResult.png

[GoogleCodeExporter]

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

На рисунках результаты примерно правильны, 
но переходы ^\t ^c и $a можно обрывать, т.к. 
шансов на совпадение они не имеют - ведь ^ 
мержится назад, а $ - вперед.  ^ и $ в \b 
работают реально тогда, когда регекс им 
начинается или заканчивается. ex.png вообще 
не имеет шансов на совпадение, ибо какая 
такая граница слова возможна между двумя 
буквами?

Кстати, поскольку \n это вариант \W то вместо 
^\w можно использовать \A\w, перевод строки 
пройдет по ветке \W\w. Аналогично с $, который 
можно заменить на самую строгую версию \z.

\B это отрицание \b и тоже разворачивается на 
четыре альтернативы - \w\w \W\W ^\W и \W$

Original comment by oasyc...@gmail.com on 3 Oct 2013 at 3:05

[GoogleCodeExporter]

Проверил ваши тесты на \b - стало лучше, но 
есть еще проблемы и ошибки - можете в 
понедельник забрать, у меня лаба в 902 до 15 
часов; если есть возможность подойти часов 
в 17...17-30 стоило бы поговорить о проблемах 
при слиянии ассертов начала и конца строки, 
я хочу сесть с вами и помочь кросс-тесты на 
них сделать...

Original comment by oasyc...@gmail.com on 8 Nov 2013 at 2:48

[GoogleCodeExporter]

Олег Александрович, возник при переводе 
тестов в вид кросс-тестов вопрос, 
касающихся подобных автоматов. В них 
получается первый переход \w 
незахватывающий и он как бы должен дать 
совпадение на строке a\tcat. Но что там должно 
генерироваться, просто Валера говорит, что 
он с подобными переходами не работал, и что 
там должно получаться не знает.

Original comment by eklepilkina@gmail.com on 21 Apr 2014 at 6:10

Attachments:

• s.png
• s1.png

[GoogleCodeExporter]

Там в переходах должен быть признак их 
"ассертовости". Он же будет проставляться 
для тех переходов, которые вы при мержинге 
сложных ассертов помечали как "из второго 
автомата".

Такие переходы описаны в issue #114 - посмотрите 
сами его/связанный код. Если сами не 
поймете, Валерию это issue точно должно 
напомнить о чем речь. Больше года назад я 
про эти переходы уже ему говорил.

Original comment by oasyc...@gmail.com on 21 Apr 2014 at 8:14

[GoogleCodeExporter]

Какие сейчас проблемы с \b.

Original comment by eklepilkina@gmail.com on 16 Nov 2014 at 11:38

Attachments:

• b

[GoogleCodeExporter]

1 - строго говоря должна (и по идее при 
нормальной реализации цифирок это должно 
обеспечиваться); но вот конкретно для 
нашего вопроса - не должна по хорошему. Мы 
же вроде обсуждали этот вопрос как-то при 
встрече? 
Я думаю эту проблему в кросс-тестинге надо 
ввести новым вариантом тега в тесте, 
позволяющего вернуть два варианта 
правильного ответа - когда совпадает и 
когда нет; так чтобы можно было запускать 
совпадение в обоих режимах (по умолчанию 
как для вопроса, но если вдруг понадобится - 
как чисто по регексовски). Предлагаю 
Валерию сделать изменения в кросс-тестере, 
а Лене доработать тесты.
2 и далее Валерий - что скажите?

Original comment by oasyc...@gmail.com on 16 Nov 2014 at 2:00

[GoogleCodeExporter]

Вообщем возникла такая проблема с циклами. 
Допустим в этом регексе ([a!]\b)+, в конечное 
состояние должны вести 3 незахватывающих 
перехода \W, \w и $. Для этого при построении 
цикла эти переходы не должны удаляться, а в 
регексе ([a!]\b)+с их быть не должно, т.е. их 
надо удалить. В процессе построения 
автомата не понятно, является цикл 
последним или нет. Аналогичная ситуация 
будет с начальным состоянием.

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

Original comment by eklepilkina@gmail.com on 29 Nov 2014 at 1:56

[GoogleCodeExporter]

Лена, вы похоже где-то сильно не так 
понимаете. По логике постепенного 
построения когда вы строите "([a!]\b)+" у вас 
остаются в конце незахватывающие переходы. 
Потом когда вы при построении "([a!]\b)+с" 
делаете конкатенацию с "с" у вас эти три 
перехода пересекаются с "с", в результате 
чего остается только один и теперь уже 
захватывающий.

При этом все логично и естественно 
получается.

Original comment by oasyc...@gmail.com on 29 Nov 2014 at 4:02

[GoogleCodeExporter]

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

Original comment by eklepilkina@gmail.com on 29 Nov 2014 at 4:59

[GoogleCodeExporter]

Тогда давайте краткий словесный алгоритм 
генерации для ассерт-перехода в конце 
цикла. Считаем что внутрицикловая 
конкатенация уже сгенерирована и из нее 
торчат вправо три незахватывающих 
перехода. Теперь вы генерируете цикл для +.

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

Распишите подробно ваш алгоритм действий 
для этого момента, почему там у вас что-то 
повторно пересекается?

Original comment by oasyc...@gmail.com on 29 Nov 2014 at 6:17

[GoogleCodeExporter]

Если описать долго, сделайте описание к 
встрече в среду; а сейчас отлаживайте те 
случаи с ^ $ и эпсами которые еще не работают

Original comment by oasyc...@gmail.com on 1 Dec 2014 at 11:38

[GoogleCodeExporter]

А у нас консультация завтра или через 2 
недели?

Original comment by eklepilkina@gmail.com on 2 Dec 2014 at 10:03

[GoogleCodeExporter]

Завтра, она по второй неделе.

Original comment by oasyc...@gmail.com on 2 Dec 2014 at 10:32

[GoogleCodeExporter]

fa_matcher failed on regex '([a!?]|)\b([c+]|)' and string 'c' 
(qtype_preg_cross_tests_from_preg_merging, 
data_for_test_assertions_wordboundary_20):
INDEX_FIRST:     0=>1, 1=>0, 2=>1, 
LENGTH:          0=>0, 1=>0, 2=>0, 
expected:
INDEX_FIRST:     0=>0, 1=>0, 2=>0, 
LENGTH:          0=>1, 1=>0, 2=>1, 

Original comment by vostreltsov@gmail.com on 1 Jan 2015 at 7:19

Attachments:

• fa_unmerged.svg
• fa_merged.svg

[GoogleCodeExporter]

Лена, можете растолковать fa_merged.svg? 
Во-первых, там явно многовато-то узлов и 
линий. У вас пустые пересечения и те, 
которые не имеют шансов совпасть удаляются?

По идее в автомате есть путь через 15-й узел, 
который соответствует ожидаемому 
совпадению. Почему он не срабатывает или 
что там не так с тегами?

Original comment by oasyc...@gmail.com on 1 Jan 2015 at 11:45

[GoogleCodeExporter]

Почему много? Там просто все проходимые 
варианты, там 2 развилки, причем в обоих 
случаях там символьные классы. Причем из-за 
пустот в альтернативе, все переходы в 
развилке для \b тоже уходят в альтернативу. 
Там нет ничего лишнего.

Ну в этом пути нет 4 тега открывающегося, я 
не знаю в этом причина или нет. Я посмотрю, 
куда делся тег.

Original comment by eklepilkina@gmail.com on 2 Jan 2015 at 6:17

[GoogleCodeExporter]

У меня кстати этого фейла нет, но я 
поправила насчет 4 тега.

Original comment by eklepilkina@gmail.com on 2 Jan 2015 at 11:59

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 2 Jan 2015 at 4:20

[GoogleCodeExporter]

Просто явно остались тесты, где падает 
из-за захвата в длину переходов 
незахватывающих. Типо таких.
fa_matcher failed on regex '([a!?]|)\b([c+]|)' and string 'a ' 
(qtype_preg_cross_tests_from_preg_merging, 
data_for_test_assertions_wordboundary_20):
LENGTH:          0=>1, 1=>1, 2=>1, 
expected:
LENGTH:          0=>1, 1=>1, 2=>0, 

 А так по остальным тестам (я Вам писала в другом issue), я особо не знаю, где проблемы.

Original comment by eklepilkina@gmail.com on 2 Jan 2015 at 5:19

[GoogleCodeExporter]

Вроде бы проблема захвата в длину 
переходов сейчас должна решаться тегами. 
Надо проверить их в этом автомате....

Original comment by oasyc...@gmail.com on 2 Jan 2015 at 6:54

[GoogleCodeExporter]

Лен, судя по всему проблема в переходе 12-7. 
Там теги 7 и 5 соответствуют пустоте и 
второму подвыражению соответственно, они 
ведь должны быть в смёрженном переходе.

Original comment by vostreltsov@gmail.com on 2 Jan 2015 at 8:32

[GoogleCodeExporter]

Я не могу понять, почему фейлится следующий 
тест.
fa_matcher failed on regex '([a!]\b)+' and string '!a!a' 
(qtype_preg_cross_tests_from_preg_merging, 
data_for_test_assertions_wordboundary_42):
INDEX_FIRST:     0=>0, 1=>2, 
LENGTH:          0=>3, 1=>1, 
expected:
INDEX_FIRST:     0=>0, 1=>3, 
LENGTH:          0=>4, 1=>1, 

Результирующий и начальный автомат на 
картинках. В смерженном есть путь для !a!a - 
это 0->6->5->6->7->4. Но он почему-то по нему не 
идет. С тегами тоже все вроде также как на 
исходном.

Original comment by eklepilkina@gmail.com on 22 Jan 2015 at 7:38

Attachments:

• t3.png
• t4.png

[GoogleCodeExporter]

Вот тут тоже не знаю, что не так с тегами. В 
первом случае путь 0->13->7. Во втором - 0->12->7
fa_matcher failed on regex '([a!?]|)\b([c+]|)' and string ' c' 
(qtype_preg_cross_tests_from_preg_merging, 
data_for_test_assertions_wordboundary_20):
INDEX_FIRST:     0=>1, 1=>0, 2=>1,
expected:
INDEX_FIRST:     0=>1, 1=>1, 2=>1,

fa_matcher failed on regex '([a!?]|)\b([c+]|)' and string 'b ' 
(qtype_preg_cross_tests_from_preg_merging, 
data_for_test_assertions_wordboundary_20):
INDEX_FIRST:     0=>1, 1=>0, 2=>1,
expected:
INDEX_FIRST:     0=>0, 1=>0, 2=>0,

Original comment by eklepilkina@gmail.com on 22 Jan 2015 at 10:29

Attachments:

• t2.png

[GoogleCodeExporter]

Короче, я не знаю, что не так в этих случаях, 
и тех, что из другого issue. Мне нужно, чтобы Вы 
посмотрели и сказали, что не так. Остальное 
работает.

Original comment by eklepilkina@gmail.com on 24 Jan 2015 at 11:21

[GoogleCodeExporter]

То, что сегодня записывала, все относится к 
разным issue, но пока все здесь:
1. Выбор пути при незахватывающем переходе 
проходит неправильно.
2. Пустота  при пересечении незахватывающих 
должна уходить в mergedafter, иначе в before
3. При мержинге закрывающиеся теги в ^ и 
пустые все переносятся после ^, $ - 
открывающиеся теги и пустые до.

Original comment by eklepilkina@gmail.com on 11 Feb 2015 at 6:27

[GoogleCodeExporter]

2 - она точно в незахватывающих? Или дело 
зависит от того, в каком направлении она 
мержится?

Original comment by oasyc...@gmail.com on 11 Feb 2015 at 8:37

[GoogleCodeExporter]

Пофиксил wb20 и wb42

Original comment by vostreltsov@gmail.com on 12 Feb 2015 at 2:44

[GoogleCodeExporter]

Те фейлы в 20, которые на этой неделе я 
поправила, но там выявились, новые.
fa_matcher failed on regex '([a!?]|)\b([c+]|)' and string ' a' 
(qtype_preg_cross_tests_from_preg_merging, 
data_for_test_assertions_wordboundary_20):
INDEX_FIRST:     0=>1, 1=>1, 2=>1, 
LENGTH:          0=>0, 1=>0, 2=>0, 
expected:
INDEX_FIRST:     0=>1, 1=>1, 2=>2, 
LENGTH:          0=>1, 1=>1, 2=>0, 
Судя по фейлу, матчится путь полностью 
незахватывающий, почему так не могу понять.
А второй фейл
fa_matcher failed on regex '([a!?]|)\b([c+]|)' and string 'b+' 
(qtype_preg_cross_tests_from_preg_merging, 
data_for_test_assertions_wordboundary_20):
INDEX_FIRST:     0=>1, 1=>1, 2=>1, 
LENGTH:          0=>1, 1=>0, 2=>1, 
expected:
INDEX_FIRST:     0=>0, 1=>0, 2=>0, 
LENGTH:          0=>0, 1=>0, 2=>0, 
Во втором подвыражении захватывается +, я 
не очень понимаю, почему там должна быть 
пустота.

Original comment by eklepilkina@gmail.com on 14 Feb 2015 at 6:13

Attachments:

• fa.svg

[GoogleCodeExporter]

Это тоже fixed?

Original comment by vostreltsov@gmail.com on 7 Mar 2015 at 8:24

[GoogleCodeExporter]

Всех поздравляю, спасибо!

Original comment by oasyc...@gmail.com on 9 Mar 2015 at 2:05

• Changed state: Done