Graph Parser Combinators

This post is about a topic I am particularly interested in, namely Graph Parser Combinators. Among functional programmers parser combinators are very popular. They are fun to play with and a lot of research has been done to make them more practically relevant (mainly by improving efficiency). There is an abundance of different libraries, e.g., the HUT Parser Combinators, Parsec or polyparse.

Since I have to deal a lot with graph-grammar based visual languages (remember my post about the diagram editor generator DiaGen), the question arose whether parser combinators may also be useful for graph parsing. So I have implemented a prototypical Haskell library and several exemplary parsers. And although there are some fundamental differences between graph and string parsing it worked astoundingly well.

At IFL 2007 I have introduced this approach. Several people have asked me whether graph parser combinators actually are powerful enough to describe highly-meshed graph languages like, e.g., Flowgraphs, a graph language representing structured Flowcharts. Such languages can naturally be described using hyperedge replacement grammars. The answer is yes, and I am going to present a solution to this problem at GT-VMT 2008.

Further reading:

• Graph Parser Combinators, Mazanek, S., Minas, M., 2008, Proceedings of IFL 2007, to appear


• Parsing of Hyperedge Replacement Grammars with Graph Parser Combinators, Mazanek, S., Minas, M., 2008, Proceedings of GT-VMT 2008, to appear