DOT format abstract syntax tree class, based on official documentation.
To provide easier modification and improve code readability the DOT format parsing process is divided to three stages. Building an abstract syntax tree is the second one. AST elements are also involved in reading to Graph, GraphAttributes, ClusterGraph and ClusterGraphAttributes.
This class provide method for building such tree from a token list. The AST is then represented by tree of structures corresponding to DOT's language abstract grammar. That grammar is nearly 100% like official one - minor adjustments have been made just for my convenience. Neverthless, my version should be equal to the official one in terms of represented language.
official DOT specification
* Graph = [ 'strict' ] ( 'graph' | 'digraph' ) [ id ] '{' [ StmtList ] '}'
* Subgraph = [ 'subgraph' [ id ] ] '{' StmtList '}'
*
* StmtList = Stmt [ ';' ] [ StmtList ]
* Stmt = NodeStmt | EdgeStmt | AttrStmt | AsgnStmt | Subgraph
*
* NodeStmt = NodeId [ AttrList ]
* NodeId = id [ port ]
*
* EdgeStmt = ( NodeId | Subgraph ) EdgeRhs [ AttrList ]
* EdgeRhs = ( '--' | '->' ) ( NodeId | Subgraph) [ EdgeRhs ]
*
* AttrStmt = ( 'graph' | 'node' | 'edge' ) AttrList
*
* AsgnStmt = id '=' id
*
* AttrList = '[' [ AList ] ']' [ AttrList ]
* AList = AsgnStmt [ ',' ] [ AList ]
*
* Port = ':' id [ ':' CompassPt ] | ':' CompassPt
* CompassPt = ( 'n' | 'ne' | 'e' | 'se' | 's' | 'sw' | 'w' | 'nw' | 'c' | '_' )
*
The AST building process tries to mirror given grammar as much as possible keeping the code clean and simple. Each grammar's nonterminal symbol has corresponding parse function. These parse functions take two args: current iterator and rest iterator. current iterator indicates a position where the parsing should begin. On successfull parse, function returns (pointer to) tree element and moves rest iterator to a place where it has ended. On failure, function returns nullptr
and does nothing to rest iterator.
Finally, non-list AST elements provide read methods. These functions allow to, surprisingly, read Graph structure and/or associated attributes. The entry point is Ast::Graph::read method which reads basic attributes like graph strictness and triggers recursively read of its ancestors.
- See also
- dot::Lexer
-
dot::Parser
Definition at line 112 of file DotParser.h.