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.
	~Ast ()
bool	build ()
	Builds the DOT format AST.
Graph *	root () const
	Returns the root of the AST (nullptr if none).

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

Private Member Functions
AList *	parseAList (Iterator current, Iterator &rest)
AsgnStmt *	parseAsgnStmt (Iterator current, Iterator &rest)
AttrList *	parseAttrList (Iterator current, Iterator &rest)
AttrStmt *	parseAttrStmt (Iterator current, Iterator &rest)
CompassPt *	parseCompassPt (Iterator current, Iterator &rest)
EdgeRhs *	parseEdgeRhs (Iterator current, Iterator &rest)
EdgeStmt *	parseEdgeStmt (Iterator current, Iterator &rest)
Graph *	parseGraph (Iterator current, Iterator &rest)
NodeId *	parseNodeId (Iterator current, Iterator &rest)
NodeStmt *	parseNodeStmt (Iterator current, Iterator &rest)
Port *	parsePort (Iterator current, Iterator &rest)
Stmt *	parseStmt (Iterator current, Iterator &rest)
StmtList *	parseStmtList (Iterator current, Iterator &rest)
Subgraph *	parseSubgraph (Iterator current, Iterator &rest)

Private Attributes
Graph *	m_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 112 of file DotParser.h.

Member Typedef Documentation

Iterator

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

private

Definition at line 133 of file DotParser.h.

Tokens

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

private

Definition at line 132 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

tokens

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

m_tend

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

private

Definition at line 136 of file DotParser.h.

m_tokens

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

private

Definition at line 135 of file DotParser.h.

---

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

• include/ogdf/fileformats/DotParser.h