PTD Parsers in AGG

As a proof-of-concept of the construction in [ICGT'21], we define the running example of [ICGT'21], linked trees, in the algebraic graph transformation system AGG developed at TU Berlin [1]. The system has been developed in Java; it can be downloaded at www.user.tu-berlin.de/o.runge/agg/.

CHR Grammar and Borrowing HR Grammar

Hypergraphs are represented as bipartite graphs with two kinds of nodes, one representing nodes, the others representing hyperedges; tentacles are represented by edges connecting hyperedges to nodes, or vice versa. The direction of tentacles is chosen to convey “node flow” in a derivation and in a parse: the nodes preceding a hyperedge are known before the hyperedge is generated (parsed, resp.), and its successors are known only afterwards.

Terminal hyperedge labels are r (root), e (edge) and l (link). Otherwise, productions are represented as in the paper.

We use a type graph to specify which hypergraphs are consistent. We exploit subtyping and multiplicities that are not used in the paper This does not only help to avoid errors when defining productions and parser operations, but also reduces the number of critical overlaps between rules in dependency analysis.

In the borrowing HR grammar, separate-edges (drawn as double lines with a negation in the paper, “$\not=$”) are represented as arrows in yellow, and borrowed nodes, drawn as “ $\circledcirc $” in the paper, are distinguished by attaching a loop arrow in red.

The grammars are found in files CHRG.ggx and bCHRG.ggx.

PTD-Parser

The predictive top-down parser is defined in PTD-Parser.ggx. Non-deterministic behavior can easily be achieved by disabling the application conditions of its expand-rules start, leaf, branch, and link.

The definition of the parser differs from that in Def. 13 and Def. 15 of [ICGT'21] in that configurations preserve the matched part of the borrowing derivation, the matched part of the input, and represent the contraction morphism by dotted edges between their nodes and hyperedges. The rules match-r, match-e, and match-l have been adapted to achieve this. Three states are distinguished for hyperedges and their tentacles:

  • Hyperedges on the stack are drawn in black.
  • Hyperedges in the input are drawn in blue.
  • Hyperedges of the matched parts of the derivation and input are drawn in green.

Some details of the representation have also been changed:

  • The state of nodes (unmatched and matched, resp.) is neither indicated by unary hyperedges, nor by loops, but by application conditions.
  • Borrowed nodes and their matching input nodes are connected by arrows drawn in red.

The grammar file also contains host graphs that have been obtained in a parse corresponding to that shown in Fig. 13 of [ICGT'21].

References

1
Claudia Ermel, Manuel Rudolf, and Gabriele Taentzer.
The AGG approach: Language and environment.
In Gregor Engels, Hartmut Ehrig, Hans-Jörg Kreowski, and Grzegorz Rozenberg, editors, Handbook of Graph Grammars and Computing by Graph Transformation, Vol. II: Applications, Languages, and Tools, pages 551–603. World Scientific, Singapore, 1999.