上下文相关图文法的表达能力分析

• 作者: 吕建 宋巍 曹春 杨启亮 胡昊 邹阳
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 可视化语言 上下文相关 图文法 表达能力 转换算法
• 年，卷（期）: 2012,（7）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 1635-1655
• 分类号: TP301
• 字数: 22590字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.04085

摘要

上下文相关图文法是描述可视化语言的形式化工具.为了直观地刻画并高效地分析可视化语言,已有图文法形式框架均着重于文法形式和分析算法的研究,而忽略了对它们之间表达能力的分析.在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上,通过构造不同形式框架之间的转换算法,揭示并形式化证明了它们表达能力之间的关系.而且,转换算法在不同形式框架之间建立了关联,使图文法的应用不必再局限于一个框架,而是可以选择不同框架分别进行图的描述和分析,从而提高了上下文相关图文法的易用性.