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

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

义配置的全面性不如 vCGG.
3.3 分析效率
在文法分析效率方面,由于图语言结构的二维非线性特点,文法分析过程中容易发生大量的回溯,造成了分
析算法的最坏时间开销通常为指数级.继承自 RGG、SGG 可以使用一个时间开销为多项式级的分析算法——
SFPA 算法(selection-free parsing algorithm) [15] .然而,SFPA 算法对产生式提出了约束较高的选择无关条件作为
归约前提,导致 SFPA 的通用性有所不足.由于归约中回溯的不可避免性,大多数图文法分析算法的设计目标是
尽可能地降低图柄查找过程的时间开销.假设 n 是主图的结点数量,m 是产生式右图的结点数量,n 与 m 代表了
主图与产生式的规模,图文法的图柄查找时间开销的时间复杂度在通常情况下为 O(A n m ) ,即在规模为 n 的主图
能够查找到规模为 m 的不同结点顺序子图的最多数量.引入了空间语义机制后,由于产生式以及主图中的结点
可以按照其空间拓扑关系进行排序,利用该顺序指导子图匹配过程可以有效缩小图柄的查找空间,从而减少时
)
间开销.因此,SGG 与 CGG 的图柄查找算法时间开销位于 O(C m [13,18] 量级,将传统图柄查找过程的排列问题转
n
变成了典型的组合问题.继承自 CGG、vCGG 可以使用 CGG 的图柄查找算法,通过对结点排序而缩小图柄的搜
索空间,并且由于图柄查找过程中不需要考虑悬边的映射问题,vCGG 分析算法的实际时间开销小于 CGG.
图文法分析性能的评价不仅体现在其时间开销上,对非法语义关系与语法结构作出判断的及时性也是评
价的一个重要依据.与 SG、SGG、CGG 相比,vCGG 产生式增加了上下文与产生式非公共子图之间的空间关系
约束,因此在分析过程中可以更早地发现错误,即时停机从而减少无效归约.例如,图 10(a)是一个任意给定的主
图,不满足图 10(b)、图 10(c)中产生式对图形元素的空间语义约束.在归约时,图 10(b)中 CGG 产生式需要根据
产生式 p1,p2 对主图进行两次归约才可以判定出该语义错误,而 vCGG 产生式只需要图 10(c)中的一个产生式进
行一步归约便可判断出其空间语义关系的非法性,在一定程度上减少了无效归约的数量.

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

(c) vCGG 产生式

Fig.10 Detection of invalid host graph in CGG and vCGG
图 10 CGG 与 vCGG 对不合法主图的检测

3.4 文法应用
通过上述对比,vCGG 不仅可以描述产生式图内部的空间语义模型,也可以将虚结点作为上下文结点直观
地描述产生式图内部与主图的坐标方位关系,提供了相对更全面的空间语义配置能力.因此,在空间图文法的实
际应用中,vCGG 可以处理一部分 SG、SGG 与 CGG 较难应对的实际应用问题.以图模型布局需求为例,图 11
是一个简单的程序流程图,其布局要求为:结点按从左到右的顺序排列,每一个标号为“if”或“while”的结点需位
于前一结点(设为 n)的正下方,而标号为“Y-branch”或“endwhile”的结点需位于结点 n 的正右方.基于虚结点对上
下文空间语义的显式配置,使用 vCGG 产生式可以较为容易地实现该布局要求.图 12 是一组用于绘制流程图的
vCGG 产生式.而使用该组产生式进行推导操作即可绘制出满足上述布局要求的程序流程图,如图 13 所示.