dot.bnf

//Copyright 2013 GoGraphviz Authors
//
//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 https://graphviz.gitlab.io/_pages/doc/info/lang.html
//The rules have been copied and are shown in the comments, with their derived bnf rules below.

// ### [ Tokens ] ##############################################################

// The keywords node, edge, graph, digraph, subgraph, and strict are case-
// independent.

node
	: 'n' 'o' 'd' 'e'
	| 'N' 'o' 'd' 'e'
	| 'N' 'O' 'D' 'E'
;

edge
	: 'e' 'd' 'g' 'e'
	| 'E' 'd' 'g' 'e'
	| 'E' 'D' 'G' 'E'
;

// TODO: Rename graphx to graph once gocc#20 is fixed [1].
//
// [1]: https://github.com/goccmack/gocc/issues/20

graphx
	: 'g' 'r' 'a' 'p' 'h'
	| 'G' 'r' 'a' 'p' 'h'
	| 'G' 'R' 'A' 'P' 'H'
;

digraph
	: 'd' 'i' 'g' 'r' 'a' 'p' 'h'
	| 'D' 'i' 'g' 'r' 'a' 'p' 'h'
	| 'd' 'i' 'G' 'r' 'a' 'p' 'h'
	| 'D' 'i' 'G' 'r' 'a' 'p' 'h'
	| 'D' 'I' 'G' 'R' 'A' 'P' 'H'
;

subgraph
	: 's' 'u' 'b' 'g' 'r' 'a' 'p' 'h'
	| 'S' 'u' 'b' 'g' 'r' 'a' 'p' 'h'
	| 's' 'u' 'b' 'G' 'r' 'a' 'p' 'h'
	| 'S' 'u' 'b' 'G' 'r' 'a' 'p' 'h'
	| 'S' 'U' 'B' 'G' 'R' 'A' 'P' 'H'
;

strict
	: 's' 't' 'r' 'i' 'c' 't'
	| 'S' 't' 'r' 'i' 'c' 't'
	| 'S' 'T' 'R' 'I' 'C' 'T'
;

// An arbitrary ASCII character except null (0x00), double quote (0x22) and
// backslash (0x5C).
_ascii_char
	// skip null (0x00)
	: '\x01' - '\x21'
	// skip double quote (0x22)
	| '\x23' - '\x5B'
	// skip backslash (0x5C)
	| '\x5D' - '\x7F'
;

_ascii_letter
	: 'a' - 'z'
	| 'A' - 'Z'
;

_ascii_digit : '0' - '9' ;

_unicode_char
	: _ascii_char
	| _unicode_byte
;

_unicode_byte
	: '\u0080' - '\uFFFC'
	// skip invalid code point (\uFFFD)
	| '\uFFFE' - '\U0010FFFF'
;

_letter        : _ascii_letter | _unicode_byte | '_' ;
_decimal_digit : _ascii_digit ;
_decimals      : _decimal_digit { _decimal_digit } ;

// An ID is one of the following:
//
//    1) Any string of alphabetic ([a-zA-Z\200-\377]) characters, underscores
//       ('_') or digits ([0-9]), not beginning with a digit;
//
//    2) a numeral [-]?(.[0-9]+ | [0-9]+(.[0-9]*)? );
//
//    3) any double-quoted string ("...") possibly containing escaped quotes
//       (\");
//
//    4) an HTML string (<...>).

id
	: _letter { _letter | _decimal_digit }
	| _int_lit
	| _string_lit
	| _html_lit
;

_int_lit
	: [ '-' ] '.' _decimals
	| [ '-' ] _decimals [ '.' { _decimal_digit } ]
;

// In quoted strings in DOT, the only escaped character is double-quote (").
// That is, in quoted strings, the dyad \" is converted to "; all other
// characters are left unchanged. In particular, \\ remains \\.

_escaped_char : '\\' ( _unicode_char | '"' | '\\' ) ;
_char         : _unicode_char | _escaped_char ;
_string_lit   : '"' { _char } '"' ;

// An arbitrary HTML character except null (0x00), left angle bracket (0x3C) and
// right angle bracket (0x3E).
_html_char
	// skip null (0x00)
	: '\x01' - '\x3B'
	// skip left angle bracket (0x3C)
	| '\x3D'
	// skip right angle bracket (0x3E)
	| '\x3F' - '\xFF'
;

_html_chars : { _html_char } ;
_html_tag   : '<' _html_chars '>' ;
_html_lit   : '<' { _html_chars | _html_tag } '>' ;

// 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.

_line_comment
	: '/' '/' { . } '\n'
	| '#' { . } '\n'
;

_block_comment : '/' '*' { . | '*' } '*' '/' ;
!comment       : _line_comment | _block_comment ;

!whitespace : ' ' | '\t' | '\r' | '\n' ;

// ### [ Syntax ] ##############################################################

<< import "github.com/awalterschulze/gographviz/ast" >>

//graph	:	[ strict ] (graph | digraph) [ ID ] '{' stmt_list '}'
DotGraph
	: graphx "{" "}"                              << ast.NewGraph(ast.GRAPH, ast.FALSE, nil, nil) >>
	| strict graphx "{" "}"                       << ast.NewGraph(ast.GRAPH, ast.TRUE, nil, nil) >>
	| graphx Id "{" "}"                           << ast.NewGraph(ast.GRAPH, ast.FALSE, $1, nil) >>
	| strict graphx Id "{" "}"                    << ast.NewGraph(ast.GRAPH, ast.TRUE, $2, nil) >>
	| graphx "{" StmtList "}"                     << ast.NewGraph(ast.GRAPH, ast.FALSE, nil, $2) >>
	| graphx Id "{" StmtList "}"                  << ast.NewGraph(ast.GRAPH, ast.FALSE, $1, $3) >>
	| strict graphx "{" StmtList "}"              << ast.NewGraph(ast.GRAPH, ast.TRUE, nil, $3) >>
	| strict graphx 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
	: graphx 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), nil >>
	| ":" Id ":" Id                               << ast.NewPort($1, $3), nil >>
	;

//TODO: 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.

//subgraph	:	[ subgraph [ ID ] ] '{' stmt_list '}'
SubGraphStmt
	: "{" StmtList "}"                            << ast.NewSubGraph(nil, $1) >>
	| subgraph "{" StmtList "}"                   << ast.NewSubGraph(nil, $2) >>
	| subgraph Id "{" StmtList "}"                << ast.NewSubGraph($1, $3) >>
	| subgraph "{" "}"                   	      << ast.NewSubGraph(nil, nil) >>
	| subgraph Id "{" "}"                         << ast.NewSubGraph($1, nil) >>
	;

//An edgeop is -> in directed graphs and -- in undirected graphs.
EdgeOp
	: "->"                                        << ast.DIRECTED, nil >>
	| "--"                                        << ast.UNDIRECTED, nil >>
	;

Id
	: id                                          << ast.NewID($0) >>
	;