1. Oleg Sychev Avatar Oleg Sychev
  2. POAS Moodle plugins
  3. Moodle Plugins
  4. Issues

Странное поведение NFA-матчера при частичном совпадении при возврате подмасок

Issue #71 closed
Oleg Sychev repo owner created an issue

Originally reported on Google Code with ID 71 ``` Выражение [+\-]?([0-9]+)?\.([0-9]+)

Если я ввожу 12 т.е. 2 и более цифры без точки, она возвращает совпадение с первой подмаской.

Но если я ввожу 1 т.е. одну цифру - совпадения с первой подмаской нет.

В чем разница? ```

Reported by `oasychev` on 2011-11-29 19:39:27

Comments (16)

  3. Oleg Sychev reporter

    ``` Нахождение квантификатора в квантификаторе представляет проблему для многих матчеров (backtracking тоже с этим делом мучался...).

    Для полной проверки работоспособности этого дела необходимо составить набор кросс-тестов.

    Принципиальных параметра, влияющих на структуру автомата, у квантификатора два: возможность совпадения 0 раз и возможность совпадения бесконечное количество раз. Итого имеем 4 вида квантификаторов.

    Два квантификатора - один в другом - дают 4*4=16 видов регулярных выражений для тестирования. Размер совпадения с внутренним квантификатором необходимо проверить с помощью захвата подмаски.

    Совпадения должны удовлетворять условиям, изложеным в http://laurikari.net/ville/regex-submatch.pdf на стр. 7

    Когда все 16 тестов пройдут - переводим в Fixed.

    ```

    Reported by `oasychev` on 2011-11-29 20:47:07

  4. Oleg Sychev reporter

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

    Соответственно левую границу для ненулевых лучше выбирать больше 2, правую для конечных - так чтобы правая минус левая было не меньше чем 3 или 4.

    Разумеется, не к каждому квантификатору применимы все случаи... ```

    Reported by `oasychev` on 2011-11-29 21:12:31

  5. Valeriy Streltsov

    ``` На мой взгляд, PCRE немного нелогичен в некоторых ситуациях (по крайней мере в нашем случае - задание правильного ответа). Например, (ab|abc) на строке 'abc' захватит только первые два символа - я так понимаю, первое из трех правил той pdf'ки в действи... ИМХО, не нужно следовать такому правилу и захватывать самое длинное совпадение. И вообще, немного непонятно, как автомат проходить по "левым" путям вперед "правых" - рекурсивно, чтоли? Тогда в чем отличие от backtracking? ```

    Reported by `vostreltsov` on 2011-11-30 18:17:37

  6. Oleg Sychev reporter

    ``` Оно и есть backtracking. Я вам разве на PCRE ссылку давал? ```

    Reported by `oasychev` on 2011-11-30 19:16:12

  7. Oleg Sychev reporter

    Reported by `oasychev` on 2011-12-23 10:45:47 - Labels added: Milestone-Release2.2 - Labels removed: Milestone-Release2.1

  8. Valeriy Streltsov

    ``` Не получается соблюдать требования POSIX при нашей стратегии "меньше символов до полного совпадения".

    Все тот же тест: (?:a|b)*abb$ на строке 'ab' - дает опять 3 символа до завершения, и это соответствует правилу leftmost-longest... ```

    Reported by `vostreltsov` on 2012-02-11 10:58:28

  9. Oleg Sychev reporter

    ``` Разумеется. Мы с вами говорили уже в другом issue что первое правило (leftmost-longest) мы подменяем, у нас другие цели. А вот второе и третье - про подмаски и квантификаторы - соблюдаем, они связаны уже с распределением символов внутри совпадения... ```

    Reported by `oasychev` on 2012-02-11 16:31:36

  10. Valeriy Streltsov

    ``` В общем что я сделал. Приоритеты действительно оказались не нужны, добавились проверки в worse_than (пока что код не вытолкнут). Правило leftmost говорит о том, что захват подмаски k приоритетнее, чем захват k+n - это проверяется в цикле по всем подмаскам (точно так же как и в исходниках TRE). Аналогично проверяется и repeating rule - если при прочих равных условиях подмаска встречена позже, выбирается последний вариант.

    Вот как сейчас выглядят проверки:

    4. Longest match if ($other->length[0] > $this->length[0]) { return true; } elseif ($this->length[0] > $other->length[0]) { return false; } Leftmost rule foreach ($this->index_first as $key=>$value) { if ($key !== 0 && $value === qtype_preg_matching_results::NO_MATCH_FOUND && $other->index_first[$key] !== qtype_preg_matching_results::NO_MATCH_FOUND) { return true; } else if ($key !== 0 && $value !== qtype_preg_matching_results::NO_MATCH_FOUND && $other->index_first[$key] === qtype_preg_matching_results::NO_MATCH_FOUND) { return false; } } Repeating rule foreach ($this->length as $key=>$value) { if ($key !== 0 && $this->index_first[$key] < $other->index_first[$key]) { return true; } else if ($key !== 0 && $this->index_first[$key] > $other->index_first[$key]) { return false; } }

    После такой доработки тесты из matching strategy (после исправления некоторых ошибок) проходят. Выталкивать этот код? ```

    Reported by `vostreltsov` on 2012-02-12 15:18:44

  11. Oleg Sychev reporter

    ``` Подождите.

    Есть два вопроса: 1) вы достигли результата Вилли - количество состояний матчинга не больше количества состояний автомата? 2) эти проверки должны быть не в qtype_preg_matching_results::worse_than - а в вашем наследнике (переопределенной операции). Хорошо бы придумать вариант чтобы вызвать родительскую функцию, но тогда нужно как-то добавить в нее возможность возвращать что эквивалентны по предыдущим правилам... ```

    Reported by `oasychev` on 2012-02-12 18:18:41

  12. Valeriy Streltsov

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

    Reported by `vostreltsov` on 2012-02-13 11:57:53

  13. Oleg Sychev reporter

    ``` 1) По Вилли надо говорить всерьез, возможно при личной встрече и когда я сам уже его почитаю возможно. Сейчас это быстро не выйдет - завален огромным количеством орг. работы по кафедре в связи с проверками. 2) Есть идея сделать параметр по ссылке &$isequal для возврата эквивалентности - хотя сейчас можно проверить вызвав дважды с разными $orequal - но это неэффективно.

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

    Reported by `oasychev` on 2012-02-13 12:53:27

  14. Oleg Sychev reporter

    ``` Валерий, это уже Fixed? ```

    Reported by `oasychev` on 2012-04-05 15:30:13

  17. Log in to comment
Assignee
Type
bug
Priority
minor
Status
closed
Component
–
Votes
0
Watchers
0
Jira: the preferred issue tracker for Bitbucket. Join the team!