Судьба цикла перебора позиций и якорения

[Oleg Sychev]

Originally reported on Google Code with ID 190

Выражение X может рассматриваться как ^.*?(X).*$ , с подмаской с номером 0, в этом случае
пропадает необходимость в "несъедающих" переходах.  (разумеется, в многострочном режиме
можно вместо точки использовать вариант, который и переводы строки берет).

Но есть ряд вопросов:
а) в случае, если само выражение начинается с .*, будет ли матчер (отдельно ДКА/НКА)
вести себя заякорено, или начнет перебирать все варианты, и насколько это будет влиять
на производительность...  Возможно добавление начальных .*? должно зависеть от заякоренности
выражения.
б) следует ли делать завершающую .* ленивой? Возможно нужна настройка - показывать
студент самое длинное совпадение или самое короткое правильное, не уверен, что в разных
случаях одно и то же будет верным.
в) следует ли добавлять аналогичные вещи в автоматы пересекаемых ассертов или нет?


Валерий, Дмитрий - прошу не тянуть с вашими соображениями...

Reported by oasychev on 2013-04-11 09:33:06

[Valeriy Streltsov]

а) делать квантификаторы ленивыми мне кажется не нужно в принципе, поскольку как их
правильно поддерживать на 100% пока что непонятно. лучше бы добавить понятие направления
тегов (минимизации\максимизации) и ставить минимизацию (и индекса, и длины) начального
.* - как раз получится leftmost для самого выражения
б) последний .* - без разницы ленивый или нет, он имеет меньший приоритет чем выражение
X и на него никак не влияет
в) однозначно стоит добавить, потому что может быть ассерт в ассерте

Reported by vostreltsov on 2013-04-11 13:14:33

[Oleg Sychev]

а) Валерий, я не понял, чем ленивые квантификаторы отличаются от минимизации? 
Цитирую http://pcre.org/pcre.txt
 With  both  maximizing ("greedy") and minimizing ("ungreedy" or "lazy") repetition

Reported by oasychev on 2013-04-11 16:55:17

[Valeriy Streltsov]

Количество совпадений и длина совпадения немного разные вещи (по крайней мере по POSIX).
Для a* минимизироваться будет целиком a*, а ленивый квантификатор будет создавать как
можно меньше повторений только символа а. Т.е. тут два подшаблона и минимизируются\делаются
ленивыми разные.

Ввод направлений, имхо, хорошая штука. С его помощью можно будет более общим образом
обрабатывать leftmost longest правило: для подшаблона создаются два тега (минимизируемый
индекса и максимизируемый длины) и в зависимости от их направления сравниваются меньше-больше.
Для .* в начале оба тега будут минимизируемыми, причем leftmost longest останется абсолютно
без изменений.

Reported by vostreltsov on 2013-04-11 17:06:06

[Oleg Sychev]

Я думаю, что есть шанс что выигрыш для НКА мы получим в производительности. Надо будет
попробовать.

По хорошему, надо бы сделать простую функцию - нужно ли матчеру прибавлять к дереву
слева и справа ^.*( и обратное - тогда матчеры, которым это выгодно, могут перегружать
match_inner и вернуть true из этой функции; а кому не надо - реализовывать match_from_pos
и возвращать false (реализация в базовом матчере).
Функция может учитывать якорение, чтобы добавлять только если выражение не заякорено.

Reported by oasychev on 2013-04-26 13:55:26

[Oleg Sychev]

Валерий, посмотрите идею в начале этого issue. Возможно вместо доработки match_from_pos
от него вообще можно отказаться?

Reported by oasychev on 2015-03-01 22:32:46