AVI'2006 Paper

Syntax Analysis for Diagram Editors: A Constraint Satisfaction Problem

Mark Minas
Most visual languages of today have a meta-model as syntax specification. Before meta-models became popular, grammars of various flavors have been used for specifying a visual language's syntax. Grammars are more complicated to build than meta-models, but grammars allow for parsing of visual sentences which is necessary for building free-hand editors. Parsing has not yet been considered for meta-model-based specifications. Such visual editors support only structured editing so far. This paper shows that the syntax analysis problem ("parsing") for meta-model-based language specifications can be transformed into a constraint satisfaction problem and solved that way.  This approach, therefore, allows for easy free-hand editing and, at the same time, easy meta-model-based language specifications. The efficiency of the approach has been demonstrated by realization in the diagram editor generator DiaGen.

This is an extended version of the paper
M. Minas. Syntax analysis for diagram editors: a constraint satisfaction problem. Appears in Proc. AVI'2006.