项目来源于湖北省教育厅科学技术研究计划项目《图文法关键技术及应用研究》，编号：B2013101 针对一维字符语言建立的形式语言理论对计算机科学的发展起到了重大的作用。但是，随着计算机软件技术的发展，特别是可视化人机交互界面技术的发展，具有图操作功能的可视化语言必将扮演越来越重要的角色。可视化的图语言表达更直观、语义更丰富、操作更简便。由于基于一维字符串的形式化理论不能更好地描述图对象间的二维特性，于是，产生了基于图的二维图文法。图文法可以为可视化图语言提供准确的语法规范、为图语言的定义、图生成器的构造及分析器的构造奠定必要的理论基础。 早在二十世纪六十年代就有人提出采用图文法的方法来解决有关图形处理的问题。国外对图文法的研究较多，国内相对较少。近几年，国内已有几个高校开始了这方面的工作。不足的是，这些研究中的大多数都只局限于对上下文无关文法的考虑，而上下文无关文法描述和处理具有复杂结构和关系的二维数据的能力较差。为了方便描述和处理结构复杂的图，近些年来，人们开始对上下文相关图文法进行研究，但是该研究领域目前还存在不少有待深入探讨的问题。其中，文法从一维扩展到二维所引出的嵌入问题（Embedding Problem） ，是首先要解决的问题，在此基础上，文法的成员可判定性、表达能力、以及文法分析器的计算复杂性等也都是值得深入研究的问题。 图文法的理论研究主要采用基于代数的方法和基于几何的方法，分别以代数理论（范畴论）和集合论为基础来形式化定义和描述图文法的机制。图文法分为上下文无关图文法和上下文相关图文法。上下文无关图文法在处理复杂关系和结构的二维数据上能力较弱。近年来，人们开始对上下文相关图文法进行研究。目前较为流行的上下文相关图文法主要有Rekers和Schurr的LGG、Zhang等人的RGG以及Adachi等人提出的NCE CSGG，河海大学的曾晓勤老师等人提出了EGG。LGG将刻画上下文的边与结点同时引入产生式的左右两端，解决了嵌入问题。LGG的语法形式较为直观、易于理解，但其分层方法和语法分析算法过于复杂，不实用。RGG将图中的结点使用双层结构表示，并引入标号机制解决嵌入问题，但不够直观、难于理解，在实际应用上较难。NCE CSGG在产生式规则中给出连接指令，明确指出边与结点的连接要求，避免了悬边的产生，但在实际应用中构造产生式规则和连接指令较复杂。EGG以边作为上下文来构造图文法，目前仍在不断完善中。 图文法应用十分广泛，特别是在软件可视化和信息可视化方面。它是可视化图语言的语法描述与分析的有力工具，如ER图、数据流图、控制流图等；也是软件系统体系结构、软件工程描述与设计的有力工具。 综上所述，针对图文法自身的诸多理论问题还有待更深入地研究。另外，在图文法的应用方面虽然取得了一些研究成果，但在针对二维图处理的诸多领域的应用上还有待探索。 技术原理：主要应用于软件可视化领域，涉及到的相关技术有：基于度序列分组的图同构判断技术；给出了产生式选择无关条件的判断条件，提高了产生式选择无关条件判断的效率，降低了归约算法的时间复杂度；提出了图文法并行归约的条件，在并行归约的情况下，提高了归约的时间效率。 性能指标:图文法的归约效率：传统的图文法归约算法的时间复杂度为指数级。实际指标：通过度序列分组技术、产生式无关条件的判断及并行归约算法，可有效提高归约的效率。在产生式满足选择无关条件的情况下使时间复杂度降为多项式级。 1、图文法形式化方法 本课题拟以图论为工具，从分析图柄与主图间的连接边入手，研究用边来表示和处理上下文信息，在对图进行分析和变换时更加方便和直观，而不需要进行图格式上的转换。 2、图文法归约方法 本项目提出了产生式选择无关条件的判断条件，提高了判断的效率，从而降低了归约的时间复杂度达到多项式级。 3、图文法的应用 本课题则尝试去探索上下文相关图文法在某个计算机相关领域中的一类基本问题中的应用，试图给出此类应用的一般途径，这是以前的研究工作中所没有涉及到的。 本成果可用于软件可视化及软件自动生成等领域。在软件的设计及开发阶段应用到大量的软件模型，而其主要是以二维的图形形式来表示。图文法的技术可以用于判断模型的准确性及规范性。同时，每种软件模型都从一个侧面反映了实际业务或软件本身的形态，其之间又具有关联性。通过对软件模型的分析，使用图文法技术可以实现软件模型的转换，及最终的软件自动生成。 本成果可用于软件可视化及软件自动生成等领域。目前存在的主要问题是，怎么对各种软件模型进行统一标准，怎么形式化表示各种软件模型。目前以实现了流程图和程序源代码之间的相互转换，在后续的研究工作中，将对软件工程中的各类模型进行分析，从而实现模型之间的相互转换及软件的自动生成。无