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

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

采用定性描述,SG 根据文法定义的定量空间关系绘制图形,CGG 使用离散坐标和连续坐标为空间语义提供基
于不同粒度的配置.为了获得全面而系统的比较结论,本节从形式化框架、文法表达能力、分析效率、以及文
法应用这 4 个维度对这几种框架进行对比分析.

3.1 形式化框架
直观性是衡量一个图文法形式框架的关键特性之一,而上下文深度是评价文法框架直观性的一个重要依
据.上下文深度是指产生式图中内部结点到上下文结点的最短路径长度,具体值等于最短路径中结点(不包含起
始结点)和边数量之和的二分之一.上下文深度大于等于 1 的文法称为显式文法,而小于 1 的文法称为隐式文法.
一般而言,显式文法的直观性高于隐式文法,而显式文法的不足在于上下文结点描述的复杂性,在很多应用场景
下较难使用有限的上下文结点描述所有可能出现的上下文信息.例如:LGG 使用通配符描述上下文信息,当通配
符数量较大时,产生式构造变得过于复杂而难以设计.对几种框架的上下文深度进行对比,如图 9 所示:SGG 将上
下文信息以顶点形式内嵌在结点的双层结构中,上下文深度为 0;CGG 继承了 EGG 的悬边机制,采用悬边表示上
下文连接,因此上下文深度为 0.5;SG 在形式上没有对上下文信息进行描述,上下文深度为空;vCGG 在产生式中
引入了虚结点,上下文深度为 1,并且虚结点在图柄查找过程中不需要匹配其标号语义信息,因此不需要考虑虚
结点除空间坐标之外的语义信息,相比 LGG 具有更高的抽象性,产生式结构也更为简洁而易于设计.此外,与前
身 CGG 相比,由于不再需要定义悬边图作为图柄,vCGG 中图的形式与定义更加符合图论的规范标准.

(a) SGG 产生式 (b) SG 产生式

(c) CGG 产生式 (d) vCGG 产生式
Fig.9 Comparison between the productions of SGG, SG, CGG and vCGG
图 9 SGG、SG、CGG、vCGG 产生式比较
形式化框架比较的另一个重点是子图嵌入问题的解决方法,大致可以分为两种:一种是使用嵌入规则进行
图转换操作,具体方法是在主图中首先删除图柄,之后根据嵌入规则将产生式图嵌入主图中;另一种方法使用结
点粘合的方式,首先在主图中删除图柄中除了与上下文结点匹配的结点之外的部分,再根据产生式两端上下文
结点的双射关系进行结点粘合.总体而言:嵌入规则方法的形式上更加灵活,例如,用户可以通过修改嵌入规则
改变嵌入前边的方向;粘合方法的规范性更好,可以确保文法操作中不会出现悬边.相比之下,SG、SGG、CGG
都是使用嵌入规则的方式进行子图嵌入操作,而 vCGG 采用粘合方式将作为上下文结点的虚结点和其对应结
点进行粘合并去除虚标号,从而得到合法的新主图.
3.2 文法表达能力

图文法形式框架的表达能力指的是文法能够描述图语言的范围,如何增强图文法的表达能力,是该领域中
的一个重要研究话题.与 CGG 相比,对于图语言 L CF 问题,由于引入了虚结点机制,vCGG 可以将第 1.2 节中图 3
的结点“fork”,“join”放入产生式中作为虚结点,直观而简洁地描述所有形如 L cf 图语言的多分支结构图.从空间
语义配置的全面性上对几种框架进行对比,vCGG 对图语言空间语义的描述更加全面.vCGG 在产生式中引入了
虚结点作为上下文结点,虚结点在图柄查找时不需考虑标号语义,匹配的是虚结点与实结点之间的语法结构以
及空间语义关系,因此,vCGG 不仅可以描述产生式非公共子图(不包含上下文结点的部分)的空间语义模型,也
可以通过上下文结点的空间语义描述非公共子图与主图之间的坐标方位关系.与之对比,SG、SGG 与 CGG 的
产生式只能描述非公共子图内部空间语义模型,缺乏对图柄与主图之间空间语义关系的描述能力,因此,空间语