计算机工程

作者：刘禹锋, 杨帆, 刘健

单位：南京财经大学 信息工程学院, 南京 210046

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

基金：国家自然科学基金(62002155)

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

来源：2023年第11期

《计算机工程》期刊编辑部

查看计算机工程杂志2023年第11期