基于图文法的逻辑型图样本生成方法

摘要：

针对图文法的推导工作流中存在的停机和不确定性问题,提出一种基于改进图文法的图自动推导算法,并将其应用于图样本生成.为了建立推导的停机机制,对EGG图文法进行改进,通过终结产生式确保每个非终结点可以在保持原有图规模的情况下进行有效推导并生成终结点.在图生成过程中,通过应用概率指导产生式和图柄的选择,解决了推导操作的不确定性问题.利用图自动推导算法,在满足精准推导要求的情况下保持了多项式级的时间复杂度.在EGGSS环境中开发图样本生成模块,以程序流程图样本生成为例演示推导算法的详细过程,并对不同应用概率分配下所生成图样本的规模分布情况进行分析和讨论.实验结果表明,在图样本规模限制为10的情况下,该方法通过降低终结产生式应用概率可使图样本的平均规模从3.16增至6.87.

关键词：图文法、推导算法、终结产生式、图样本生成、程序流程图

所属期刊栏目：49

分类号：TP182(自动化基础理论)

资助基金：国家自然科学基金62002155

在线出版日期：2023-11-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：203-210