## Exercise ‹34›:

Hierarchic Graphs
Note: this exercise is taken from the Compilers subject at Barcelona School of Informatics.

Design a grammar to describe hierarchic graphs. The set of tokens is {graph, endgraph, IDENT, (, ), ,, ;, >}. The token IDENT refers to identifiers, such as graph names, i.e., non-empty sequences of alphanumeric characters and underscore, not starting by a digit.

Example input:
```  graph F(in, out)
in > a > out;
in > b > a;
b > out;
endgraph

graph G(a, b, c, d)
a > x > y > x;
b > x; y > c; y > d;
endgraph

graph top(x1, x2, y)
x1 > n1; x1 > n2;
G(n1, n2, n8, n5);
G(n3, n4, n6, n7);
x2 > n3; x2 > n4;
F(n7, n11);
G(n5, n6, n9, n10);
G(n8, n9, n12, n13);
G(n10, n11, n14, n15);
n13 > y; n14 > y;
n15 > n12;
endgraph
```
Remarks:
• The grammar must have a special node named global as root.
• Each input contains at least one graph.
• The set of parameters of a graph can be empty, as in “graph H() ...”.
• The body of a graph can be empty, as in “graph H(a,b) endgraph”.
• The AST corresponding to a graph must have the token graph as root, the graph name as first child, a special node named params as second child, with one child per parameters, and a special node named body as third child, with one child per edge definition.
• An edge definition of the form x > y > z must be represented by a subtree with the token > as root, and one child per node. An edge definition consisting of an embedded subgraph must be represented by a subtree with the token ( as root, the graph name as first child and a special node named params as second child, with one child per parameter.
Authors: Nil Mamano / Documentation:
 // Write your syntactic and lexical descriptions here... To be able to submit you need to either log in, register, or become a guest.