Объясняющий граф->дерево - практика 2014

[Oleg Sychev]

Originally reported on Google Code with ID 288

Написать код, переводящий в дерево регулярного выражения из наследников preg_node из
а) dot-кода
б) классов explanation graph (после оптимизации)

Расширить по всем видам узлов графа.

Reported by oasychev on 2014-07-07 08:22:06

[Oleg Sychev]

Reported by oasychev on 2014-07-07 08:33:48

[Valeriy Streltsov]

Виртуалку скопировал на комп в 902, который сразу за дверью справа (на мониторе написано
19). Она лежит в диске D:\moodle vm.
Там сам образ и небольшое readme.

Reported by vostreltsov on 2014-07-08 10:56:33

[Former user]

Необходимы пояснения по этой строке - "из наследников preg_node из dot-кода".. На какие
файлы ориентироваться? Что нужно реализовать в этой части?..

Reported by pro100hobit on 2014-07-09 07:01:55

[Valeriy Streltsov]

Есть файл preg_nodes.php - это узлы абстрактного синтаксического дерева, такое дерево
должно быть на выходе. Можешь посмотреть файл tests/parser_test.php - там есть структуры
для всех возможных операций.

dot-код генерируется dst-узлами и прочими классами графа: authoring_tools/preg_explaining_graph_xxx
Какой он получается можно видеть в тестах tool_explaining_graph_test.php. Внизу два
закомменченных теста, в которых вызывается создание дот-кода.

Reported by vostreltsov on 2014-07-09 08:47:10

[Oleg Sychev]

Как дела, чего достигли, какие вопросы появились?

Reported by oasychev on 2014-07-10 13:28:55

[Former user]

1)Установил виртуалку. Запустил тесты tool_explaining_graph_test.php. Распечатал граф.
Получил пример графа.
2)Перевёл на PHP несколько функций (необходимы для функции addSubgraph) и тесты к ним
(пока без адаптации к полученным в пункте 1 примерам графа).
3)Веду разработку функции, выделяющей subgraph графа(addSubgraph). Есть отличия между
моим классом и классом qtype_preg_explaining_graph_tool_subgraph, что, вероятно,приведёт
к трудностям при адаптации на язык PHP моего хода решения на C++. Например, в своем
классе я не хранил узлы, связи, вложенные подграфы и т.д. 

Reported by pro100hobit on 2014-07-11 09:05:51

[Oleg Sychev]

Если пишете код - почему не коммиттите и не выталкиваете на гугль-коде? Это позволяет
мне следить за вашим прогрессом и поправлять если надо. Это должно делаться постоянно,
по мере разработки кода! А я даже клона от вас пока не увидел (Сперцян уже завел, но
не выталкивал еще ничего)

Reported by oasychev on 2014-07-11 09:26:22

[Oleg Sychev]

В понедельник в 13-30 встреча будет в политехе. Быть всем, кто по моим задачам работает.
Лучше взять ноутбуки потому что многим надо показать:
а) что делать с меркуриалом и клонами
б) вопросы по коду

Reported by oasychev on 2014-07-12 16:51:47

[Former user]

В результате анализа графа должна получиться переменная - подграф ($graph). Такой вопрос
- можно ли на выходе еще получить вектор узлов графа (если нужно будет, также вектор
подграфов, связей и т.д.),т.е. конечная функция будет такой -analysis_subgraph($digraph,
$pos, &$nodesofgraph), или на выходе только $graph?

Reported by pro100hobit on 2014-07-15 18:34:57

[Oleg Sychev]

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

Что вы понимаете под "анализом графа" - считывание dot в граф? 

Reported by oasychev on 2014-07-15 20:17:30

[Former user]

"А зачем вам еще вектор этих узлов?" В прошлой работе было, возможно, понадобится и
здесь.
"Что вы понимаете под "анализом графа" - считывание dot в граф?" Да.

Reported by pro100hobit on 2014-07-15 21:04:26

[Oleg Sychev]

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

Reported by oasychev on 2014-07-15 21:24:05

[Former user]

Добавил функцию analysis_subgraph. В неё нужно ещё добавить выделение связей для узлов.
Пока не придумал как реализовать это наилучшим образом. Какие будут советы?

Пока мой вариант такой:
при обнаружении в строке "->" выделять источник и получатель, а именно их имена:
например, строка '"nd2_0_1" -> "nd4"[id="graphid_6", label="", arrowhead="normal",
color="black", tooltip="", ]'.
Выделяю источник: nd2_0_1 .
Выделяю получатель: nd4 .
Преобразовываю в graphid.
В итоге: 
1)graphid2_0_1 ;
2)graphid4 .
Вызов функции, которая по этим graphid найдет мне указатели на узлы в $graph.
Заполнение полей объекта класса link полученными значениями.

Перехожу к выполнению перевода из $graph в дерево.

Reported by pro100hobit on 2014-07-16 13:33:09

[Oleg Sychev]

Можно составить карту (в PHP просто массив) с ключом graphid и значением - ссылкой (указателей
нет - но все объекты работают как ссылки автоматически) на узел в $graph. Как локальную
переменную при функции считывании графа.

Reported by oasychev on 2014-07-16 22:04:20

[Former user]

А вообще... можно одним коммитом охватывать добавление тестов и функции..? Или нужно
делать два разных коммита?

Reported by pro100hobit on 2014-07-17 18:04:20

[Oleg Sychev]

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

Reported by oasychev on 2014-07-17 19:52:13

[Former user]

Для синтаксического дерева есть какой-нибудь класс?

Reported by pro100hobit on 2014-07-18 09:17:39

[Oleg Sychev]

Для дерева как такового класса нет - он не нужен. Дерево создается из узлов-наследников
qtype_preg_node - см. preg_node.php
Чтобы распечатать пример дерева можно использовать parser_test - парсер это код, создающий
дерево из самого регулярного выражения...

Reported by oasychev on 2014-07-18 09:50:26

[Former user]

Посмотрел файлы, понял частично.

Мне по алгоритму необходимо сначала найти стартовый узел в $graph. После этого проводится
его анализ, следовательно, его добавление как узел дерева.

Т.е. мне необходимо после поиска этого узла написать такие строки кода?
$handler = $this->run_handler('');
$root = $handler->get_ast_root();
Или можно как-то иначе создать $root ($astroot класса qtype_preg_regex_handler)?

Как я понимаю по тестам, именно он заполняется.

Далее $root->type == TYPE_LEAF_*** (пока не решил, что именно подходит для стартового
узла, ведь потом он будет заменен на конкатенацию или вовсе удален (будет ли это возможно
потом?))

$root->operands[0]->type === TYPE_LEAF_*** (как понял - оформление связи с последующим
узлом).

На верном пути ли я?

Reported by pro100hobit on 2014-07-18 12:33:48

[Oleg Sychev]

Не очень верном.
Хэндлеры вас не касаются вообще (пока по крайней мере). Они только возможность посмотреть
в деле на дерево. Смысл хэндлера - в получении дерева из регулярного выражения.

Вам нужно создать в своей переменной и вернуть из функции то, что нормальный хедлер
хранить в ast_root - но с самим хэндлером и ast_root дела вам иметь не надо.

Я не знаю что вы за стартовый узел графа понимаете - граф не дерево, корня не имеет.
Там есть очень специфического цвета узел с написанием begin - от него идет начало графа.

$root - это про дерево, а не про граф. LEAF - это лист, конечная точка на дереве. Операнд
для выражения. Корнем лист может быть только если выражение без единой операции, что
бывает очень редко. А так корнем может быть все, что угодно - какая операция последней
вычисляется, так и корень...

Reported by oasychev on 2014-07-18 12:51:40

[Former user]

"Вам нужно создать в своей переменной и вернуть из функции то, что нормальный хедлер
хранить в ast_root"... То есть мне нужно поля унаследовать или что? 
Не нашел, где именно прописаны поля ast_root. В preg_regex_handler.php нашел по поиску
id, operands, subpattern и всё. В общем смысле понятно, как реализовывать - вообще
ничего не понял.

"Там есть очень специфического цвета узел с написанием begin - от него идет начало
графа." Да, да, да! Именно он. Всегда его имел ввиду.

...Олег Александрович, не могли бы Вы, хоть пример кода(узлы дерева и их связи)набросать
какой-нибудь(например, для такого регулярного выражения '\b(a|b)'). Это сразу упростило
бы мне понимание и я бы, возможно, приступил бы уже к решению.

Reported by pro100hobit on 2014-07-18 13:24:30

[Oleg Sychev]

Вообще не связывайтесь с хэндлерами. Я предложил вам вставить распечатку дерева в https://code.google.com/r/pro100hobit-preg-graph-to-tree/source/browse/question/type/preg/tests/parser_test.php
- просто потому, что там легче всего получить готовое дерево и полюбоваться как оно
выглядит. Можете вписать туда любой регекс (хоть ваш), закомментировать ассерты и напечатать
$ast_root (возможно сейчас уже без подчеркивания - astroot).

Вам же надо создать аналогичное дерево, но без парсера/хендлера - из графа.

Дети узлов хранятся для операций - соответственно поле для них объявлено в классе qtype_preg_operator
который является промежуточным между node и конкретными операторами

В вашем случае корнем будет конкатенация (что-то типа qtype_preg_concat), от нее два
ребенка - qtype_preg_leaf_assert и qtype_preg_leaf_alternative, у последней еще два
ребенка для букв. 

Reported by oasychev on 2014-07-18 14:36:44

[Former user]

Так?
$tree = new qtype_preg_concat;
$tree->operands[] = new qtype_preg_leaf_assert;
$tree->operands[] = new qtype_preg_leaf_alternative;
$tree->operands[1]->operands[] = для 1 буквы...

Reported by pro100hobit on 2014-07-18 15:20:24

[Oleg Sychev]

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

Reported by oasychev on 2014-07-18 15:25:19

[Former user]

Спасибо большое! Теперь всё понятно. Приступаю.

Reported by pro100hobit on 2014-07-18 15:28:50

[Former user]

Есть qtype_preg_node_cond_subexpr... Нужно ли мне это? Если да, то необходим пример
регулярного выражения.

Reported by pro100hobit on 2014-07-24 06:20:34

[Oleg Sychev]

Нужно, но не обязательно прямо сейчас - сейчас достаточно в том объеме, который был
на НКПО. При доделке до диплома нужно обязательно.

Там есть более редкие и сложные как операции, так и операнды. Если хотите пример -
наберите в поиске Conditional Subpattern Regular Expression . описание всех возможностей
есть в http://pcre.org/pcre.txt - но там надо разыскивать по названию...

Вот начало оттуда:
CONDITIONAL SUBPATTERNS

       It  is possible to cause the matching process to obey a subpattern con-
       ditionally or to choose between two alternative subpatterns,  depending
       on  the result of an assertion, or whether a specific capturing subpat-
       tern has already been matched. The two possible  forms  of  conditional
       subpattern are:

         (?(condition)yes-pattern)
         (?(condition)yes-pattern|no-pattern)

       If  the  condition is satisfied, the yes-pattern is used; otherwise the
       no-pattern (if present) is used. If there are more  than  two  alterna-
       tives  in  the subpattern, a compile-time error occurs. Each of the two
       alternatives may itself contain nested subpatterns of any form, includ-
       ing  conditional  subpatterns;  the  restriction  to  two  alternatives
       applies only at the level of the condition. This pattern fragment is an
       example where the alternatives are complex:

         (?(1) (A|B|C) | (D | (?(2)E|F) | E) )


       There  are  four  kinds of condition: references to subpatterns, refer-
       ences to recursion, a pseudo-condition called DEFINE, and assertions.

Reported by oasychev on 2014-07-24 09:10:07

[Former user]

понятно, пока не буду туда соваться..

subgraph "cluster_1_0_4" {style=dotted;color=black;bgcolor=white;label=" repeated at
least 3 times";id="graphid_1_0_4";tooltip="quantifier";(соответствует qtype_preg_node_infinite_quant)

и
subgraph "cluster_1_0_5" {style=dotted;color=black;bgcolor=white;label=" repeated no
more than 3 times or missing";id="graphid_1_0_5";tooltip="quantifier";(соответствует
классу qtype_preg_node_finite_quant)
По параметрам различий не нашел.. мне по ключевым словам из label сравнивать, чтобы
определить к какому же именно классу принадлежит узел-надпись? или как-то иначе можно?

Reported by pro100hobit on 2014-07-24 09:21:34

[Oleg Sychev]

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

Фразы можно поискать в question/type/preg/lang/en/qtype_preg.php - только там ВСЕ фразы
вообще. Однако зная фразы квантификаторов можно найти соответствующий раздел этого
файла и выписать их все. Учтите, что там будут подстановки (например для чисел) - в
виде {$a} или {$a->field} а не в точности те фразы что вы видите на экране, но по словам
и структуре предложения поиском раздел найти можно.

Reported by oasychev on 2014-07-24 09:28:14

[Former user]

Исправил.. теперь бесконечного цикла нет.

Принимаюсь за тесты.

Reported by pro100hobit on 2014-07-30 16:17:03

[Former user]

Олег Александрович, что такое mockup? (записано у меня в листке; возможно, не так записал)

Reported by pro100hobit on 2014-11-03 15:29:31

[Oleg Sychev]

Это черновик интерфейса пользователя, есть спец. программы по их составлению.

Reported by oasychev on 2014-11-03 16:01:03

[Former user]

Правильно ли я понимаю, что первым шагом мне нужно создать макет формы редактора для
edu.vstu.org?

Reported by pro100hobit on 2014-11-03 16:14:49

[Oleg Sychev]

Да. И к макету описание как это будет работать. Но параллельно надо выбрать на какой
технологии это будет основано (насколько и как используется dot, или чисто самим и
т.д.) - и обосновать это с конкретными аргументами почему так лучше.

Reported by oasychev on 2014-11-03 20:59:05

[Former user]

Высылаю очень сырые наброски. Интересует: корректно ли я мыслю, если не так, то что
не так? Написал мало, так как не вижу смысла пока писать обширней без критики, хотя
работы там очень много.

И еще такой вопрос, Олег Александрович. Когда у нас встреча? (переспрашиваю, чтобы
точно знать)

Reported by pro100hobit on 2014-11-09 19:19:26

<hr> * Attachment: макет.docx

[Oleg Sychev]

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

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

Reported by oasychev on 2014-11-09 23:12:42

[Former user]

Задачу оставляю за собой, Олег Александрович.

Reported by pro100hobit on 2014-12-08 10:14:39

[Oleg Sychev]

А где вы сегодня есть то?

Reported by oasychev on 2014-12-08 10:51:48

[Former user]

Не видел смысла приходить.
Мало сделал.
Разобрался только в добавлении прямоугольников по клику и их перемещению.
http://jsfiddle.net/anokegta/

Reported by pro100hobit on 2014-12-08 13:03:30

[Former user]

Здравствуйте, Олег Александрович. Хотелось бы снова услышать критику по макету, высланному
ранее.

Reported by pro100hobit on 2015-01-14 13:13:44

[Oleg Sychev]

Вы имеете в виду макет от 9 ноября или JS-ку?
JS пока странная, непонятно какое отношение она имеет к результату... Потому что рисовать
прямоугольники произвольного размера в произвольном месте там особо не нужно. Там нужно
прямоугольник определенного размера к графу подцепить например....

Reported by oasychev on 2015-01-16 15:15:47

[Former user]

Макет от 9 ноября

Reported by pro100hobit on 2015-01-17 09:36:36

[Oleg Sychev]

Сорри, два экзамена плюс активизация курсовых у 4-го курса.

По 9 ноября два замечания по имеющемуся тексту:
1) Не совсем куда угодно можно перемещать вершины, старт должен быть всегда левее конца.
Вообще советую поддерживать правило  - «то, что матчится после, должно быть правее»
- оно интуитивно ясно для пользователя.
2) Под элементом "слово" вы наверное последовательность символов имели ввиду. Там не
обязательно слово, любая последовательность без развилок, циклов и вариантов будет
в одном узле. Иначе граф просто гигантским выйдет…

Вообще же в документе очень мало внимания уделено первому разделу - внешней спецификации
- как это все должно работать. Как добавлять новые узлы, развилки, повторения. Как
определяется узла положение при вставке - с какими они будут связаны. Как редактировать
и перемещать существующие узлы (включая разбитие узла типа "последовательность символов"
на несколько элементов если в середину надо вставить развилку, повторение и т.д.).
Ответов на эти вопросы я не вижу. Нужны "пользовательские истории" (имею такой-то граф,
делаю такое-то изменение - описание действий мышкой/клавиатурой - и ожидаемый результат)
про все виды действий с графом.

Reported by oasychev on 2015-01-18 14:34:05

[Former user]

А вообще... с Вами когда можно встретиться?

Reported by pro100hobit on 2015-01-20 15:14:00

[Oleg Sychev]

В пятницу у меня экзамен, в свободное от студентов время можно поговорить...

Reported by oasychev on 2015-01-20 15:17:45

[Former user]

А время, аудитория?

Reported by pro100hobit on 2015-01-21 13:54:25

[Oleg Sychev]

Где и как у нас экзамены по "основам программирования" обычно проходят вы уже забыли?
Экзамен у меня с утра, а когда именно в его течении будет свободное время - это уж
как получится...

Reported by oasychev on 2015-01-21 14:05:07

[Former user]

А конструктор регулярных работает на http://edu.vstu.org/? Жму на "показать" - реакции
никакой.

Reported by pro100hobit on 2015-01-31 19:22:47

[Oleg Sychev]

Вроде наладил, попробуйте.

Reported by oasychev on 2015-02-08 21:13:42

[Oleg Sychev]

Работа давно закончена.