Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::dot::Ast Class Reference

DOT format abstract syntax tree class, based on official documentation. More...

#include <ogdf/fileformats/DotParser.h>

Classes

struct  AList
 
struct  AsgnStmt
 
struct  AttrList
 
struct  AttrStmt
 
struct  CompassPt
 
struct  EdgeLhs
 
struct  EdgeRhs
 
struct  EdgeStmt
 
struct  Graph
 
struct  NodeId
 
struct  NodeStmt
 
struct  Port
 
struct  Stmt
 
struct  StmtList
 
struct  Subgraph
 

Public Member Functions

 Ast (const Tokens &tokens)
 Initializes AST building but does not trigger the process itself. More...
 
 ~Ast ()
 
bool build ()
 Builds the DOT format AST. More...
 
Graphroot () const
 Returns the root of the AST (nullptr if none). More...
 

Private Types

using Iterator = Tokens::const_iterator
 
using Tokens = std::vector< Token >
 

Private Member Functions

AListparseAList (Iterator current, Iterator &rest)
 
AsgnStmtparseAsgnStmt (Iterator current, Iterator &rest)
 
AttrListparseAttrList (Iterator current, Iterator &rest)
 
AttrStmtparseAttrStmt (Iterator current, Iterator &rest)
 
CompassPtparseCompassPt (Iterator current, Iterator &rest)
 
EdgeRhsparseEdgeRhs (Iterator current, Iterator &rest)
 
EdgeStmtparseEdgeStmt (Iterator current, Iterator &rest)
 
GraphparseGraph (Iterator current, Iterator &rest)
 
NodeIdparseNodeId (Iterator current, Iterator &rest)
 
NodeStmtparseNodeStmt (Iterator current, Iterator &rest)
 
PortparsePort (Iterator current, Iterator &rest)
 
StmtparseStmt (Iterator current, Iterator &rest)
 
StmtListparseStmtList (Iterator current, Iterator &rest)
 
SubgraphparseSubgraph (Iterator current, Iterator &rest)
 

Private Attributes

Graphm_graph
 
const Iterator m_tend
 
const Tokens m_tokens
 

Detailed Description

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 114 of file DotParser.h.

Member Typedef Documentation

◆ Iterator

using ogdf::dot::Ast::Iterator = Tokens::const_iterator
private

Definition at line 135 of file DotParser.h.

◆ Tokens

using ogdf::dot::Ast::Tokens = std::vector<Token>
private

Definition at line 134 of file DotParser.h.

Constructor & Destructor Documentation

◆ Ast()

ogdf::dot::Ast::Ast ( const Tokens tokens)
explicit

Initializes AST building but does not trigger the process itself.

Parameters
tokensDOT format token list to build the AST.

◆ ~Ast()

ogdf::dot::Ast::~Ast ( )

Member Function Documentation

◆ build()

bool ogdf::dot::Ast::build ( )

Builds the DOT format AST.

Returns
True if success, false otherwise.

◆ parseAList()

AList* ogdf::dot::Ast::parseAList ( Iterator  current,
Iterator rest 
)
private

◆ parseAsgnStmt()

AsgnStmt* ogdf::dot::Ast::parseAsgnStmt ( Iterator  current,
Iterator rest 
)
private

◆ parseAttrList()

AttrList* ogdf::dot::Ast::parseAttrList ( Iterator  current,
Iterator rest 
)
private

◆ parseAttrStmt()

AttrStmt* ogdf::dot::Ast::parseAttrStmt ( Iterator  current,
Iterator rest 
)
private

◆ parseCompassPt()

CompassPt* ogdf::dot::Ast::parseCompassPt ( Iterator  current,
Iterator rest 
)
private

◆ parseEdgeRhs()

EdgeRhs* ogdf::dot::Ast::parseEdgeRhs ( Iterator  current,
Iterator rest 
)
private

◆ parseEdgeStmt()

EdgeStmt* ogdf::dot::Ast::parseEdgeStmt ( Iterator  current,
Iterator rest 
)
private

◆ parseGraph()

Graph* ogdf::dot::Ast::parseGraph ( Iterator  current,
Iterator rest 
)
private

◆ parseNodeId()

NodeId* ogdf::dot::Ast::parseNodeId ( Iterator  current,
Iterator rest 
)
private

◆ parseNodeStmt()

NodeStmt* ogdf::dot::Ast::parseNodeStmt ( Iterator  current,
Iterator rest 
)
private

◆ parsePort()

Port* ogdf::dot::Ast::parsePort ( Iterator  current,
Iterator rest 
)
private

◆ parseStmt()

Stmt* ogdf::dot::Ast::parseStmt ( Iterator  current,
Iterator rest 
)
private

◆ parseStmtList()

StmtList* ogdf::dot::Ast::parseStmtList ( Iterator  current,
Iterator rest 
)
private

◆ parseSubgraph()

Subgraph* ogdf::dot::Ast::parseSubgraph ( Iterator  current,
Iterator rest 
)
private

◆ root()

Graph* ogdf::dot::Ast::root ( ) const

Returns the root of the AST (nullptr if none).

Member Data Documentation

◆ m_graph

Graph* ogdf::dot::Ast::m_graph
private

Definition at line 140 of file DotParser.h.

◆ m_tend

const Iterator ogdf::dot::Ast::m_tend
private

Definition at line 138 of file DotParser.h.

◆ m_tokens

const Tokens ogdf::dot::Ast::m_tokens
private

Definition at line 137 of file DotParser.h.


The documentation for this class was generated from the following file: