摘要：

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

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

Abstract:

To address the problems of halting and uncertainty in the derivation workflow in a graph grammar, this study proposes an automatic derivation algorithm for graphs based on an improved graph grammar and applies it to the automatic generation of graph samples. To build the halting mechanism of derivation, a graph grammar named Edge-based Graph Grammar formalism(EGG)is improved, where terminal productions are used to ensure that each non-terminal node could be derived effectively into a terminal node, preserving the graph size. In the generation of graphs, application probabilities are used to guide the selection of productions and redexes, and the uncertainty problem in the derivation is addressed. Based on this, an automatic derivation algorithm is designed that runs in polynomial time complexity and satisfies the requirements of concise derivation. Moreover, a module of graph sample generation is developed for the Edge-based Graph Grammar formalism Supporting System(EGGSS), with an example of the generation of the sample programming flowcharts to illustrate the entire process of the derivation method. The size distribution of graph samples on different allocations of application probabilities is also analyzed and discussed. The experimental results show that lowering the application probability of terminal productions of the proposed method increases the average size from 3.16 to 6.87 with a graph size limit of 10.

Key words: graph grammar, derivation algorithm, terminal production, graph sample generation, program flowchart