Reserved Graph Grammar:

A Specification Tool for Diagrammatic VPLs

Da?Qian Zhang Kang Zhang

Department of Computing, Macquarie University, NSW 2109, Australia

{daqian, kang}@mpce.mq.edu.au

Abstract

When implementing textual languages, formal grammars are commonly used to facilitate understanding languages and creating parsers. In the implementation of a diagrammatic visual programming language (VPL), this rarely happens, though graph grammars with their well? established theoretical background may be used as a natural and powerful syntax?definition formalism. Yet all graph grammar parsing algorithms presented up to now are either unable to recognize interesting visual languages or tend to be hopelessly inefficient (with exponential time complexity) when applied to graphs with a large number of nodes and edges.

This paper presents a context?sensitive graph grammar called reserved graph grammar, which can explicitly, efficiently and completely describe the syntax of a wide range of diagrams using labeled graphs. Moreover, its parsing algorithm is of polynomial time complexity in most cases.

1. Introduction

An important class of visual programming languages (VPLs) is the diagrammatic one, which is based on object? relationship abstractions (e.g. using nodes and edges). Frequently used diagrammatic VPLs include Entity?Relationship database design languages, data?flow programming languages (e.g. Petri nets), control flow programming languages, state transition specifications, and so on.

In the implementation of textual languages, formal grammars are commonly used to facilitate the language understanding and the parser creation. In the diagrammatic VPL implementation, this is not usually the case. Graph grammars with their well?established theoretical background may be used as a natural and powerful syntax?defi-

nition formalism [1] and the parsing algorithm based on a graph grammar may be used to check the syntactical correctness and to interpret the language semantics.

One obstacle for the application of graph grammars is that even for the most restricted classes of graph grammars the membership problem is NP?complete [2]. As a consequence, all graph grammar parsing algorithms presented so far are either unable to recognize interesting languages of graphs or tend to be hopelessly inefficient when applied to graphs with a large number of nodes and edges.

Another problem is that nearly all known graph grammar parsing algorithms [2,3,4,5,6,7] deal only with context?free productions. This makes them difficult to specify a large portion of VPLs. A context?sensitive graph grammar, on the other hand, allows left? and right?side graphs of a production to have arbitrary number of nodes and edges, like a layered graph grammar proposed by J. Rekers and A. Schurr [8], which can be used to specify the syntax of a wide range of diagrammatic VPLs.

Although being expressive, the layered graph grammar is rather inefficient in its implementation. Its parsing algorithm is complicated and the complexity generally reaches exponential time. It is reported that parsing grammars with the Rekers?Schurr algorithm is extremely hard [9].

This paper presents a context?sensitive graph grammar called reserved graph grammar (RGG) which uses a powerful formalism to support the linking of newly created graphs into a parsed graph (traditionally called embedding). RGG is complete and explicit in describing the syntax of a wide range of diagrams using labelled graphs. Compared to the layered graph grammar where the context?graph [8] must explicitly appear in the production, the embedding mechanism in the reserved graph grammar allows the grammar representation to avoid most of the context?specifications while being more expressive. This greatly reduces the expression complexity, and in turn increases the efficiency of the parsing algorithm.