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

3670 Journal of Software 软件学报 Vol.32, No.12, December 2021

图文法是一种使用产生式(图重写规则)进行图语言定义与分析的二维化形式化工具.使用图文法对各种可视化
语言语法结构的描述、操纵和分析,具有直观明了和简便的优点.至今,图文法已被广泛地应用于各种可视化语
[1]
[2]
言的配置与分析中,例如图语言定义与转换 、图模型的动态分析 .不仅如此,图文法还被广泛地应用于软件系
[5]
统建模 [3,4] 、信息可视化 、模式识别 [6−8] 等领域.
作为二维或三维空间上最重要的特征之一,空间语义信息在可视化语言的空间拓扑结构描述以及空间知
识呈现上是不可或缺的关键因素之一.然而,大多数图文法在面向空间语义处理需求时存在诸多困难之处.Stiny
和 Gips 从描述空间元素形状的角度出发,提出了形状文法 SG(shape grammar) [9,10] .SG 将形状定义为一系列空间
元素的有限排列,例如线段、点、矩形.SG 的文法直观易懂,可以被广泛地应用于建筑图像分析 [11] 、绘图设计 [12]
等领域.根据事先定义的规则,SG 可以通过迭代地使用形状替换操作来生成各种各样的设计.然而,由于只支持
单方向的工作流,SG 更侧重于完成不同类型图形的生成绘制工作,而在图形分析处理能力上有所欠缺.Kong 等
人 [13,14] 在上下文相关图文法 RGG(reserved graph grammar) [15] 形式框架中加入了空间信息处理机制,提出了一
种空间图文法——SGG(spatial graph grammar).SGG 对空间语义信息采用定性研究方法进行描述,包括 6 种拓
扑关系、4 种方向关系、顺序距离关系以及 7 种对齐关系.基于定性分析方法,SGG 可以较为直观灵活地分析各
种可视化语言的语法与语义结构,在网页描述及模式验证 [16,17] 领域取得了较好的应用效果.然而,SGG 也有存在
一些不足之处:首先,由于对空间语义信息缺少定量描述能力,SGG 在对空间关系进行配置时缺乏相应的精准
性;其次,SGG 中使用额外的语义函数描述空间语义关系,并通过执行操作代码实现语义变换,较大程度地增加
了 SGG 在实际应用中的复杂性.针对 SG 与 SGG 文法框架的局限性,本文作者在前期研究中提出了一种坐标图
文法框架——CGG(coordinate graph grammar) [18] ,将空间语义信息的定量和定性描述机制整合在一个理论框架
内,并利用图形元素之间的坐标关系设计了相对低时间开销的图柄查找算法,为空间语义信息提供了相对灵活
的配置方案.表 1 给出了 CGG 与 SG、SGG 这两种具有代表性的空间文法框架的对比,CGG 在保持 SG 和 SGG
优点的同时弥补了两者的不足,为空间语义配置提供了一个更全面的形式化框架.目前,CGG 已被应用在 UML
类图定义与布局 [19] 、流程图生成与检测 [18] 等实际案例中.然而,CGG 是在 EGG(edge based graph grammar) [20] 的
理论框架的基础上加入空间语义机制而构建的图文法形式框架,因此,EGG 的部分缺陷延伸到了 CGG 中:首先,
CGG 中悬边图的概念不符合图论中点边图的定义,使得图柄结构的规范性有所欠缺;其次,在 CGG 的归约操作
中,悬边的匹配需要考虑图柄排列问题,导致大量冗余图柄的出现,在一定程度上增加了归约执行步数,也导致
大量无效归约的产生;最后,CGG 产生式中使用悬边描述上下文信息,通过减少上下文信息的匹配提高文法的
抽象程度,却在某种程度上影响了文法的直观性以及表达能力.针对上述问题,本文在前期研究的基础上,通过
定义虚结点的概念,构建一个新的空间图文法框架 vCGG(virtual node based coordinate graph grammar).该框架
在文法中保留上下文结点的同时,维持 CGG 产生式的抽象能力,从而为图的空间语义提供更加直观而全面的形
式化描述与分析手段.
Table 1 Comparison among SG, SGG and CGG [18]
表 1 CGG 与 SG、SGG 的对比 [18]
图文法框架 推导和归约 配置粒度 语义形式 二维和三维建模
SG 推导 连续值 定量描述 二维和三维
SGG 推导和归约 离散值 定性描述 二维
CGG 推导和归约 连续值和离散值 定量描述和定性描述 二维和三维
本文第 1 节介绍 CGG 的理论框架.第 2 节在 CGG 基础上构建一个新的空间图文法框架 vCGG,包括框架的
基本概念与文法操作.第 3 节对 vCGG 与几种具有代表性的空间图文法进行对比分析.第 4 节给出总结及展望.

1 CGG 形式框架

1.1 基本概念
CGG 是在上下文相关图文法 EGG 中引入空间语义机制扩展而来的空间图文法形式框架,通过在传统连续