dot_parser

disclaimer требования к заданию описаны не полностью и должны уточняться по ходу работы (git pull request, комментарии к коммитам, тестам и т.п.)

Dot- язык описания графов

Задача 1

40 баллов

• Реализовать парсер подможества языка Dot:
  • Направленные и не направленные графы
  • метки (атрибуты) узлов
  • комментарии

Полная грамматика языка:

graph	:	[ strict ] (graph | digraph) [ ID ] '{' stmt_list '}'
stmt_list	:	[ stmt [ ';' ] stmt_list ]
stmt	:	node_stmt
|	edge_stmt
|	attr_stmt
|	ID '=' ID
|	subgraph
attr_stmt	:	(graph | node | edge) attr_list
attr_list	:	'[' [ a_list ] ']' [ attr_list ]
a_list	:	ID '=' ID [ (';' | ',') ] [ a_list ]
edge_stmt	:	(node_id | subgraph) edgeRHS [ attr_list ]
edgeRHS	:	edgeop (node_id | subgraph) [ edgeRHS ]
node_stmt	:	node_id [ attr_list ]
node_id	:	ID [ port ]
port	:	':' ID [ ':' compass_pt ]
|	':' compass_pt
subgraph	:	[ subgraph [ ID ] ] '{' stmt_list '}'
compass_pt	:	(n | ne | e | se | s | sw | w | nw | c | _)

Пример:

 graph ethane {
     C_0 -- H_0 [type=s];
     C_0 -- H_1 [type=s];
     C_0 -- H_2 [type=s];
     C_0 -- C_1 [type=s];
     C_1 -- H_3 [type=s];
     C_1 -- H_4 [type=s];
     C_1 -- H_5 [type=s];
 }

Задача 2

20 баллов

Найти готовый парсер языка Dot и написать визитор по синтаксическому дереву, который бы формировал несколько представлений графа и выводил их в файл:

• матрицу смежности
• список инцидентности
• список ребер

Задача 3

20 баллов

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