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
  

VEX

VEX (visual expressions) is a VL for the representation of lambda expressions.


The picture provides two exemplary VEX expressions. The upper one represents the lambda term λy.(x y), i.e. a function that applies the free variable x to its argument. The other one represents the term λx.λy.(x y). Here variable x also is bound by an abstraction.

VEX is a very simple visual language in the sense that there are only three different visual components: the circle, the line and the arrow. The whole meaning of an arrangement of these components is determined by their spatial relations.


A lambda term is inductively defined. It is either a variable, an application of one lambda term to another one or an abstraction that consists of the variable to be bound and its body, i.e. the scope of the particular variable. For these three cases visual representations are defined.

In VEX a single variable is represented by a circle. It does not need to have a name as in the textual form. An abstraction is represented by a circle with a smaller circle internally tangent to it. Elements contained in the bigger circle are part of the abstractions body whereas the smaller circle represents the parameter. The application of an expression e1 to an expression e2 is represented by an arrow that points from e1 to e2. Further the outermost circles of e1 and e2 have to touch each other.

Variables can be bound via lines to parameters of abstractions. If they are free they need to be bound to a free variable circle that must not be inside another circle. The meaning for this is that it has to be possible to identify occurrences of the same free variable.

The main purpose of VEX is to simplify the teaching of lambda calculus. For this sake it is very benefitial that variable bindings are made explicit by lines and not implicitly hidden behind equal names. In particular one does not have to deal with the difficulties resulting from overlapping scopes and thus the need for alpha conversion.



Syntax analysis for VEX diagrams is quite difficult. There are ambiguities (i.e. to circles connected by a line, which one is the variable and which one the free variable circle?) and a lot of combinations of particular patterns and their spatial arrangement. However, there is a quite flexible DiaGen editor for VEX where the language is defined via a hyperedge replacement grammar. However, as you see in the picture "two different kinds of circles" need to be defined restricting the freedom of the user somewhat.

Practical on Graph and Model transformation

I have already written several posts regarding our seminar on graph and model transformation. The next three months we conduct a practical on graph and model transformation on top of this seminar.

The first task is the implementation of an editor for UML class diagrams (restricted to classes, attributes, generalizations and a limited notion of associations). However, the editor should, of course, not be implemented from scratch. Rather it should be generated using a meta-CASE-tool. We have divided the students in three small groups. Each group has to use a different meta-CASE-tool. The tools to use are:

• MetaEdit+ by MetaCase, I already have written about MetaEdit+


• GMF, an eclipse project


• DSL Tools by Microsoft, a framework based on MS Visual Studio

Whereas MetaEdit+ and DSL Tools are commercial products, GMF is open source. All three tools have in common that they are of sufficient quality and well-documented, making them suited for our practical.

ER diagrams

In the last days I had to deal a lot with entity relationship (ER) diagrams, because I have to conduct exercises for a database course. ER diagrams have been developed in the seventies by Chen and are a widely used visual language for the conceptual design of database systems. Further in my last post I described the tool AToM3 whose main formalism is ER.


This figure is from the wikipedia article and shows an exemplary ER diagram.

To my surprise there seem to be no freeware or open source tools that allow the drawing of ER diagrams in the commonly used notations, i.e. the original one by Chen plus some conservative extensions like Min-Max etc. I have tried several of the free tools referenced in the wikipedia article on ER like BrModelo (only in portuguese language), Ferret (platform-specific and not very feature-rich), MySQL workbench (proprietary notation and MySQL-focused) and even some of the commercial ones like SmartDraw and MS Visio. But none of them is as feature-rich as one might expect in the context of such an old visual language.

Using DiaMeta, for instance, it would be possible to specify a compliant and feature-rich ER editor in a very short time. One even could apply a EMF-based model transformation with, e.g., ATL to derive the corresponding database schema.

Did I miss a tool that is freely available, provides an interface in English language and conforms to the widely-adopted concrete syntax? Any further references are greatly appreciated.

AToM3

I am back from vacation and continue reporting about the seminar talks. On 29.11.07 we discussed the tool AToM3, a research project of Hans Vangheluwe and Juan de Lara.

AToM3 is an acronym for "A Tool for Multi-formalism and Meta-Modelling". From my point of view its main features are:

• meta CASE-tool: specify a visual language (formalism) and generate an environment


• homogeneous view on metamodelling: define models in a particular formalism and use them directly as a formalism again, for instance, a petri net formalism can be defined using the ER (entity relationship) formalism and in the following real petri nets can be drawn; most of AToM3 can be bootstrapped (even user interaction)


• model transformations: internally models are represented as graphs, graph grammars can be defined and used for model transformation

AToM3 is a very interesting research tool. There are a lot of publications discussing particular aspects of the tool and its theoretical foundations. However, it seems not to be ready for production settings yet. Parts of the documentation are outdated and even the Hello-World example caused several exceptions (but I got it up and running) and useless warnings like "Bad things will happen". However, as a researcher in the area of graph transformation you have to deal with the tool or at least with the publications by all means.

Further reading:

• AToM3 website


• AToM3 publications


• AToM3, some more publications