刘禹锋,杨 帆

(南京财经大学 信息工程学院,江苏 南京 210046)

作为一种丰富的信息描述手段,可视化语言(可视化图)是软件系统概念设计阶段中重要的人机交互工具,例如数据库系统概念设计阶段的 E-R(entity-relationship)图、面向对象系统中的 UML(unified modeling language)图以及描述离散并行系统的Petri 网.可视化语言研究的重点之一是如何使用有效而又规范的方式去描述各种不同类型的可视化语言.一部分研究者尝试使用一维字符文法描述可视化语言,然而,由于图的二维性以及非线性特点,字符文法在描述可视化语言时有着表达能力不足以及直观性较差等问题.基于形式语言理论,图文法是一种使用产生式(图重写规则)进行图语言定义与分析的二维化形式化工具.使用图文法对各种可视化语言语法结构的描述、操纵和分析,具有直观明了和简便的优点.至今,图文法已被广泛地应用于各种可视化语言的配置与分析中,例如图语言定义与转换[1]、图模型的动态分析[2].不仅如此,图文法还被广泛地应用于软件系统建模[3,4]、信息可视化[5]、模式识别[6-8]等领域.

作为二维或三维空间上最重要的特征之一,空间语义信息在可视化语言的空间拓扑结构描述以及空间知识呈现上是不可或缺的关键因素之一.然而,大多数图文法在面向空间语义处理需求时存在诸多困难之处.Stiny和Gips 从描述空间元素形状的角度出发,提出了形状文法SG(shape grammar)[9,10].SG 将形状定义为一系列空间元素的有限排列,例如线……