dot.bnf

//Copyright 2013 Vastech SA (PTY) LTD
//
//Licensed under the Apache License, Version 2.0 (the "License");
//you may not use this file except in compliance with the License.
//You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
//Unless required by applicable law or agreed to in writing, software
//distributed under the License is distributed on an "AS IS" BASIS,
//WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//See the License for the specific language governing permissions and
//limitations under the License.

//This bnf has been derived from http://www.graphviz.org/content/dot-language
//The rules have been copied and are shown in the comments, with their derived bnf rules below.

//graph	:	[ strict ] (graph | digraph) [ ID ] '{' stmt_list '}'
DotGraph
    : Graph "{" "}"                                     << ast.NewGraph(ast.GRAPH, ast.FALSE, nil, nil) >>
    | Strict Graph "{" "}"                              << ast.NewGraph(ast.GRAPH, ast.TRUE, nil, nil) >>
	| Graph Id "{" "}"                                  << ast.NewGraph(ast.GRAPH, ast.FALSE, $1, nil) >>
    | Strict Graph Id "{" "}"                           << ast.NewGraph(ast.GRAPH, ast.TRUE, $2, nil) >>
	| Graph "{" StmtList "}"                            << ast.NewGraph(ast.GRAPH, ast.FALSE, nil, $2) >>
	| Graph Id "{" StmtList "}"                         << ast.NewGraph(ast.GRAPH, ast.FALSE, $1, $3) >>
    | Strict Graph "{" StmtList "}"                     << ast.NewGraph(ast.GRAPH, ast.TRUE, nil, $3) >>
	| Strict Graph Id "{" StmtList "}"                  << ast.NewGraph(ast.GRAPH, ast.TRUE, $2, $4) >>
    | Digraph "{" "}"                                   << ast.NewGraph(ast.DIGRAPH, ast.FALSE, nil, nil) >>
    | Strict Digraph "{" "}"                            << ast.NewGraph(ast.DIGRAPH, ast.TRUE, nil, nil) >>
	| Digraph Id "{" "}"                                << ast.NewGraph(ast.DIGRAPH, ast.FALSE, $1, nil) >>
    | Strict Digraph Id "{" "}"                         << ast.NewGraph(ast.DIGRAPH, ast.TRUE, $2, nil) >>
	| Digraph "{" StmtList "}"                          << ast.NewGraph(ast.DIGRAPH, ast.FALSE, nil, $2) >>
	| Digraph Id "{" StmtList "}"                       << ast.NewGraph(ast.DIGRAPH, ast.FALSE, $1, $3) >>
    | Strict Digraph "{" StmtList "}"                   << ast.NewGraph(ast.DIGRAPH, ast.TRUE, nil, $3) >>
	| Strict Digraph Id "{" StmtList "}"                << ast.NewGraph(ast.DIGRAPH, ast.TRUE, $2, $4) >>
	;
			
	
//stmt_list	:	[ stmt [ ';' ] [ stmt_list ] ]	
StmtList 
	:  Stmt1                                             << ast.NewStmtList($0) >>
    |  StmtList Stmt1                                    << ast.AppendStmtList($0, $1) >>
	;

Stmt1
    :  Stmt                                             << $0, nil >>
    |  Stmt ";"                                         << $0, nil >>
    ;
	
//stmt	:	node_stmt | edge_stmt | attr_stmt | (ID '=' ID) | subgraph
Stmt	
    : Id "=" Id                                         << ast.NewAttr($0, $2) >>
	| NodeStmt                                          << $0, nil >>
	| EdgeStmt                                          << $0, nil >>
	| AttrStmt                                          << $0, nil >>
  	| SubGraphStmt                                      << $0, nil >>
	;
		
//attr_stmt	:	(graph | node | edge) attr_list
AttrStmt
	: Graph AttrList                                    << ast.NewGraphAttrs($1) >>
	| Node AttrList                                     << ast.NewNodeAttrs($1) >>
	| Edge AttrList                                     << ast.NewEdgeAttrs($1) >>
	;
		
//attr_list	:	'[' [ a_list ] ']' [ attr_list ]
AttrList
	: "[" "]"                                           << ast.NewAttrList(nil) >>
	| "[" AList "]"                                     << ast.NewAttrList($1) >>
	| AttrList "[" "]"                                  << ast.AppendAttrList($0, nil) >>
	| AttrList "[" AList "]"                            << ast.AppendAttrList($0, $2) >>
	;
		
//a_list	:	ID [ '=' ID ] [ ',' ] [ a_list ]
AList
    : Attr                                              << ast.NewAList($0) >>
    | AList Attr                                        << ast.AppendAList($0, $1) >>
    | AList "," Attr                                    << ast.AppendAList($0, $2) >>
    ;

//An a_list clause of the form ID is equivalent to ID=true.
Attr
    : Id                                                << ast.NewAttr($0, nil) >>                    
    | Id "=" Id                                         << ast.NewAttr($0, $2) >>
    ;
		
//edge_stmt	:	(node_id | subgraph) edgeRHS [ attr_list ]
EdgeStmt
	: NodeId EdgeRHS                                    << ast.NewEdgeStmt($0, $1, nil) >>
	| NodeId EdgeRHS AttrList                           << ast.NewEdgeStmt($0, $1, $2) >>
    | SubGraphStmt EdgeRHS                              << ast.NewEdgeStmt($0, $1, nil) >>
    | SubGraphStmt EdgeRHS AttrList                     << ast.NewEdgeStmt($0, $1, $2) >>
	;
		
//edgeRHS	:	edgeop (node_id | subgraph) [ edgeRHS ]
EdgeRHS
	: EdgeOp NodeId                                     << ast.NewEdgeRHS($0, $1) >>
	| EdgeOp SubGraphStmt                               << ast.NewEdgeRHS($0, $1) >>
	| EdgeRHS EdgeOp NodeId                             << ast.AppendEdgeRHS($0, $1, $2) >>
	| EdgeRHS EdgeOp SubGraphStmt                       << ast.AppendEdgeRHS($0, $1, $2) >>
	;
	
//node_stmt	:	node_id [ attr_list ]	
NodeStmt
	: NodeId                                            << ast.NewNodeStmt($0, nil) >>
	| NodeId AttrList									<< ast.NewNodeStmt($0, $1) >>
	;
	
//node_id	:	ID [ port ]	
NodeId
	: Id                                                << ast.NewNodeId($0, nil) >>
	| Id Port											<< ast.NewNodeId($0, $1) >>
	;

//compass_pt	:	(n | ne | e | se | s | sw | w | nw | c | _)
//Note also that the allowed compass point values are not keywords, 
//so these strings can be used elsewhere as ordinary identifiers and, 
//conversely, the parser will actually accept any identifier.
//port	:	':' ID [ ':' compass_pt ]
//		|	':' compass_pt
Port	
	: ":" Id                                            << ast.NewPort($1, nil) >>
	| ":" Id ":" Id										<< ast.NewPort($1, $3) >>
	;
	
//subgraph	:	[ subgraph [ ID ] ] '{' stmt_list '}'	
SubGraphStmt
	: "{" StmtList "}"                                	<< ast.NewSubGraph(nil, $1) >>
	| Subgraph "{" StmtList "}"							<< ast.NewSubGraph(nil, $2) >>
	| Subgraph Id "{" StmtList "}"						<< ast.NewSubGraph($1, $3) >>
	;
	
//An edgeop is -> in directed graphs and -- in undirected graphs.	
EdgeOp	
	: "->"                                              << ast.DIRECTED, nil >>
	| "--"												<< ast.UNDIRECTED, nil >>
	;
		
//The keywords node, edge, graph, digraph, subgraph, and strict are case-independent. 
Graph	
	: "graph"                                           << $0, nil >>
	| "Graph" 											<< $0, nil >> 
	| "GRAPH" 											<< $0, nil >>
	;

Strict	
	: "strict"                                          << $0, nil >>
	| "Strict" 											<< $0, nil >> 
	| "STRICT" 											<< $0, nil >>
	;

Digraph 
	: "digraph"                                         << $0, nil >> 
	| "Digraph" 										<< $0, nil >> 
	| "DiGraph" 										<< $0, nil >> 
	| "DIGRAPH" 										<< $0, nil >>
	;

Node 	
	: "node"                                            << $0, nil >> 
	| "Node" 											<< $0, nil >> 
	| "NODE" 											<< $0, nil >>
	;

Edge	
	: "edge"                                            << $0, nil >>
	| "Edge" 											<< $0, nil >>
	| "EDGE" 											<< $0, nil >>
	;

Subgraph
	: "subgraph"                                      	<< $0, nil >>
	| "Subgraph" 										<< $0, nil >>
	| "SubGraph" 										<< $0, nil >>
	| "SUBGRAPH" 										<< $0, nil >> 
	;
		
//		An ID is one of the following:
//		Any string of alphabetic ([a-zA-Z'200-'377]) characters, underscores ('_') or digits ([0-9]), not beginning with a digit; //CHECK 200-377
//		a numeral [-]?(.[0-9]+ | [0-9]+(.[0-9]*)? );
//		any double-quoted string ("...") possibly containing escaped quotes ('")1; //TODO
//		an HTML string (<...>).
//		An ID is just a string; the lack of quote characters in the first two forms is just for simplicity. 
//		There is no semantic difference between abc_2 and "abc_2", or between 2.34 and "2.34". 
//		Obviously, to use a keyword as an ID, it must be quoted. Note that, in HTML strings, angle brackets must occur in matched pairs, and unescaped newlines are allowed. 
//		In addition, the content must be legal XML, so that the special XML escape sequences for ", &, <, and > may be necessary in order to embed these characters in attribute values or raw text.
//		Both quoted strings and HTML strings are scanned as a unit, so any embedded comments will be treated as part of the strings.
Id		
	: id                                                << ast.NewId($0) >>
	| string_lit                                        << ast.NewId($0) >>
    | int_lit                                           << ast.NewId($0) >>
    | float_lit                                         << ast.NewId($0) >>
    | html_lit                                          << ast.NewId($0) >>
	;

//The language supports C++-style comments: /* */ and //. 
//In addition, a line beginning with a '#' character is considered a line output from a C preprocessor (e.g., # 34 to indicate line 34 ) and discarded.

//TODO (if dot file is not parsable, it might be because of these points)

//Semicolons aid readability but are not required except in the rare case that a named subgraph with no body immediately preceeds an anonymous subgraph, 
//since the precedence rules cause this sequence to be parsed as a subgraph with a heading and a body. Also, any amount of whitespace may be inserted between terminals.

//TODO
//As another aid for readability, dot allows single logical lines to span multiple physical lines using the standard C convention of a backslash immediately preceding a newline character. 
//In addition, double-quoted strings can be concatenated using a '+' operator. As HTML strings can contain newline characters, they do not support the concatenation operator.

//TODO
//Note there are still 3 sections on the webpage which have not been included (Subgraphs and Clusters, Lexical and Semantic Notes, and Character Encodings)