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

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

以 CGG 为例,由于产生式中缺少显式的上下文结点“a”和“b”,导致在产生式设计阶段结点“c”坐标的计算复
杂化且易出错,也在一定程度上增加了产生式设计人员学习曲线的陡峭程度,不利于布局方法的推广应用.
4 结论与展望

针对空间图文法形式框架存在的问题,本文对前期工作中构建的坐标图文法 CGG 进行改进,通过引入虚结
点描述产生式与主图之间的语法结构与空间语义关系,并构建了一个新的空间图文法形式框架 vCGG 与几种
典型空间图文法形式框架进行对比分析,vCGG 具有以下几个优点.
(1) 在产生式中引入虚结点作为上下文结点,上下文信息得到了显式的描述,文法具有更好的直观性;
(2) 采用粘合的方式进行图转换操作,有效防止了转换过程中出现悬边,操作的规范性得以保证;
(3) 通过虚结点描述上下文与产生式之间的空间语义关系,在保留上下文抽象性的同时,使文法具有更全
面的空间语义配置性能;
(4) 使用虚结点代替悬边描述上下文,在增强了文法表达能力的同时,避免了 CGG 中的悬边映射问题;
(5) 在归约的过程中,能够通过较少的产生式更早地发现语法与语义错误并及时停机,减少了无效归约的
数量.
在今后的研究中,在图文法理论研究方面,我们将进一步改善空间图文法形式框架,尝试利用图形元素之间
的空间拓扑关系进一步缩小图柄搜索空间,减小分析算法的时间开销,使文法的实用性更强.在图文法应用方
面,我们考虑将图形元素的空间特征作为关联属性,为产生式关联语义动作或条件谓词作为属性文法,在图转换
过程中加入语法制导翻译,尝试将图文法应用在建筑外观建模、工业设计与验证等领域中,并开发一个空间图
文法系统平台,为文法操作以及相关应用的落地提供支撑.

References:
[1] Shi Z, Zeng XQ. Bidirectional transformation between BPMN and BPEL with graph grammar. Computers and Electrical
Engineering, 2016,51:304−319.
[2] Hibshman J, Sikdar S, Weninger T. Towards interpretable graph modeling with vertex replacement grammars. In: Proc. of the Int’l
Conf. on Big Data. 2019. 372−376.
[3] Li C, Huang L, Chen L. Breeze graph grammar: A graph grammar approach for modeling the software architecture of big data—
Oriented software systems. Software Practice & Experience, 2015,45(8):1023−1050.
[4] Duarte M, Ribeiro L. Graph grammar extraction from source code. In: Proc. of the Brazilian Symp. on Formal Methods. 2017.
52−69.
[5] Miyadera Y, Murakami C, Anada K, et al. Attribute graph grammar method for research information collection and sharing. In:
Proc. of the Int’l Conf. on Digital Information Management. 2016. 235−242.
[6] Chen Q, Shi D, Feng G, et al. On-line handwritten flowchart recognition based on logical structure and graph grammar. In: Proc. of
the Int’l Conf. on Information Science & Technology. 2015. 424−429.
[7] Park S, Nie X, Zhu SC. Attribute and-or grammar for joint parsing of human pose, parts and attributes. IEEE Trans. on Pattern
Analysis and Machine Intelligence, 2017, 1555−1569.
[8] Julcaaguilar F, Mouchère H, Viardgaudin C, et al. Top-down online handwritten mathematical expression parsing with graph
grammar. In: Proc. of the BeroAmerican Congress on Pattern Recognition. 2015. 444−451.
[9] Stiny G, Gips J. Shape grammars and the generative specification of painting and sculpture. Proc. of the Workshop on
Generalisation & Multiple Representation Leicester, 1971,71:1460−1465.
[10] Stiny G. Pictorial and formal aspects of shape and shape grammars and aesthetic systems. Los Angeles: University of California,
1975.
[11] Mamoli M. A shape grammar for the building-type definition of the ancient Greek and Roman library and the evaluation of library
plans. In: Proc. of the Artificial Intelligence for Engineering Design Analysis and Manufacturing. 2020. 1−16.
[12] Li YN, Zhang K, Li DJ. Rule-based automatic generation of logo designs. Leonardo, 2017,50(2):177−181.