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

N-арность операций в дереве выражения strikes back

Issue #192 closed
Valeriy Streltsov created an issue

Originally reported on Google Code with ID 192

Нужно сделать нормальную реализацию пустоты в альтернативах. На данный момент она реализована
с небольшой ошибкой в случае (||||) - преобразование дерева срабатывает криво в случае
полностью право-ассоциативного дерева на входе.

Нужен либо эффективный и правильный алгоритм преобразования дерева, либо изменение
альтернативы\конкатенации на n-арные.

Лично я склоняюсь к n-арности, так как это - удаление преобразования дерева в принципе
и достаточно простой код внутри правил для альтернативы. Вдобавок к этому легко можно
оптимизировать (|||||) до (|). Для НКА (судя по всему и ДКА) и инструментов авторинга
изменений в существующем коде потребуется минимум.

Reported by vostreltsov on 2013-04-14 19:32:25

Comments (31)

  1. Valeriy Streltsov reporter 
    Преобразование дерева: preg_parser.y, строки 181...203 (функция make_operator_leftassoc).

    Reported by vostreltsov on 2013-04-14 20:23:50

  2. Oleg Sychev repo owner 
    А почему не поступить так: рекурсивно составить массив операндов к n-арной операции,
потом циклом по нему воссоздать левую ассоциативность? Так ее легко можно регулировать...
Можно заодно и одинаковые пустоты прибить... Вам что, лишний цикл жалко чтобы из n-арной
бинарную сделать?

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

    Reported by oasychev on 2013-04-15 15:40:22

  3. Oleg Sychev repo owner 
    n-арность может быть сделана, если  все матчеры будут по ней работать сразу. Ну и 3-й
курс тоже оповестить придется...

    Reported by oasychev on 2013-04-15 15:58:24

  4. Oleg Sychev repo owner 
    Issue 183 has been merged into this issue.

    Reported by oasychev on 2013-04-15 16:09:05

  5. Oleg Sychev repo owner 
    Подписывают третий курс - проверить работу с n-арными операциями дерева и описания,
граф вроде был сделан.

    Reported by oasychev on 2013-04-18 15:25:45

  7. Oleg Sychev repo owner 
    Я бы в связи с n-арностью сделал в дереве два режима для конкатенации и альтернативы:
n-арный (свернутый) и бинарный (развернутый). Переключать их можно, например, по двойному
щелчку на соответствующем узле.

Для матчеров же N-арность позволяет легко сделать поддержку настройки ассоциативности
конкатенации? Может ее добавить в параметры матчинга?

    Reported by oasychev on 2013-04-21 20:22:08

  9. Valeriy Streltsov reporter 
    Для матчера ассоциативность можно менять и порядком обхода операндов, т. е. в зависимости
от параметра дописывать array_reverse($node->operands) или нет.

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

Говоря проще, ассоциативность я бы добавил на уровне парсинга\матчеров, но в "бинаризации"
деревьев смысла не вижу.

    Reported by vostreltsov on 2013-04-21 20:39:21

  10. Oleg Sychev repo owner 
    Юзеры бывают разные - этот набор инструментов в т.ч. может использоваться и при изучении
регексов на ТЯПе и аналогичных дисциплинах (для понимающих - этот вариант внедрения
гораздо быстрее и надежнее по отзывам, чем ждать пока откликнуться зарубежные юзеры
вопроса). Поэтому по умолчанию надо свернуть, а при щелчке можно и разворачивать -
не так уж это и сложно...

    Reported by oasychev on 2013-04-21 21:04:54

  11. Oleg Sychev repo owner 
    Ну так мы мы доделаем переключение режимов?

    Reported by oasychev on 2013-06-26 14:42:52

  12. Oleg Sychev repo owner

    Reported by oasychev on 2013-07-02 14:22:22 - Labels added: Priority-Low - Labels removed: Priority-Medium

  13. Oleg Sychev repo owner 
    У N-арности выявилось крайне неприятное свойство для инструментов авторинга: она сильно
ограничивает возможности выделения пользователем части регекса и просмотра этой части
везде (а это важная функция). По сути например юзер может выделить либо один подшаблон,
либо весь регекс - два конкатенированных подшаблона выделить уже нельзя.

Есть предложение устроить в N-арных preg-узлах функцию, которая бы возвращала их развертку
в бинарные узлы без клонирования поддеревьев. Точнее ей передается два индекса узлов
- начало и конец участка, который надо развернуть в бинарное поддерево.

    Reported by oasychev on 2013-07-05 15:33:50

  14. Oleg Sychev repo owner 
    Это надо к релизу, иначе у инструментов авторинга будут серьезные проблемы...

    Reported by oasychev on 2013-07-05 15:34:33 - Labels added: Priority-High - Labels removed: Priority-Low

  15. Valeriy Streltsov reporter 
    Предлагаю сделать просто опцию парсинга. Внутри парсера сделать функцию expand и вызывать
ее из правил конкатенации\альтернативы.

    Reported by vostreltsov on 2013-07-05 15:46:39

  16. Oleg Sychev repo owner 
    expand($from, $to)
предположим у нас есть N-арный узел с 10 детьми, from=2 to=5
 я:  получаем N-арный узел, детьми которого являются узлы  от 0 до 1, развернутое бинарное
дерево узлов от 2 до 5 и узлы от 6 до 9
поддеревья не клонируются - модифицировать их никто не будет...
 Valeriy:  надо поддерево возвратить, или само его преобразовать?
 я:  возвратить новое поддерево (корневым узлом), устроенное так как я сказал, но без
клонирования узлов-детей оригинального N-арного узла

    Reported by oasychev on 2013-07-05 15:58:40

  17. Valeriy Streltsov reporter 
    Я посмотрел на парсер. Почему бы не сделать это опцией именно парсинга? Сделать у него
константы ассоциативности (три штуки, на левую, правую и n-арность) и задавать её опцией?
Будет намного проще и с точки зрения кода, и использования. У функции expand еще есть
проблема - нету своего счетчика id.

    Reported by vostreltsov on 2013-07-06 17:04:33

  18. Former user Account Deleted 
    Я поддерживаю Валеру. Думаю, это нам не принципиально, а реализовать проще.

    Reported by ZluMYO on 2013-07-06 17:06:19

  19. Oleg Sychev repo owner 
    На комментарии 17 и 18: все хорошо, кроме того что это будет сильно неудобно для пользователя.

Предложенный вами вариант заставляет либо разворачивать все, либо ничего. Т.е. если
юзер хочет выделить 2-3 конкатенации, он вынужден разворачивать весь регекс в огромных
размеров баобаб...

Мой вариант - разворачивать только ту часть, которую выделил юзер - точнее если границы
выделения находятся внутри N-арного узла, то разворачивать только этот узел, причем
не весь - а только выделенную часть. Таким образом мы сохраняем свободу выделения и
имеем при этом дерево намного компактнее (только выделение делается в этом случае через
текст, через дерево это не так просто будет).

Через предложенную выше функцию это легко реализуется. Причем id у новых узлов будут
строится по принципу <id n-арного узла>_<индекс левого(правого, в зависимости ассоциативности)
ребенка n-арного узла с которым данный узел связан напрямую>. Это дает легкую ссылку
на эти узлы. И развернуть тоже несложно.

    Reported by oasychev on 2013-07-09 12:08:59

  20. Oleg Sychev repo owner 
    Прикладываю два рисунка как примерно должно выглядить - сорри, делал в спешке, но идею
должно продемонстрировать. На первом показан неразвернутый N-арный узел, на втором
- развернутый когда пользователь выделил узлы с С_1 по С_3.

При это все остальные узлы графа остаются прежними...

    Reported by oasychev on 2013-07-09 12:33:44

    <hr> * Attachment: chart_notexpanded.png<br>chart_notexpanded.png * Attachment: chart_expanded.png<br>chart_expanded.png

  21. Oleg Sychev repo owner 
    Делаем еще в preg-узлах функцию определения корня дерева по переданному диапазону в
тексте (строка и столбец начала, строка и столбец конца). Функция обновляет данные
диапазона при необходимости в сторону расширения до ближайшего полного узла - но сначала
протестировать лексер на предмет работы в многострочном режиме!

    Reported by oasychev on 2013-07-12 14:42:25

  22. Valeriy Streltsov reporter 
    Лексер\парсер доработаны, функции добавлены.

    Reported by vostreltsov on 2013-07-13 16:12:41

  23. Oleg Sychev repo owner 
    Теперь нам нужен таки текстовый элемент для выделения.

    Reported by oasychev on 2013-07-15 15:13:32

  24. Oleg Sychev repo owner 
    Функции оказались неудачными - в итоге из-за N-арности бета без выделения осталась :(((
Почему-то две функции - одна разворачивающая поддерево, другая - находящая подходящий
узел - оказались никак не связанными. А именно при поиске по координатам подходящего
узла может потребоваться развернуть дерево - и тот же поиск по координатам может точно
определить

Как это должно происходить в самом деле:
1) конструктор инструмента авторинга получает информацию о координатах выделения и
сохраняет ее в полях класса до вызова родительского конструктора;
2) конструктор инструмента авторинга должен перегружать build_dst(), в нем сначала
обновить абстрактное дерево так, чтобы узлы развернулись, затем по нему построить конкретное

Нужно хотя бы к релизу это сделать.

1. Сделать функцию, совмещающую функцию предыдущих двух: она получает координаты выделения,
если надо их обновляет, - но при поиске подходящего узла дерева учитывает, что N-арный
узел можно и развернуть, если таким образом получим более точное приближение; эта функция
изменяет ast и обновляет координаты. - Стрельцов
2. Эта функция будет вызываться в классе абстрактного инструмента в build_dst() перед
построением конкретного дерева - Пахомов
3. Конструктор инструмента авторинга получает параметры с координатами и сохраняет
их в полях класса (в названиях полей - слово selection должно встречаться) - Пахомов

    Reported by oasychev on 2013-07-24 16:34:31 - Labels added: Priority-Critical - Labels removed: Priority-High

  25. Valeriy Streltsov reporter 
    Я исправил свою функцию, тесты вроде бы проходят, теперь бы посмотреть как это будет
выглядеть в инструментах авторинга.

    Reported by vostreltsov on 2013-08-16 17:46:17

  26. Oleg Sychev repo owner 
    Валерий - я бы сделал более подробный PHPDoc - комментарий к find_node_by_indexes  -
он теперь далек от того, что делает функция...

    Reported by oasychev on 2013-08-16 18:48:25

  28. Oleg Sychev repo owner 
    Есть мнение, что удобнее размещать в узлах дополнительную информацию об индексе символа
от начала строки и передавать в функцию find_node_by_indexes именно их, чтобы не пересчитывать.
Требует доработки лексера/абстрактного узла, но бережет от ошибок при пересчете координат.
Алгоритм пересчета уже используется как минимум в двух местах, причем на разных языках
- на PHP и javascript....

    Reported by oasychev on 2013-09-04 21:22:45

  29. Valeriy Streltsov reporter 
    Мнение учтено/реализовано :)

    Reported by vostreltsov on 2013-09-10 13:22:28

  30. Oleg Sychev repo owner 
    Тогда ждем виджет выделения от Пахомова, сколько уже можно?

    Reported by oasychev on 2013-09-10 19:03:27

  31. Oleg Sychev repo owner 
    Проблемы с N-арностью решены, главным образом усилиями Валерия (с некоторыми подсказками
;)

    Reported by oasychev on 2013-09-20 12:29:39 - Status changed: Done

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