Graphviz DOT

The language dot, neato and every "render me a graph" tool read - nodes, edges and the attributes hung on both:

 1digraph G {
 2	subgraph cluster_0 {
 3		style=filled;
 4		color=lightgrey;
 5		node [style=filled,color=white];
 6		a0 -> a1 -> a2 -> a3;
 7		label = "process #1";
 8	}
 9
10	start -> a0;
11	a1 -> b3;
12	start [shape=Mdiamond];
13}

The whole grammar turns on the order of the alternatives in Statement. An edge, an assignment and a node all begin with the same name, and only what comes after that name tells them apart. Alternatives are tried in order and the first one that fits wins, so EdgeStatement is written before Assignment and both before NodeStatement - the other way round, a0 would be read as a node and the -> a1 behind it would have nowhere to go.

Keywords have the same problem in the lexer, where the same rule applies: T_GRAPH and friends are declared before T_ID, or graph would be read as an identifier and never as a keyword.

Grammar

  1/**
  2 * -----------------------------------------------------------------------------
  3 *  Graphviz DOT
  4 * -----------------------------------------------------------------------------
  5 *
  6 * The language a graph is described in for Graphviz: the nodes, the edges
  7 * between them and the attributes of both.
  8 *
  9 * @see https://graphviz.org/doc/info/lang.html
 10 */
 11
 12%pragma root Graph
 13
 14%skip  T_WHITESPACE        \s++
 15%skip  T_COMMENT           //[^\r\n]*+|#[^\r\n]*+
 16%skip  T_DOC               /\*.*?\*/
 17
 18%token T_STRICT            (?i)strict\b
 19%token T_GRAPH             (?i)graph\b
 20%token T_DIGRAPH           (?i)digraph\b
 21%token T_SUBGRAPH          (?i)subgraph\b
 22%token T_NODE              (?i)node\b
 23%token T_EDGE              (?i)edge\b
 24
 25// A string is written across several lines by escaping the line break
 26%token T_STRING            "(?:[^"\\]|\\[\s\S])*+"
 27%token T_HTML_STRING       <(?:[^<>]|<[^<>]*+>)*+>
 28%token T_NUMBER            -?(?:\.[0-9]++|[0-9]++(?:\.[0-9]*+)?)
 29%token T_ID                [a-zA-Z\x{0080}-\x{FFFF}_][a-zA-Z\x{0080}-\x{FFFF}_0-9]*+
 30
 31%token T_DIRECTED_EDGE     ->
 32%token T_UNDIRECTED_EDGE   --
 33
 34%token T_BRACE_OPEN        \{
 35%token T_BRACE_CLOSE       \}
 36%token T_BRACKET_OPEN      \[
 37%token T_BRACKET_CLOSE     \]
 38%token T_SEMICOLON         ;
 39%token T_COMMA             ,
 40%token T_COLON             :
 41%token T_EQUAL             =
 42
 43Graph
 44  : <T_STRICT>? (<T_GRAPH> | <T_DIGRAPH>) Id()?
 45    ::T_BRACE_OPEN:: StatementList() ::T_BRACE_CLOSE::
 46  ;
 47
 48StatementList
 49  : (Statement() ::T_SEMICOLON::?)*
 50  ;
 51
 52/**
 53 * An edge is read before a node, because both begin with the same name and
 54 * only an edge goes on past it.
 55 */
 56Statement
 57  : AttributeStatement()
 58  | Subgraph()
 59  | EdgeStatement()
 60  | Assignment()
 61  | NodeStatement()
 62  ;
 63
 64// graph [...], node [...], edge [...]
 65AttributeStatement
 66  : (<T_GRAPH> | <T_NODE> | <T_EDGE>) AttributeList()
 67  ;
 68
 69// rankdir = LR
 70Assignment
 71  : Id() ::T_EQUAL:: Id()
 72  ;
 73
 74// a -> b -> c [color = red]
 75EdgeStatement
 76  : (Subgraph() | NodeId()) EdgeRight()+ AttributeList()?
 77  ;
 78
 79EdgeRight
 80  : EdgeOperator() (Subgraph() | NodeId())
 81  ;
 82
 83EdgeOperator
 84  : <T_DIRECTED_EDGE>
 85  | <T_UNDIRECTED_EDGE>
 86  ;
 87
 88// a [shape = box]
 89NodeStatement
 90  : NodeId() AttributeList()?
 91  ;
 92
 93// a, a:port, a:port:n
 94NodeId
 95  : Id() Port()?
 96  ;
 97
 98Port
 99  : ::T_COLON:: Id() (::T_COLON:: Id())?
100  ;
101
102Subgraph
103  : (::T_SUBGRAPH:: Id()?)? ::T_BRACE_OPEN:: StatementList() ::T_BRACE_CLOSE::
104  ;
105
106AttributeList
107  : (::T_BRACKET_OPEN:: AttributeSet()? ::T_BRACKET_CLOSE::)+
108  ;
109
110AttributeSet
111  : (Id() (::T_EQUAL:: Id())? (::T_SEMICOLON:: | ::T_COMMA::)?)+
112  ;
113
114Id
115  : <T_ID>
116  | <T_STRING>
117  | <T_HTML_STRING>
118  | <T_NUMBER>
119  ;

Usage

1use Phplrt\Compiler\Compiler;
2use Phplrt\Source\File;
3
4$parser = new Compiler()
5    ->load(new File(__DIR__ . '/grammar.pp3'))
6    ->getParser();
7
8$graph = $parser->parse(new File(__DIR__ . '/cluster.dot'));

Three kinds of comment are thrown away by %skip - //, # and /* ... */ - and so is the whitespace that separates statements, since DOT is happy to have its statements on one line or on twenty.

25+ more grammars. phplrt/grammars collects ready to read grammars for real languages - JSON5, TSV, semantic versions, DQL, PHQL, JMS types, PSR-5 and Doctrine annotations, Symfony expressions, Go! AOP pointcuts, Praspel contracts and more - each with sample inputs and a test that keeps it honest.