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

作者：刘禹锋^*; 杨帆; 刘健

来源：计算机工程, 2023, 1-11.

DOI：10.19678/j.issn.1000-3428.0066285

• 图文法
• 推导方法
• 终结产生式
• 图样本生成
• 程序流程图

借助于归约工作流，图文法被广泛地应用于可视化语言的语法语义分析中。与之对比，图文法的推导工作流较少被直接应用于实际工程，而更多地被用于各类可视化语言的形式定义中。针对推导工作流中存在的停机问题和不确定性问题，本文提出了一个基于改进图文法的图模型推导方法，并将其应用于图样本自动生成中。为了建立推导的停机机制，对图文法EGG（Edge-based Graph Grammar Formalism）进行了改进，通过终结产生式确保每个非终结点可以在保持原有图规模的情况下进行有效推导并生成终结点。在图生成过程中，通过应用概率指导产生式和图柄的选择，解决了推导操作的不确定性问题。在此基础上设计了一个图自动推导算法，该算法在满足精准推导要求的情况下维持了多项式级的时间复杂度。此外，在EGGSS (Edge-based Graph Grammar Formalism Supporting System) 环境中开发了一个图样本生成模块，以程序流程图样本生成为案例演示推导算法的详细过程，并对不同应用概率分配下所生成图样本的规模分布情况进行了分析和讨论。实验结果表明，在图规模限制为10的情况下通过降低终结产生式应用概率可以使样本的平均规模从3.16增至6.87。

• 单位
  南京财经大学