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

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

(( ∈
• ∀ nn . Q N ∧ (( f ′ NL ( f NN ( ))n ∈ L r )) ⇒ ( ( )d n = s d s ( f NN ( ) ))n ∧ ( ( )d n = e d e ( f NN ( ))))n ,其中,d e (n)和 d s (n)是结
点 n 在主图中的出入度;
• ∀n((n∈Q.N)⇒(n.c d =(f NN (n)).c d ))),其中,c d 是 Q 或 G L|R 中结点的离散坐标;
• ∀ n ,n (( ,n n ∈ Q . )N ∧ ( f ′ ( f ( ))n ∈ L ) ∧ ( f ′ ( f ( )n )∈ L ) ⇒ ( f ( )n − f ( )n = f ′ ( f ( ))n − f ′
1 2 1 2 NL NN 1 v NL NN 2 v NC 1 NC 2 NC NN 1 NC
( f ( ) ))n .
NN 2
其中,f NL 和 f ′ 是 Q 和 G L|R 的结点标号映射,f NC 和 f ′ 分别是 Q 和 G L|R 的结点坐标映射.
NL NC
基于不同的空间语义描述粒度,vCGG 两个子框架 vcCGG 与 vdCGG 的图柄定义有所不同.在满足同构关系
的前提下,vcCGG 要求图柄和产生式图需要满足坐标关系的完全匹配,产生式图中任意两个结点与它们在主图
中对应结点具有相等的坐标差,即产生式图通过平移可以与图柄完全重合.与 vcCGG 相比,vdCGG 空间语义匹
配条件按照虚结点和实结点分为两个层次:在第 1 层,图柄和产生式图的对应结点需要在各自空间内部具有相
等的离散坐标;在第 2 层,虚节点之间的定量坐标关系需要和对应主图结点完全一致,即所有虚结点可以同时通
过平移与其在图柄中的对应结点完全重合.匹配要求的划分使 vCGG 既能对产生式内部结点提供定性与定量
的拓扑关系描述,也能维持上下文结点的一致性.例如:图 7(a)是一个主图,若根据图 7(b)中产生式右图在主图中
查找图柄时,在 vcCGG 和 vdCGG 中的任何一个子框架下,该产生式右图都符合图柄的匹配条件;而当在主图中
查找图 7(b)中产生式右图的图柄时,在 vcCGG 框架下产生式右图与主图的任何一个子图都不符合坐标匹配条
件,而在 vdCGG 框架下则可以成功查找到所需图柄.此外,vCGG 要求图柄中实结点在主图中的出入度与产生式
图中对应结点完全相等,保证了图柄中所有与产生式图中实结点对应的结点在主图中只能与虚结点对应的结
点相连接,在图转换过程中避免了悬边的出现.

(a) 主图 (b) cCGG 产生式 p1 (c) cCGG 产生式 p2
Fig.7 The redex matching in vCGG
图 7 vCGG 中的图柄匹配
2.2 文法操作
图文法的主要工作流是图推导与归约,分别面向实际应用中图的生成与分析需求.推导与归约工作流的基
本构成要素是图转换操作.图转换操作根据其执行方向可以分为 L-application 与 R-application,其中,L-
application 是指用产生式右图替换左图在主图中图柄的操作,而 R-application 用产生式左图替换右图在主图中
图柄.L/R application 中的一个重要问题是如何避免转换后的新主图中产生悬边,即嵌入问题.在 vCGG 中,由于
在产生式使用虚结点作为上下文结点,可以使用粘合的方式解决嵌入问题.根据不同的配置粒度要求,vcCGG 和
vdCGG 中 L/R application 的具体步骤如下.
1) 根据当前产生式生成一个产生式实例;
2) 平移产生式实例的右图或左图 G R|L .
¾ vcCGG:将图柄中的任意结点 n 与其在产生式图 G L|R 中的对应节点 n′的坐标差值,即 n.c−n′.c,作
为偏移量平移产生式的另一端 G R|L ;