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

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

1.2 框架缺陷
由于延续了 EGG 的悬边机制,CGG 存在一个较为明显的表达能力上的缺陷——L cf 图语言问题 [21] .如图 3
所示,图语言 L cf 是由一对“fork”,“join”结点以及它们之间的任意数量(不小于 2)“stat”分支组成的一类流程图.对
于这一类图语言,无法通过有限数量的 EGG 或 CGG 产生式描述所有可能情形下的 L cf 图.其原因在于:如果要描
述任意一个 L cf ,由于“stat”分支的数量是未知的,无法在产生式设计阶段穷举所有分支,从而无法在产生式中确
定“fork”与“join”结点所连接的悬边数量.L cf 图语言问题可以通过定义额外的通配悬边加以解决,然而通配悬边
的处理在一定程度上增加了产生式以及文法操作的复杂性.相比之下,图文法 LGG 和 RGG 则不存在这个问题.
在产生式设计阶段,LGG 可以将出入边数量未知的结点(例如“fork”和“join”结点)作为上下文结点,在匹配时不
需要考虑上下文结点的出入度;RGG 使用双层结构结点中标记的顶点来关联上下文,在匹配时不需要考虑顶点
所连接边的数量.

Fig.3 An example of the graphical language L cf
图 3 一个图语言 L cf 的例子
悬边机制带来的另一个问题是悬边映射问题.在 EGG 和 CGG 的工作流中,当一个主图子图与产生式图符
合图柄匹配条件时,若产生式图中存在一个结点连接了两条及两条以上同方向的悬边,需根据这些悬边在主图
中不同映射情况生成多个图柄进行处理 [20] .如图 4 所示,左侧主图虚线框内的子图与产生式 p1 与 p2 的右图之
间均满足图柄匹配条件.由于产生式 p1 的右图结点“stat”连接了两条同方向的悬边“1”、悬边“2”,两条悬边与主
图中对应结点“stat”所连接的边(stat,a-branch),(stat,b-branch)之间存在两种双射,而在不同双射情况下进行 R-
application 会产生两种具有不同结构的主图,因此,两种双射情况下的图柄应当被视为不同的图柄.这种规定可
以保证图转换结果的唯一性,然而该规定在一些场景下并不是必要的.例如:对于图 4 中的产生式 p2,在任意一种
双射情况下对主图进行 R-application 所产生的新主图均具有相同的结构.原因在于:悬边“1”、悬边“2”在产生式
p2 的左图中只与一个结点“stat 2 ”相连接,在进行子图替换的过程中,主图的余图只能与该结点进行连接,因而不
会出现两种图转换结果.在这种情况下,如果按照上述规定进行归约,则容易因图柄集规模扩大而导致多余回溯
的出现,产生不必要的分析时间开销.
2 vCGG 形式框架
2.1 基本概念

针对空间图文法存在的问题,本章在继承 CGG 形式框架空间语义机制的前提下构建新的空间图文法框架
vCGG,该框架引入虚结点作为上下文结点,描述图柄与产生式之间语法结构与空间语义上的关系,在保留文法
抽象性的同时,增加文法的表达能力与分析效率.由于 CGG 使用两个子框架 dCGG 与 cCGG 分别处理定性与定
量空间语义关系,vCGG 根据空间语义的不同粒度描述分为 vdCGG(virtual-node based discrete coordinate graph
grammar)与 vcCGG(virtual-node based continuous coordinate graph grammar),以下是 vCGG 形式框架中基本概念
的定义.