Page 5 - 《软件学报》2021年第12期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(12):3669−3683 [doi: 10.13328/j.cnki.jos.006164] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
vCGG:一种基于虚结点的空间图文法形式框架

刘禹锋, 杨 帆

(南京财经大学 信息工程学院,江苏 南京 210046)
通讯作者: 刘禹锋, E-mail: yfengliu28@126.com

摘 要: 作为一种二维的形式化方法,图文法为可视化语言提供了直观而规范的描述手段.然而,大多数图文法形
式框架在空间语义处理能力方面有所不足,影响了图文法的表达能力及其实际应用范围.针对现存的问题,构建了一
种新型空间图文法形式框架 vCGG(virtual-node based coordinate graph grammar).区别于其他空间图文法,vCGG 在
产生式中通过定义虚结点的概念描述产生式与主图之间的语法结构与空间语义关系,在保留抽象能力的同时,提高
了其空间语义配置性能.通过与几种典型空间图文法框架比较,vCGG 形式框架在直观性、规范性、表达能力以及
分析效率方面均有着较好的表现.
关键词: 可视化语言;图文法;产生式;空间语义;虚结点
中图法分类号: TP301

中文引用格式: 刘禹锋,杨帆.vCGG:一种基于虚结点的空间图文法形式框架.软件学报,2021,32(12):3669−3683. http://www.
jos.org.cn/1000-9825/6164.htm
英文引用格式: Liu YF, Yang F. vCGG: Virtual-node based spatial graph grammar formalism. Ruan Jian Xue Bao/Journal of
Software, 2021,32(12):3669−3683 (in Chinese). http://www.jos.org.cn/1000-9825/6164.htm
vCGG: Virtual-node Based Spatial Graph Grammar Formalism

LIU Yu-Feng, YANG Fan
(College of Information Engineering, Nanjing University of Finance and Economics, Nanjing 210046, China)

Abstract: As a two-dimensional formal method, Graph grammar provides an intuitive and formal way to specify visual programming
languages. However, most existing graph grammar formalisms have some deficiencies in the ability of dealing with spatial semantics,
which influences the expressive power and practical application scope of graph grammar. For solving the problems, this study defines
visual node to build a new spatial graph grammar formalism vCGG (virtual-node based coordinate graph grammar). Different from other
spatial graph grammars, vCGG takes the virtual nodes to specify the relationships of syntax structure and spatial semantic between host
graphs and productions, which reserves the power of the abstraction and improves the specification of spatial semantics. Compared with
other spatial graph grammars, the formalism of vCGG has good performance in the intuitiveness, normalization, expressive power, and
analysis efficiency.
Key words: visual programming languages; graph grammar; production; spatial semantic; virtual node

作为一种丰富的信息描述手段,可视化语言(可视化图)是软件系统概念设计阶段中重要的人机交互工具,
例如数据库系统概念设计阶段的 E-R(entity-relationship)图、面向对象系统中的 UML(unified modeling
language)图以及描述离散并行系统的 Petri 网.可视化语言研究的重点之一是如何使用有效而又规范的方式去
描述各种不同类型的可视化语言.一部分研究者尝试使用一维字符文法描述可视化语言,然而,由于图的二维性
以及非线性特点,字符文法在描述可视化语言时有着表达能力不足以及直观性较差等问题.基于形式语言理论,

∗ 基金项目: 国家自然科学基金(62002155)
Foundation item: National Natural Science Foundation of China (62002155)
收稿时间: 2020-06-05; 修改时间: 2020-08-02, 2020-09-17; 采用时间: 2020-10-20