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

[GoogleCodeExporter]

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

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

Original issue reported on code.google.com by oasyc...@gmail.com on 7 Jul 2014 at 8:22

[GoogleCodeExporter]

Original comment by oasyc...@gmail.com on 7 Jul 2014 at 8:33

[GoogleCodeExporter]

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

Original comment by vostreltsov@gmail.com on 8 Jul 2014 at 10:56

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 9 Jul 2014 at 7:01

[GoogleCodeExporter]

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

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

Original comment by vostreltsov@gmail.com on 9 Jul 2014 at 8:47

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 10 Jul 2014 at 1:28

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 11 Jul 2014 at 9:05

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 11 Jul 2014 at 9:26

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 12 Jul 2014 at 4:51

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 15 Jul 2014 at 6:34

[GoogleCodeExporter]

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

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

Original comment by oasyc...@gmail.com on 15 Jul 2014 at 8:17

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 15 Jul 2014 at 9:04

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 15 Jul 2014 at 9:24

[GoogleCodeExporter]

Добавил функцию 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 в 
дерево.

Original comment by pro100ho...@gmail.com on 16 Jul 2014 at 1:33

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 16 Jul 2014 at 10:04

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 17 Jul 2014 at 6:04

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 17 Jul 2014 at 7:52

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 18 Jul 2014 at 9:17

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 18 Jul 2014 at 9:50

[GoogleCodeExporter]

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

Мне по алгоритму необходимо сначала найти 
стартовый узел в $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_*** (как понял - 
оформление связи с последующим узлом).

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

Original comment by pro100ho...@gmail.com on 18 Jul 2014 at 12:33

[GoogleCodeExporter]

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

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

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

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

Original comment by oasyc...@gmail.com on 18 Jul 2014 at 12:51

[GoogleCodeExporter]

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

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

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

Original comment by pro100ho...@gmail.com on 18 Jul 2014 at 1:24

[GoogleCodeExporter]

Вообще не связывайтесь с хэндлерами. Я 
предложил вам вставить распечатку дерева в 
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, у последней 
еще два ребенка для букв. 

Original comment by oasyc...@gmail.com on 18 Jul 2014 at 2:36

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 18 Jul 2014 at 3:20

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 18 Jul 2014 at 3:25

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 18 Jul 2014 at 3:28

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 24 Jul 2014 at 6:20

[GoogleCodeExporter]

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

Там есть более редкие и сложные как 
операции, так и операнды. Если хотите 
пример - наберите в поиске 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.

Original comment by oasyc...@gmail.com on 24 Jul 2014 at 9:10

[GoogleCodeExporter]

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

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 сравнивать, чтобы 
определить к какому же именно классу 
принадлежит узел-надпись? или как-то иначе 
можно?

Original comment by pro100ho...@gmail.com on 24 Jul 2014 at 9:21

[GoogleCodeExporter]

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

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

Original comment by oasyc...@gmail.com on 24 Jul 2014 at 9:28

[GoogleCodeExporter]

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

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

Original comment by pro100ho...@gmail.com on 30 Jul 2014 at 4:17

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 3 Nov 2014 at 3:29

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 3 Nov 2014 at 4:01

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 3 Nov 2014 at 4:14

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 3 Nov 2014 at 8:59

[GoogleCodeExporter]

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

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

Original comment by pro100ho...@gmail.com on 9 Nov 2014 at 7:19

Attachments:

• макет.docx

[GoogleCodeExporter]

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

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

Original comment by oasyc...@gmail.com on 9 Nov 2014 at 11:12

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 8 Dec 2014 at 10:14

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 8 Dec 2014 at 10:51

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 8 Dec 2014 at 1:03

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 14 Jan 2015 at 1:13

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 16 Jan 2015 at 3:15

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 17 Jan 2015 at 9:36

[GoogleCodeExporter]

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

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

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

Original comment by oasyc...@gmail.com on 18 Jan 2015 at 2:34

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 20 Jan 2015 at 3:14

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 20 Jan 2015 at 3:17

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 21 Jan 2015 at 1:54

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 21 Jan 2015 at 2:05

[GoogleCodeExporter]

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

Original comment by pro100ho...@gmail.com on 31 Jan 2015 at 7:22

[GoogleCodeExporter]

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

Original comment by oasyc...@gmail.com on 8 Feb 2015 at 9:13