Graph Parser Combinators

Graph Parser Combinators

What are Graph Parser Combinators?

Graph parser combinators are an attempt to carry over the popular parser combinator approach to the domain of graphs. In analogy to string grammars there are also several different graph grammar formalisms. We have noted that most advantages of string parser combinators also apply to graphs, and, surprisingly, even further advantages have appeared. A parser constructed using graph parser combinators resembles the particular graph grammar very closely. It can be adapted to varying demands in a flexible way, and can be freely used in the host program -- it is a first-class citizen after all.

What is the current state of the implementation?

We have already written a powerful Haskell library on top of polyparse. However, we have noticed that a functional-logic approach is even more suited. Therefore, we have reimplemented the framework using the multi-paradigm declarative language Curry. The resulting library is simple and straightforward. We have already applied it successfully to several practical problems. However, since this is very much work in progress there is no downloadable release yet. We gladly send you a commented snapshot on request.

What can Graph Parser Combinators be used for?

As already mentioned the use of graph parser combinators has several merits. Most exciting is the fact that parsers can be applied backwards and, thus, used as generators or for the completion of graphs. We have connected our framework to the diagram editor generator framework DiaGen, where we use it to compute completions of a given diagram.

Graph Parser Combinators as a Benchmark

In the report "Graph Parser Combinators: A Challenge for Curry-Compilers" we have suggested to use this application as a benchmark for Curry compilers. Since only three compilers have been compared and we are no expert on these particular compilers we provide the benchmark suite here for download. That way you can reconstruct or even improve our results. You may also want to add data for your favourite compiler. Just send me an email and I gladly add your data here.

Download benchmark, see file README.txt for further information

Publications about Graph Parser Combinators

We can send you these documents in PDF on request.

  • S. Mazanek, M. Minas. Constructing a Bidirectional Transformation between BPMN and BPEL with Functional-logic Graph Parser Combinators. Accepted solution for the GraBaTs 2009 synthesis case study. At the contest this solution was awarded with the third place out of the 10 submitted solutions.
  • S. Mazanek, M. Minas. Graph Parser Combinators: A Challenge for Curry-Compilers. 25. Workshop der GI-Fachgruppe Programmiersprachen und Rechenkonzepte, 2008. Technical Report of Christian-Albrechts-Universität Kiel, no. 0811, pages 55-66.
  • S. Mazanek, S. Maier, M. Minas. Auto-completion for Diagram Editors based on Graph Grammars. Appears in Proc. of the 2008 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC 2008), 2008. IEEE Computer Society Press.
  • S. Mazanek, M. Minas. Functional-logic graph parser combinators. Proc. of the 19th International Conference on Rewriting Techniques and Applications (RTA 2008), 2008. LNCS, Volume 5117/2008, pages 261-275.
  • S. Mazanek, M. Minas. Parsing of hyperedge replacement grammars with graph parser combinators. Proc. 7th International Workshop on Graph Transformation and Visual Modeling Techniques (GT-VMT 2008), 2008. Electronic Communications of the EASST, Volume 10.
  • S. Mazanek, M. Minas. Graph parser combinators. Proc. of the 19th International Symposium on Implementation and Application of Functional Languages (IFL 2007), 2008. LNCS, Volume 5083/2008, pages 1-18.


Please send any questions, requests and suggestions to Steffen Mazanek.