图文法关键技术研究及应用

图文法是一维字符串文法在二维平面空间对象上的自然扩展，是描述可视化图语言语法的形式化方法，可为图语言的定义、图生成器及图分析器的设计奠定必要的理论基础和技术支持。但是，形式化上下文相关图文法的研究目前在理论上都还不够成熟，仅有的少数几种图文法形式化方法在处理图文法几个关键问题（如嵌入问题、成员判定问题、产生式形式、表达能力、和语法分析复杂性等）上均存在这样或那样的不足。这些理论上的缺陷在很大程度上制约了图文法在信息可视化及软件可视化等相关领域的广泛应用。本课题拟从理论和技术上探索通用且实用的图文法形式化方法。首先，围绕产生式的构造，力图建立一个能有效解决嵌入问题与成员判定问题的形式化框架；然后在此基础上，实现一个能直观便捷定义图文法的软件系统平台，来开展对上下文相关图文法表达能力，和降低语法分析复杂性等课题研究；最后，还将研究图文法在可视化图语言和软件工程等与图密切相关领域中的应用途径。

形式文法是计算机科学的重要理论基础。图文法是传统一维字符串文法向二维空间对象的扩展，是定义和分析可视化图语言的理论基础。本项目研究重点解决图文法形式化中面临的一些关键问题，如嵌入问题、成员判定问题、语法分析高复杂性问题、产生式形式和表达能力强弱问题，并尝试探索图文法的实际应用。经过几年的努力，项目研究取得了一些成果：给出了新的形式化方法和操作机制来描述时间和空间信息、提出了新的降低归约算法复杂性和分析文法表达能力的途径、探索了新的图文法应用领域、以及开发了支持图文法操作机制的软件系统平台。这些研究成果将促进软件可视化和信息可视化领域的向前发展，使信息产业在国民经济和社会发展中发挥更大的作用。