|
|
|
**disclaimer** требования к заданию описаны не полностью и должны уточняться по ходу работы (git pull request, комментарии к коммитам, тестам и т.п.)
|
|
|
|
|
|
|
|
Dot- [язык описания графов](https://en.wikipedia.org/wiki/DOT_(graph_description_language))
|
|
|
|
|
|
|
|
## Задача 1 ##
|
|
|
|
|
|
|
|
### 20 баллов
|
|
|
|
|
|
|
|
- Реализовать парсер подможества языка Dot:
|
|
|
|
- Направленные и не направленные графы
|
|
|
|
- метки (атрибуты) узлов
|
|
|
|
- комментарии
|
|
|
|
|
|
|
|
- Реализовать визитор по синтаксическому дереву, который бы выводил исходный документ в формате Markdown (том же, на котором написана эта вики)
|
|
|
|
|
|
|
|
[Полная грамматика языка](https://www.graphviz.org/doc/info/lang.html):
|
|
|
|
|
|
|
|
```
|
|
|
|
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];
|
|
|
|
}
|
|
|
|
```
|
|
|
|
|
