● 摘要
随着软件复杂性的增加，可视化建模在软件工程领域发挥着日益重要的作用，从形式语言角度对建模语言进行研究，可提高建模语言的规范性、增强建模支持系统的可重用性。一是因为有着严格语法定义的文法规范，可使建模语言适合计算机的自动解释和分析；二是抽象层次分明的描述体系，可使建模语言的实现分割成良式定义的模块，如图形编辑、模型定义和模型分析。但是目前可视化建模语言一般是基于元模型或描述性规则等描述方法，支持工具则采用语法制导编辑模式，虽然便于用户定制领域模型，但是半形式化和非形式化的描述既不利于模型分析和验证，也导致软件开发过程复杂。另一方面，可视化语言理论存在计算性能的瓶颈问题，缺乏对可视化建模语言的有力支持。为了改善这种情况，本文对高维文法及其语法分析进行了研究，提出一种可以描述多种可视化建模语言的文法体系，和分析效率高于同类成果的语法分析算法，并以多种建模语言为例，对文法体系的描述能力和分析方法的效率进行了验证。最后，基于该描述体系设计了具有自动语法分析功能的支持系统。本文的主要内容和贡献为：(1)将可视化语言和字符串语言进行对比，分析了可视化语言、尤其是可视化建模语言的特征：图符通过连接式和几何式关系在二维空间按一定规则构建成结构化或非结构化图形。在对比了当前几种典型可视化语言描述体系的优缺点之后，提出了一个基于关系结构的可视化建模语言描述体系，以包含符号集和关系集的字母表为基础，通过连接关系、空间关系和逻辑关系在较高抽象层次上描述模型的组成规则。并且研究了关系文法及其语法分析中需要解决的几个关键问题：多维结构的描述和分析、上下文相关性的支持、图形的起始分析位置和扫描顺序等的解决方案。(2) 基于对符号关系文法SRG(Symbol-Relation Grammar)的扩展，提出了改进的符号关系文法ESRG(Extended Symbol-Relation Grammar)。SRG是一种通用的可视化语言描述体系，但是分析效率极低，不能直接应用。ESRG是一种扩展的上下文无关关系文法，通过对SRG附加合流性、连通性、重写确定性等若干约束，提高了文法体系的语法分析效率，并且改变了产生式规则的格式，提高文法体系的可读性，增加了上下文元素的引用，使文法体系可以描述复杂结构的可视化建模语言。本文通过对多种建模语言实例的描述说明了其具备较强的描述能力。(3) 针对ESRG文法设计了二维扩展Earley分析算法。其主要特点是支持无序分析，对输入语句和产生式没有附加任何格式限制，并且由于可列举所有可能的分析路径，因此能处理有歧义的文法。分析算法的扩展主要基于三个出发点：一是一维分析空间到二维分析空间的扩展；二是产生式右部从自左至右的顺序推导到以符号关系约束为制导的、无序推导的扩展；三是向前查看一个符号及其关系、剪裁无效推导分支，提高了分析过程向前推进的确定性，从而有效改善算法的分析效率。本文以不同输入规模的状态图和流程图为例，对比了ESRG文法语法分析算法和SRG文法语法分析算法的成本，说明了ESRG文法语法分析器的高效性。(4) 设计了基于关系文法体系的可视化建模语言支持系统，实现了ESRG文法的通用语法分析器。用户只需通过窗口输入不同可视化建模语言的ESRG文法，语法分析器就可对输入图形进行自动分析。这种通用语法分析器的设计，使得不必为每个可视化建模语言编写语法分析程序，从而降低了语言实现的复杂度和维护的难度。