上下文相关图文法及其应用研究

发布时间：2017-12-08 14:19

  本文关键词：上下文相关图文法及其应用研究

  更多相关文章： 上下文相关图文法 形式框架 表达能力 产生式上下文 语法分析算法

【摘要】：可视化语言提供了一种可视、直观与抽象的方式去描述复杂对象的结构与构成的方法,已广泛应用于计算机相关领域。可视化语言研究的最基本问题之一是如何描述可视化语言。与形式文法用于描述文本语言类似,图文法是描述可视化语言的自然选择。由于上下文无关图文法在易用性和表达能力上均存在明显不足,上下文相关图文法的研究成为必然。然而,已有上下文相关图文法在形式框架的完备性上尚多有不足,诸多关键问题研究仍面临挑战,具体表现为：(1)在表达能力上,对于已有形式框架表达能力的理论分析有所欠缺;(2)在产生式形式上,隐式的形式框架普遍存在因产生式中上下文缺失而导致的直观性差的问题；(3)在语法分析算法上,已有的两类算法存在分析效率低下或适应范围过窄的问题。本文提出了一个一般性的上下文相关图文法的概念框架,并在此基础上对上述问题进行了较为系统性的研究,主要工作如下：1.在分析与归纳已有上下文相关图文法形式框架的基本特征基础上,通过构造不同形式框架图文法实例之间的转换算法,揭示并证明了这些形式框架的表达能力之间的关系。一方面,这些结论揭示了已有上下文相关图文法形式框架的表达能力之间关系,补充并完善了图文法的表达能力之间关系的理论。另一方面,这些算法也为不同形式框架图文法实例之间的转换提供了一种可行的方法,使上下文相关图文法的应用不再拘泥于一个形式框架,而是可以在不同形式框架之间选择适当的描述形式与分析算法,从而提高了这些形式框架的易用性。2.针对隐式上下文相关图文法形式框架中普遍存在的因产生式中上下文缺失所导致的直观性差的问题,以RGG形式框架为基础,提出了一种上下文的形式定义与计算方法来揭示产生式中所隐含的上下文。在产生式之间的偏前驱关系与全前驱关系概念基础上,形式化定义了产生式的上下文,刻画了上下文的基本特征与上下文存在的一个充分条件,并构建了上下文与上下文实例之间的关联。在此基础上构造了一组算法来计算产生式的上下文。对原本隐含在产生式中的上下文的发掘增强了产生式形式的直观性,从而有助于图文法的理解与设计。而且,此方法还可以推广到其它隐式上下文相关图文法形式框架。3.针对已有上下文相关图文法的语法分析算法中存在的问题,提出了两类相应的改进方法。一、针对仅适用于合流图文法的语法分析算法的适用范围过窄的问题,以RGG形式框架为例,提出了两种转换算法,将非合流的产生式集转换为生成相同图语言的合流产生式集,从而拓宽了这类算法的适用范围。第一种算法基于扩充的RGG形式框架XRGG,将非合流的RGG产生式转换成合流的XRGG产生式；第二种算法基于产生式上下文,将非合流的RGG产生式转换成合流的装配了裁剪过的1层上下文及其派生上下文的RGG产生式。两种算法的适用情形有所不同。二、针对通用语法分析算法效率低下的问题,提出了一种上下文匹配方法,用产生式的上下文去匹配主图中图柄的上下文来进一步鉴别待替换图柄,以尽可能地排除不必要归约,从而提高了通用算法的分析效率。4.研究了上下文相关图文法在程序并行性分析中的应用。针对并行性分析往往需要先从程序代码中抽取出控制与数据流图或其它依赖图的问题,基于RGG形式框架,定义了一种任务级的并行编程图语言GPPL来直接描述顺序或并行程序的控制与数据流图,并提出了相应的并行性分析算法以挖掘GPPL图程序的并行性特征,从而使并行性挖掘避免了从程序中抽取出相应依赖图的过程。与已有方法相比,GPPL图的形式更为简洁与直观和更具表达能力,而且算法的并行性挖掘能力也更强。5.设计并部分实现了一个上下文相关图文法支撑系统,以支持基于上下文相关图文法的图语言设计、分析及应用。系统提供了可视化的用户操作界面,其主要功能涵盖图文法编辑与语法检查、产生式上下文计算、以及在图文法合流判定基础上的对于主图的语法分析。而且,在此支撑系统上实现了对GPPL图语言的定义和一个GPPL图的语法分析。
【学位授予单位】：南京大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP391.1
，

本文编号：1266694