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

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

坐标差值;而 dCGG 要求产生式图 G | L R 和图柄 Q 具有等价的空间拓扑结构,即 G | L R 中任意一个结点和它在图柄
Q 中对应的结点具有完全相等的离散坐标值.
在图文法的推导或归约工作流中,在根据一个产生式图找到其在主图中的图柄后,便可以对图柄执行图转
换操作.根据不同的配置粒度,cCGG 和 dCGG 中图转换操作的具体步骤如下.
1) 根据当前产生式生成一个产生式实例;
2) 平移产生式实例的右图或左图 G | R L .
¾ cCGG:将图柄中的任意结点 n 与其在产生式图 G | L R 中的对应节点 n′的坐标差值,即 n.c−n′.c,作为
偏移量平移产生式的另一端 G | R L ;

¾ dCGG:首先,在产生式图 G | L R 中选择一个具有最大“Y”值的结点 n′,若存在多个(大于 1)这样的结
点,则从中选择具有最小“X”值的结点;其次,将图柄中的对应结点 n 与 n′的坐标差值 n.c−n′.c 作
为偏移量平移另一个产生式图 G | R L ;
3) 从主图中删除图柄;
4) 将产生式图 G 嵌入到主图中.
| R L
图 2 是一个 CGG 中 R-application 的例子,其中,图 2(a)是一个给定主图,图 2(b)和图 2(c)分别是一个 cCGG
产生式和 dCGG 产生式.对于 cCGG 产生式,产生式实例的左图使用偏移量(0,1.5)进行平移,该偏移量是图 2(a)
中虚线框内所示图柄与产生式右图之间匹配结点的坐标差值.而对于 dCGG 产生式,首先在产生式右图中选择
具有最大“Y”坐标值的结点“stat 1 ”,然后将图柄中的对应结点与结点“stat 1 ”的坐标差值(−1,0)作为偏移量,平移产
生式左图.在该例中,使用 cCGG 产生式和 dCGG 产生式对图柄进行 R-application 操作,得到的是两个不同的主
图,如图 2(d)、图 2(e)所示.

(a) 一个主图 (b) 一个 cCGG 产生式

(c) 一个 dCGG 产生式 (d) cCGG 下新主图 (e) dCGG 下新主图
Fig.2 An example of CGG R-application
图 2 CGG 中 R-application 实例