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

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

相比之下,SG、SGG 与 CGG 只能配置产生式图内部的空间语义模型而缺乏对产生式与上下文之间的空间
语义关系的描述.在面对上述需求时,最直接的方法是将 vCGG 产生式中的虚结点(即上下文结点)引入产生式
中作为普通实结点.例如,图 14 是一个满足上述关于“if”结点布局要求的 CGG 产生式.然而,该方法存在着较大
的弊端:首先,将虚结点引入产生式作为普通实结点需要穷举该结点允许接受的标号(如“statement”“endif”),而
每种标号都对应着一个产生式,造成了产生式规模与数量的增长,尤其在需要引入多个虚结点作为实结点时,产
生式的数量随之呈指数增长;其次,实结点的增加在一定程度上影响了产生式图作为一个图形单元的逻辑独立
性,例如,图 14 中产生式中出现了不属于“if”选择结构的实结点“statement”;最后,在产生式中引入普通实结点还
需考虑它们的上下文信息,进一步增加了产生式的规模与数量,也使产生式的抽象程度有所下降.

(0, 0) (2, 0) (0, 0) (2, 0) Y- (4, 0) N- (6, 0) (8, 0)
1 statment stat := 1 statement endif stat
branch branch
Y N
(2, 0)
if

Fig.14 CGG production under the layout requirements
图 14 满足布局需求的一个 CGG 产生式
SG、SGG 与 CGG 配置产生式与上下文之间空间语义关系的另一种方法是:根据图柄结点在主图中与余图
的坐标关系,间接地设计嵌入图结点的坐标信息.图 15 是根据这种间接配置方法设计的 CGG 产生式,其设计过
程为:首先计算出产生式左图结点“stat”的图柄与主图中上下文的坐标差,再根据产生式右图结点“if”与左图结
点之间的坐标关系分配满足布局要求的“if”结点坐标.然而,由于缺少产生式与上下文的空间关系的显式描述,
这种间接配置方法的直观性有所不足,增加了设计人员绘制产生式的难度,尤其在那些坐标计算较为复杂的应
用场景下.例如,部分图模型布局算法要求相邻结点之间需保持一个合适的距离,例如力引导布局算法 [22] 、
Fruchterman-Reingold 算法 [23] 以及 Kamada-Kawai 算法 [24] .图 16 描述了一个要求相邻结点距离不小于 2 的布局
需求,其中,图转换后与上下文结点“a”,“b”相邻的结点由结点“d”转变为新增结点“c”.
(0, 0) (0, 0) Y- (2, 0) N- (4, 0) (6, 0)
1 stat := endif stat
branch branch
Y N
(-2, 2)
1 if

Fig.15 Indirect specification of the spatial relationship between production and context
图 15 上下文与产生式之间空间关系的间接配置

Fig.16 Deficiency of the indirect specification of spatial semantics in intuitiveness
图 16 间接空间语义配置在直观性上的缺陷