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

刘禹锋 等:vCGG:一种基于虚结点的空间图文法形式框架 3677

¾ vdCGG:首先,在产生式图 G L|R 中选择任意一个虚结点 n′,将图柄中的对应结点 n 与 n′的坐标差值
n.c−n′.c 作为偏移量平移另一个产生式图 G R|L ;
3) 从主图中删除图柄中所有的边以及与 G L|R 中实结点匹配的结点;
4) 按照产生式图 G L|R 的虚节点与图柄结点的映射关系,粘合产生式图 G R|L 的虚结点与图柄中对应结点,
并在主图中去除该虚标号.
vCGG 图转换的操作继承了 CGG 中的坐标映射机制,即产生式局部坐标与主图全局坐标的映射关系,区别
在于:vdCGG 基于虚结点而计算获得坐标偏移量,而 dCGG 的偏移量是基于最大“Y”值的结点而计算得出.相比
之下,vdCGG 偏移量的可解释性更好,产生式设计人员的学习曲线较为平缓.图 8 描述了使用图 7 中的产生式 p1
和 p2 对图 7(a)中的主图分别进行 R-application 生成的新主图,其中,图 8(a)是使用图 7(a)中产生式 p1 在 vcCGG
框架下生成的新主图,图 8(b)是使用产生式 p2 按照 vdCGG 的 R-application 步骤生成的主图.

(a) 基于产生式 p1 的新主图 (b) 基于产生式 p2 的主图
Fig.8 New host graphs generated by the productions in Fig.7
图 8 使用图 7 中产生式进行 R-application 生成的新主图
2.3 vCGG及其语言定义

定义 2.5. vCGG 是一个四元组(λ,L,P,S),其中,
• λ是一个初始图;
• L=L v ∪L r ,L v ∩L r =∅,其中,L v 是虚结点的标号集,L r 是实结点的标号集;
• L r =L T ∪L NT ,L T ∩L NT =∅,其中,L T 是终结点的标号集,L NT 是非终结点的标号集;
• P 是一个产生式集;
• S 是一个由若干正实数组成的标尺集,并且满足关系:S⊆R+.
为了避免产生式的冗余,vCGG 的形式化定义中继承了 CGG 的标尺集概念.类似于地图标尺,标尺集中的每
一个正实数代表着主图对产生式的坐标比例.标尺的引入,可以有效地减少产生式的数量,尤其是那些结构完全
相同而互相之间坐标成比例关系的产生式.每个产生式集 P 中的产生式都可以通过坐标与标尺的相乘得到多
个实际使用的产生式,因此,标尺集所包含正实数的数量对一个文法的实际表达能力有着重要的影响.
定义 2.6. 对于 vCGG 的任意一个文法 vcgg,其语言Γ(vcgg)是一个由空间语义图组成的集合:
Γ(vcgg)={G(λ→*G)∧f NL (G.N)∈L T }.
图文法的语言是由初始图经过推导操作生成的只含有终结点的图的集合.对一个只含有终结点的图进行
归约操作的过程,可以判断该图是否属于相应文法所定义的语言.vCGG 的推导工作流生成的是一个包含空间
语义配置的图,而归约工作流可以在判断给定图的结构语法的合法性的同时,分析该图的空间语义模型.

3 与已有文法的对比

本节对新构建的 vCGG 框架与几种具有代表性的框架 SGG、SG、CGG 进行对比,其中,SGG 对空间语义