关键词: 可视化语言, 图文法, 图变换, 图重写, EGG, 设计模式

Abstract: Researches on graph transformation and visual language motivate and promote the research and development of graph grammars. As the extension of one dimensional string grammars, graph grammars can be used to formally describe objects in a two dimensional apace, such as images, graphs, and tables etc., and supply theoretical and technical supports for their definition, generation, transformation, and parsing. The design pattern, with an appearance of a two dimensional graph, is the basis of reusable objectoriented software. In order to suit to the various requirements of users, a design pattern usually needs to evolve under the condition of unchanging some basic structure criterions. It is discussed in this paper the application of graph grammar EGG and its formalism to the evolution of design patterns. The discussions are mainly focused on two aspects of graph transformation and graph parsing. The former is to make use of the EGG productions as graphrewriting rules to guide every graph transformation for guaranteeing the validity of corresponding the design pattern’s evolution in each step; and the latter is to make use of the grammar mechanism of the EGG to parse the given graphs for checking the validity of any freely evolved design patterns.

Key words: visual language;graph grammar;graph transformation;graph rewriting;EGG;design pattern