（模式识别与智能系统专业论文）一种基于边的上下文相关图文法形式化框架.pdf

河海大学硕士学位论文摘要 摘要 形式语言理论对计算机科学的发展起了重大的作用 作为对传统字符文法扩 展的图文法的形式化研究 其重要意义是不言而喻的 图文法研究中最主要的几 个问题包括 嵌入问题的解决 文法类型的划分 成员问题的判定和语法分析计 算复杂性的降低 过去几十年中已经有一些图文法形式化方法及图文法应用方面 的成果问世 但它们大多是基于上下文无关图文法的 而随着图文法研究的不断 深入 人们发现上下文相关图文法具有更广阔的应用前景 目前已经有一些上下 文相关图文法被提出 但它们或者是过于繁琐 既不直观又不简便 不方便使用 或者是计算复杂性太高 不实用 本文首先对图文法发展及其现状进行了简要介绍 并重点讨论了图文法研究 中的几个主要问题 在此基础上 针对现有上下文相关图文法的一些不足 围绕 解决图文法中关键问题 嵌入问题提出了一个基于边的上下文相关图文法形式 化框架 并对由此定义的文法的一些性质及相应的归约算法进行了讨论 接着 对所提出的图文法与已有的文法进行了比较 然后 给出了一个该文法的应用实 例 利用它来描述设计模式的演化 最后 对全文进行了总结并展望了今后值得 进一步研究的一些问题和方向 关键词 图文法 形式化 上下文相关 嵌入问题 设计模式 河海大学硕士学位论文abstmd a b s t r a c t i ti sw c nl n o 啪t h a tf 1 0 咖a l i a n g u a g e t h e o r yp l a y s 柚i m p o r t a n tm l ei i lt h e d e v e l o p m e n to f c o m p u t e rs c i e n c e 柚ds ow i l lb et h er e s e a r c ho n 铆od i i t l e n s i o n a lg r a p h g r a i t l m a rf o m a l i s m w h i c hi s 锄e t e n s i o no fo n ed i m e n s i o n a ls t r i i l gg r a m m a r s t 1 l e m a i l lp r o b l e m so ft h er e s e a r c ho ng r a p hg r 姗m a ri 1 1 c l u d et h es o l u t i o nt 0e m b e d d i n g p r o b l e m t h ec l a s s i f i c a t i o no ff a p hg r 猢a r s t h ed e c i d a b i l i t yo fm e m b e r s h i pp r o b l e m 锄i dt h er e d u c t i o no fp a r s e r sc o m p l e x i 哆i nt h ep a s td e c a d e s t h e r ew e r es o m eg m p h 伊锄m a r s 锄dt h e i ra p p l i c a t i o n sp r o p o s e d 锄dm o s to ft h e ma r eb a s e do nc o n t e t 丘 e e g r a p hg r a m n l a r s a l o n gw i t ht h ed e e p e n i n go ft h e1 c s e a r c h c o n t e x t s e n s i t i v eg r a p h g r a i n m a rs h o w saf i m ev i s t a n o a d a y ss o m ec o n t e t s e n s i t i v eg r a p hg r a l l l m a r sh a v c a r i s e n h o e v e r t h e ya r ce i t h e rt o oi f l t r i c a t et ou s eo rt o oc o m p l e xt oc o m p u t ef o rr e a i a p p l i c a t i o n s n i sp a p e rf hb r i e n ym r o d u c e st h cd e v e l o p m e n ta n dc u 盯e n ts t a t u so fg r a p h g r a m m a r s e s p e c i a l l yt h ek e yp r o b l e m si i lt h er e s e a r c ho fg r a p hg r a m m a r s c o n s i d e r i n g t h es h o r t c o m i n g so fe x i s t i l l gc o n t e t s e n s i t i v eg r a p hg r 啪m a r w ep r o p o s e 锄e d g e b a s e dc o n t e t s e n s i t i v ef a p hg r a m m a rf 0 啪a l i s mw i t hac o n c e n t r a t i o no ns o l v i n gt h e k e yg r a p hg r a n l m a rp r o b l e m e m b e d d i n gp r o b l e m a n dd i s c u s st h e 危a t u r e so ft h e p r o p o s e dg r a p hg r a m m a ra n d sp a r s i l l ga l g o r i t h m t h e n s o m ec o m p a r i s o n so ft h e p r o p o s e dg r a p hg m m m a r sw i t ho t h e re x i s t i n g 鲈舭瑚a r sa r eg i v e ni nt h ep a p e r a r e n a r d s a na p p l i c a t i o ne x a l i l p l eo f t h eg r a p hg r a m m a ri sg i v e n l b rd e s c r i b i n gd e s i g i l p a t t e me v o l u t i o n f i n a l l y as u m m a r y i sg i v e na n df h r t h e rr e s e a r c h e so ng r a p hg r a m m a r s a r ep r e v i e w e d k e y w o r d s g r a p hg r a m m a r f o m a l i s m c o n t e t s e n s i t i v e e m b e d d i n gp r o b l e m d e s i g np a t t e m i l 学位论文独创性声明 本人所呈交的学位论文是我个人在导师指导下进行的研究工作及 取得的研究成果 尽我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经发表或撰写过的研究成果 与我一同工作的 同事对本研究所做的任何贡献均已在论文中作了明确的说明并表示了 谢意 如不实 本人负全部责任 论文作者 签名 注 手写亲笔签名 学位论文使用授权说明 年月日 河海大学 中国科学技术信息研究所 国家图书馆 中国学术期 刊 光盘版 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档 可以采用影印 缩印或其他复制手段保存论文 本人电子文 档的内容和纸质论文的内容相一致 除在保密期内的保密论文外 允 许论文被查阅和借阅 论文全部或部分内容的公布 包括刊登 授权河 海大学研究生院办理 论文作者 签名 注 手写亲笔签名 年月日 河海大学硕士学位论文第一章绪论 1 1 研究背景 第一章绪论 随着计算机软件技术的深入和快速发展 特别是人机友好界面技术的发展 具 有图操作功能的可视化图语言正在扮演越来越重要的角色 有望逐步成为软件开发 的主要工具 相对于传统的字符语言而言 可视化图语言具有表达直观 语义丰富 操作简便等诸多优点 如同传统字符语言的定义和实现需要形式化字符文法的支持 一样 可视化图语言的定义和实现也需要相应形式化文法的支持 由于可视化语言 中图对象之间关系的二维特性 基于一维字符串的形式语言理论显然已不能胜任对 此类语言的描述 于是 作为一维字符文法自然扩充的二维图文法 便应运而生 众所周知 针对一维字符语言建立的形式语言理论对计算机科学的发展起了重 大的作用 特别是在计算机语言和计算复杂性等方面 因此 图文法形式化研究的 重要意义也是不言而喻的 形式化图文法可以为可视化图语言提供准确的语法规范 为图语言的定义 图生成器及分析器的构造奠定必要的理论基础 在图文法研究中 任何二维对象 如图象和图形等 都被抽象为带有结点和边 的图 有向图或无向图 来表示 其中结点用来表示对象元素 边用来表示图中结 点之间的关系 与一维的字符文法的功能类似 图文法用来形式化定义和分析这类 图 但与字符文法不同的是 其重点是解决在图的推导和归约过程中可能产生悬边 的嵌入问题 这是一维文法中所没有的 再就是解决较一维文法更加复杂的图文法 表达能力 图文法的分类 和可判定性 归约过程的停机 等问题 在1 9 6 9 年第一届i j c a i 会议上p f a l t z 和r o s e n f e l d 发表了一篇题为 w 曲 g r a m m a r s 的文章 l 从而揭开了图文法研究的序幕 此后 人们在图文法理论和 应用方面进行了大量探索 在图文法形式化定义和图文法系统实现方面取得了许多 成果f 2 3 6 l 目前已有许多图文法及相关的形式化方法问世 其中多数是面向特定应 用领域的 它们通常可化归为现有的两类图文法理论中的一种 这两类分别是基于 代数的方法 7 1 和基于集合的方法 3 j 二者分别以代数理论 范畴论 和集合论为基础 来形式化定义和描述图文法的机制 证明有关的定理 以及设计归约算法等 近年 来 图文法的研究采用基于集合的方法的居多 在对文法结构作一些限制之后研究 了它们的性质 并给出了一些归约算法 o 另外 有人将基于代数的方法中的一些 河海大学硕士学位论文第一章绪论 思想运用到图文法中 但不涉及用范畴论进行严格的数学定义 取得了一些比较好 的效果 l i l2 j 在应用方面 目前图文法已被用来对多种图表进行识别和分析 p f a h z 提出了 n l 矾t s t 系统 利用图文法对神经网络图象 n e u r a ln e t v o r kp i c t u r c 进行分析 1 3 j 觚s s e n s 等人讨论了用图文法对示意图和流程图进行分析的方法 l4 j 在此基础上 f a h m y 等人又将图文法应用到音乐领域 用来对音符进行识别 1 5 d o l a d o 用图文 法来建造f o l l r e s t e r d i a g r a m 1 6 l g 6 t t l e r 用它来设计c a d 系统 1 7 进一步扩大了图文法 在这一领域内的应用 如今 随着对图文法研究的逐渐深入 它被用来研究并发系 统 8 进行数据流分析 1 9 l 和软件体系结构描述 2 0 对x m l 文档进行分析和转换 2 i 等 图文法的其它应用领域还包括图论 程序语言翻译 可视化语言 生物学 并 发系统研究 数据库描述 增量编译程序 软件开发环境等 这些方面的应用详见 2 2 2 3 近年来 随着对上下文相关图文法研究的不断深入 人们开始研究利用 它来对可视化语言进行形式化定义和语法分析 m 2 5 矧 另外图文法在模式识别领域中 也显示出良好的应用前景 目前已有人用它来进行手写体的识别 2 7 虽然图文法的研究已经取得了很大进步 但遗憾的是这些研究中的大多数都只 局限于对上下文无关文法的考虑 而上下文无关文法描述和处理具有复杂结构和关 系的二维数据的能力比较弱 从而限制了它的应用范围 正是基于这一点 为了方便描述和处理结构复杂的图 近些年来 人们开始对 上下文相关图文法进行研究 与上下文无关图文法相比 上下文相关图文法的表达 能力更强 使用它来对一些问题进行描述也更加方便 因此对上下文相关图文法的 研究具有重要意义 但是该研究领域目前还存在不少有待深入探讨的问题 其中 前面提到过的嵌入问题是首先要解决的问题 在此基础上 图文法的表达能力 成 员可判定性 以及图文法分析器的计算复杂性等也都是值得深入研究的问题 1 2 研究现状 1 9 9 7 年 r e k e r s 针对在可视化语言中的应用提出了一种上下文相关图文法l g g l a y e r e dg r a p hg r a m m a r l l 并对该文法的嵌入问题 成员判定问题和计算复杂 性问题等进行了详细分析 此后 人们对上下文相关图文法的研究逐渐多了起来 又陆续出现了r g g s g g 等上下文相关图文法 2 河海大学硕士学位论文 第一章绪论 所谓上下文相关图文法 是指产生式的两端可以是任意图的图文法 与之对应 的 上下文无关图文法则是指产生式左端必须是唯一结点的图文法 正因为上下文 相关图文法对产生式的要求较为宽松 因此它的表达能力更强 应用范围也更广泛 而相应的计算复杂性也更高 所谓嵌入问题 简单的说就是当用一个子图替换掉主图中的一个子图之后 如 何将替换入的子图嵌入到主图当中构成一个完整的图 在处理这一问题时 目前的 上下文相关图文法大多采取的是不变型的嵌入方法 即在产生式两端分别定义了一 组图元 一般是结点 并在它们之间建立起一一对应关系 当对主图中满足条件的 子图进行替换时 只要把每个图元的连接关系转移到其对应图元上即可 而除去这 些图元之外 图柄的其它部分则不允许和余图直接相连 在l g g 中 这些对应图元实际上是刻画上下文的结点与边 即l g g 将所有的 上下文结点和边同时引入到了产生式规则的左右两端 从而解决了嵌入问题 在解 决成员判定问题时 l g g 采用了一种对图结点与边的标号进行分层的方法 基于这 种层次关系定义了两图之间的 小于 关系 并要求产生式的左端小于右端 从而 保证了文法的可判定性 在此基础上 l g g 给出了一个详细的归约算法 l g g 的 语法形式较为直观 易于理解 但这种将所有上下文结点和边都写进产生式中的做 法 会增加产生式的长度和数量 也不易于语法分析过程中图的匹配 虽然使用通 配符可以减少产生式的数量 但在某些情况下通配符的数量也可能会是很多的 正 是这些原因导致了l g g 文法的归约算法复杂度很高 难以在实际问题中得到应用 同时 l g g 所采用的分层机制和引入的通配符让其显得更加复杂 不易掌握 为了解决l g g 中面临的问题 z h a n g 等人在l g g 的基础上提出了r g g 文法 r g g 继承了l g g 的许多思想 但对图的结构进行了改变 并提出了一个复杂度较 低的归约算法 i g 文法对其所描述的图的结构进行了重新定义 将图中的结点定 义成了双层结构 同时为了解决嵌入问题 r g g 中引入了一种称为 标记 的机制 所谓标记 实际上是赋给顶点的一个数值 r g g 正是通过具有相同标记的顶点之间 的对应关系解决了嵌入问题 在成员判定问题上 r g g 采用了和l g g 类似的对图 的顶点和边进行分层的方法 此外 在附加了一个 选择无关 条件的情况下 r g g 构造了一个具有多项式时间复杂度的语法分析算法 这让r g g 比l g g 易于在实际 问题中得到应用 但是 r g g 中图的双层结构和标记机制刁i 够直观 在利用这一文 河海大学硕士学位论文第一章绪论 法对图进行变换时 需要先将一般意义下的图转换成r g g 定义下的图 这一转换 过程中包含了如何设置双层结点以及如何将连到该结点上的边分配到各个小结点上 等问题 给实际应用带来一定程度的困难 而且选择无关条件在许多实际应用背景 下也常常难以满足 总之 现有的上下文相关图文法形式化方法都存在这样或那样的不足 这些缺 陷不可避免地影响了图文法的实际应用 因此 如何构建一个直观 简洁且表达能 力强的图文法形式化框架 并为其设计高效的文法分析算法等 都是有待深入研究 的问题 1 3 论文内容 本文针对现有上下文相关图文法的缺点提出了一种基于边的形式化方法来定义 上下文相关图文法 称为e g g e d g e dg r a p hg r a m m a r e g g 承袭了l g g 和l g 在产生式两端分别定义一组图元 并利用这些图元建立起一种对应关系来解决嵌入 问题的思想 但这种元素仅用边 结构信息 而略去了边的一端的上下文结点 语 义信息 这一改变的出发点是为了让产生式能有效地表达抽象的上下文结构信息 而尽量少地涉及具体的上下文语义信息 另外 e g g 在保证文法是可归约的这一问 题也将对产生式所作的限制进行了改变 通过这些改变 e g g 克服了已有的几种典 型上下文相关图文法存在的一些不足 展现出了一些较好的特性 在此基础上 本文对e g g 和现有的几种上下文相关图文法的一些特性进行了 详细比较 从而展示出了e g g 的一些优点 同时 文章还给出了一个e g g 文法对 设计模式进行描述的实例 通过这个例子进一步说明了该文法的实用性 1 4 论文组织 论文共分六章 第一章绪论 主要介绍选题背景 研究现状及目前存在的问题 然后针对这些 问题引出论文的主要内容 以及论文在解决这些问题方面所作的研究 第二章图文法形式化方法 本章介绍了图文法形式化方法中的一些基本定义和 图文法研究中的关键问题 然后对现有图文法解决这些问题的途径进行了简要介绍 最后给出了一个使用图文法对图进行变换的实例 4 河海大学硕士学位论文第一章绪论 第三章基于边的上下文相关图文法e g g 主要对基于边的上下文相关图文法 进行了详细介绍 包括e g g 中的一些基本定义 性质及归约算法 第四章e g g 与已有文法的比较 主要对e g g 与其它图文法进行了比较 其中 主要是与典型上下文相关图文法l g g 和r g g 的比较 通过比较可以看出该文法的 一些优点 第五章e g g 在设计模式中的应用 给出了一个基于边的上下文相关图文法的 应用实例 用其对设计模式的演化进行描述 第六章总结与展望 对本文进行了总结 并对今后工作进行了展望 河海大学硕士学位论文第二章图文法形式化方法 第二章图文法形式化方法 2 1 图文法的相关定义 图文法是用来定义图语言和对图进行语法分析的形式化工具 图文法中的概念 多源于图重写系统 所谓图重写 是指根据图重写规则对一个图进行变换而得到另 一个图的过程 下面首先给出图重写中的一些常用定义 定义2 1g 巧互么么最力称作是标号集z 厶上的一个图 其中 是图的 结点集 通常它由终结点集玢和非终结点集朊两部分组成 z 是图g 的边集 痧 专z 和詹 z 专厶两个函数给出了图口中每个结点和边的标号 z 寸 和 f 斗 两个函数给出了图g 中每条边的端点 起点和终点 需要指出的是 定义l 描述的是一个结点带有标号 边既有标号也有方向的图 在不同的应用领域中 图重写系统对于结点有无标号 边有无标号和属性以及有向 或无向等约定会有所不同 定义2 2 图重写式是形如g l g 的一个规则 其中g l 和 是两个图 规则指出如 何对一个给定图进行重写 即找到和g l 同构的子图时 就可以用和 同构的图对其进 行替换 定义2 3 主图 h o s tg r a p h 是使用图重写式来对其进行重写的图 记为矿嘁 另外 g 中和 同构的一个子图记为g l 0 s t 在图的重写过程中 它可以被和g 同构 的图所替换 在某些重写方式下 g i h o s t 除了要和g l 同构 边也需要满足某些约束条件 定义2 4g h o s t 中去除蜀h 0 5 t 的所有结点和边以及有一个端点落在g l i l o s t 上的边之后 所得到的图称作余图 r e s i d u a lg r a p h 记为g 噶i d i l a l 定义2 5 g p 是和 同构 用来替换主图中的g l 胁的图 图重写式是对主图进行重写的基本依据 但要完成主图的重写仅有图重写式是 不够的 还必须要有相应的规则来对g o s t 如何嵌入到g 噶i d m l 中进行说明 这一规则称 为嵌入规则 它和图重写式是进行图重写所必需的 在某些图重写系统中 图重写 规则除了这两者之外 还包含了应用条件 属性转移函数等 但这些并不是图重写 所必需的 另外 在对图进行重写时 存在两种不同的重写方式 顺序重写和并行重写 8 6 河海大学硕士学位论文第二章图文法形式化方法 前者每一步只在主图中寻找一个 并进行替换 后者则在每一步重写时都将主 图分成几部分分别进行重写 图重写可以完成图的变换 但它对图如何牛成以及图结构的分析并不深究 与 之相比 图文法则着重研究图的生成 推导 和图结构的分析 归约 使图的结构 更加明显地呈现出来 图文法继承了图重写中的一些定义 但在另一些定义上图文 法有更多的限制 下面是图文法中的几个新的定义 定义2 6 一个产生式p 是在相同标号集上的一对图 通常用 l r 或者l r 表 示 其中l 和r 分别称为产生式的左端和右端 定义2 7 一个图文法g g 是一个三元组 a p e 其中a 是文法的初始图 p 是 一组产生式 e 是文法的嵌入规则 这个定义指出 图文法比图重写多了一个初始图 初始图是图文法对图进行变 换的起点 文法中的所有图都是通过对初始图进行变换得到的 另外 还与图重写 不同的是 图重写规则的使用是立足于单向的图变换 而图文法产生式的使用则是 兼顾双向的图生成和图识别 用图文法 既可以在主图中寻找和产生式左端同构且 满足替换条件的子图 用和产生式右端同构的图对其进行替换 也可以寻找和产生 式右端同构且满足替换条件的子图 用和产生式左端同构的图对其进行替换 这两 个过程中 我们都把可替换的子图称为图柄 r e d e x 前一过程称为推导 用它可以 从初始图出发产生出一个图的集合 此集合称作是图文法所产生的语言 后一过程 称为归约 用它可以判断一个图是否属于某个给定图文法产生的语言 在不严格区 分推导和归约时 把它们统称为图的变换 在对图进行变换的方式上 图文法一般都是采用的顺序方式 即每一步只寻找 主图的一个图柄进行替换 在这种方式下 如果图g 可以通过一步变换得到图口 记作口j 口 如果图g 可以通过至少零步变换得到图g 记作口j 事仃 由此 我 们可以定义图文法产生的语言 定义2 8 假设g g 八p e 是一个图文法 l g g 彳j 幸g 八g 中不含非终结点 称作是该图文法产生的语言 2 2 图文法研究的关键问题 如前所述 在图文法研究中 嵌入问题是首先要解决的问题 在此基础上 图 7 河海大学硕士学位论文第二章图文法形式化方法 文法的表达能力 成员可判定性 以及图文法分析器的计算复杂性等也都是值得深 入研究的问题 总体来看 嵌入问题的解决 文法类型的划分和成员问题的判定是 图文法中最关键的三个问题 其中嵌入问题是字符文法中所没有的 后两个问题则 由于图的复杂结构而变得较字符文法更加复杂 所谓嵌入问题 是指图柄被替换之时 替换图柄的部分如何嵌入到余图之中 这是文法从一维到二维所产生的新问题 在一维文法中 字符是以线性次序排列的 当运用产生式对字符串进行替换后 只要将替换字符串置于被替换字符串原来的位 置 就可以得到一个新的线性排列的字符串 因而不存在嵌入问题 而文法从一维 扩展到二维 语素间由线性排列关系变成了空间上的邻接关系 在进行图变换时 替换部分如何嵌入到余图之中必须要有详细的说明 以免形成悬边 所谓悬边 是 指替换之前连接图柄与余图的边 这些边的一个端点在替换时随图柄从主图中删除 而又不知在嵌入的图中哪是新端点 为此 文法中必须给出确定新端点的方法 即 嵌入规则 在一些图文法形式框架中 嵌入问题也被称作悬边问题 在嵌入方法上 目前存在两种不同的描述方式 集合的方法和代数的方法 前 者以集合论为理论基础 借助一些表达式来说明嵌入方法 这些表达式给出了替换 部分需要和余图建立连接的结点 以及确定和这些结点相连的余图中结点所需要的 信息 8 这些信息一般包括结点的标号 边的方向和标号 以及经过的路径等 代 数方法则是用映射等一些数学概念来描述嵌入方法r 刀 从具体的嵌入方法来看 目前已有的嵌入方法主要有下面列出的几类 8 其中 前几类都是采用集合的方法来描述的 最后一类最早出现在基于代数的方法的图文 法中 采用代数方法进行描述 现在在一些图文法中借用了这种嵌入方法的思想但 并不进行严格的数学描述 1 无限制型 这是采用集合的方法描述中最简单的一类 对表达式没有任何 限制 2 方向和标号保留型 替换之后连接替换部分和余图的边都是根据替换前连 接图柄和余图的边建立的 并且要求边的方向和标号保持不变 3 深度l 型 要求替换之后余图中和替换部分的结点相邻的结点必须是在替 换之前和图柄中的结点相邻的结点 4 简单型 必须同时满足上述 2 和 3 的条件 河海大学硕士学位论文 第二章图文法形式化方法 5 基本型 简单型 并且嵌入方法与余图中结点的标号无关 6 类似型 基本型 并且嵌入方法与替换前连接图柄和余图的边的方向和标 号无关 7 不变型 产生式两端分别定义了一组图元 一般是结点 它们之间存在 一一对应关系 当对图柄进行替换时 只要把每个图元的连接关系转移到其对应图 元上即可 而除去这些图元之外 图柄的其它部分是不允许和余图直接相连的 不同的图文法可能有不同的表达能力 图文法的表达能力一方面与文法采用的 嵌入方法相关 另一方面还与文法对产生式形式的约束相关 图文法对产生式形式 的分类与字符文法类似 但更复杂一些 主要包括以下几类 捌 1 无限制的产生式 对产生式的形式没有任何限制 2 单调的产生式 产生式左端的结点数小于或等于产生式右端的结点数 3 上下文相关的产生式 产生式左端的一部分是产生式右端的一个子图 4 上下文无关的产生式 产生式左端只有一个结点 且为非终结点 5 线型产生式 受限的上下文无关的产生式 产生式右端至多只含有一个非 终结点 6 正则产生式 受限的上下文无关产生式 产生式右端要么全由终结点组成 要么最多有一个非终结点 并且其余的终结点都有一条边连结并指向这个非终结点 与字符文法的分类不同 图文法的分类不仅取决于产生式形式而且还取决于嵌 入方法 在两者之一确定的情况下 我们可以得到图文法之间表达能力的关系 比 如 当产生式形式固定为上下文相关的时候 不同嵌入方法得到的图文法表达能力 存在以下关系 2 9 不变型互类似型量基本型 简单型 深度l 型 方向和标号保留 型g 无限制型 而在嵌入方法固定为无限制型的情况下 不同产生式形式的图文法 表达能力之间存在如下关系 2 9 j 正则型 线型c 上下文无关型 上下文相关型 单调 型c 无限制型 成员判定问题涉及两个层面的考虑 一方面 图文法的形式框架要保证归约的 过程能在有限步完成 并给出肯定或否定的判定结果 也就是说 给定任意一个图 能够在有限时间内判断出此图是否属于给定文法产生的语言 这一点要通过定义适 当的图文法形式予以保证 另一方面 仅保证停机还不够 还要求归约算法的复杂 性不能太高 要能满足实际应用的要求 这方面是有许多值得深入研究的课题 9 河海大学硕士学位论文第二章图文法形式化方法 2 3 现有图文法解决关键问题的一些途径 如前所述 一个图文法的表达能力由它的产生式类型和嵌入方法共同决定 在 依据产生式形式对图文法进行分类所得到的图文法类型中 上下文相关图文法和上 下文无关图文法由于能在表达能力和产生式形式之间取得较好的平衡 因此在实际 问题中的应用较为广泛 从它们和几类嵌入方法的关系来看 在采用前几类嵌入方 法时 这两类图文法的表达能力是类似的 此时只需要研究形式更为简单的上下文 无关图文法即可 而在采用不变型的嵌入方法时 上下文无关图文法的表达能力较 之上下文相关图文法就弱了很多 因此这类嵌入方法往往应用于上下文相关图文法 在图文法发展的早期阶段 人们研究较多的是上下文无关图文法 在此过程中 人们提出了多种上下文无关图文法的形式框架 如n l c n o d el a b e lc o n t r o l l e d 0 n c e n e i g h b o u r h 0 0 d c o n t r o l l e d e m b e d d i n g 3 i h r g h p e r e d g er e p l a c e m e n t g r a m m a r 3 2 r g r e l a t i o n a lg r a m m a r 3 3 a m g a t t r i b u t e dm u l t i s e tg r a m m a r 3 4 p l g p i c t u r el a y o u tg r 锄m 岫 3 4 等 如前所述 上下文无关图文法的产生式左端是唯一的非终结点 这意味着在图 的推导过程中 需要寻找的图柄也始终是一个唯一结点的形式 在上下文无关图文 法中 大多是采用集合的方式来描述其嵌入方法的 其中连接说明 2 c o i l l l e c t i o n 访s t r u c t i o n 是最典型的一种形式 它的作用就相当于前面提到的表达式 这一方式 将在2 4 节的图文法实例中详细介绍 上下文无关图文法在采用的嵌入方法足够复杂的情况下 它们的表达能力能够 等同于上下文相关图文法 但是 在一些应用领域中 存在难以用上下文无关图文 法产生式直观描述的问题 比如在e r 图中 经常会遇到如图2 1 所示的图的变换 这是用上下文无关图文法无法直观地描述的 而用上下文相关图文法则可以直观地 描述这一形式的变换 另外 随着图文法研究的逐渐深入和其应用范围的不断扩大 人们发现上下文无关图文法在描述和处理一些具有复杂结构和关系的二维数据时不 够方便 于是 对上下文相关图文法的研究逐渐发展起来 匿翌匿圈 圃 圈 囵 圃囵 团重翻伍亘亟 卜 臣薹圈 2 囵一恒蔓多圈 一团 图2 1 一个e r 图转换实例 l o 河海大学硕士学位论文第二章图文法形式化方法 1 9 9 7 年 r e k e r s 针对在可视化语言中的应用提出了一种上下文相关分层图文 法l g g l a y e r e dg f 叩hg r 觚u n a r l i 此后 又陆续出现了r g g s g g 等上下文 相关图文法 如前所述 上下文相关图文法大多采用的是不变型的嵌入方法 即在产生式的 左右两端定义了一组一一对应的图元 文法通过这些图元的对应关系来完成替换部 分在余图的嵌入 具体来说 就是在使用产生式对主图的图柄进行替换之后 只要 将余图上和图柄中的某个图元有连接关系的结点连接到替换部分的对应图元上就可 以了 在此过程中不会出现悬边 而这些对应图元之外 余图和图柄之间没有其它 的连接关系 在l g g 中 产生式两端的对应图元实际上是同一个结点 也就是说 在利用 产生式进行替换时 它们并没有发生变化 l g g 文法将这些结点称作上下文结点 在产生式中进行了明确标注 如图2 1 所示即位一个l g g 产生式 其中的灰色结点 就是上下文结点 r g g 文法则对其所描述的图的结构进行了重新定义 将图中的结 点定义成了双层结构 并将内部的小结点叫做顶点 同时为了解决嵌入问题 r g g 中引入了一种称为 标记 的机制 所谓标记 实际上是赋给图中某些顶点的一个 数值 r g g 中带有标记的顶点就相当于前面提到的对应图元 r g g 正是通过具有 相同标记的顶点之间的对应关系解决了嵌入问题 如图2 2 所示即为一个r g g 下的 结点 图2 3 就是一个i 沁g 产生式 图2 2r g g 结点结构 图2 3 一个r g g 产生式 l g g 和r g g 文法的出现大大促进了上下文相关图文法的发展 但它们还都存 河海大学硕士学位论文第二章图文法形式化方法 在一些明显的缺点 其中之一就是为了保证文法的可判定性 对结点和边的标号进 行了分层 这很不利于文法的应用 为了简化l g g 和r g g 的分层方法 z c n g 等人 对r g g 进行改进 得到了r g g 文 法 6 r g g 摈弃了l g g 和r g g 对结点进行分 层的思想 按照传统分类方式将结点分为终结点和非终结点 并基于此定义了图的 大小 进而通过 产生式左边尺寸要小于或等于右边 的条件保证了文法的可判定 性 这一条件还使得图的结构更加直观和便于使用 此外 r g g 给出了一个不依 赖s e l e c t i o n 舶e 条件的归约算法 从而拓展了规约算法使用范围 但不可避免的是 该算法的复杂度与s f p a 相比又大大提高 之后 k o n g 等人在r g g 的基础上将空间信息加入到文法中来提高文法的表达 能力 得到了s g g 5 s g g 在定义中融合了对象间的抽象关系和空间关系 并在文 法的分析中成功地使用空间关系信息降低了搜索图柄的复杂度 2 4 一个简单的图文法实例 为了更直观地展现图文法的基本框架及关键问题 这里给出一个简单的图文法 实例 e d n c e 文法 n c e 是一种典型的上下文无关图文法 它所采用的嵌入方法属 于2 2 节所提到的深度l 型 在具体做法上 它为文法建立了一组连接说明 c o 曲e c t i o ni i l s t m c t i o n 来实现替换部分在余图中的嵌入 这种文法可以定义无向 图或有向图 定义有向图的通常称为e d n c e 文法 一个e d n c e 文法可以形式化描述为一个六元组 r q p s 其中 是结点的 标号集 是终结结点的标号集 r 是边的标号集 q r 是终结边的标号集 p 是图文法的产生式集合 s z 一 是图文法的初始图 产生式p 的形式是x 专 d c 其中x 一 d 为产生式的右端 c 是连接说明 c 的形式是 p p q d 其中 p p q i x 是d 中的一个结点 d 伽 o u t 若d 0 u t 那么在用和产生式右 端d 同构的图对主图中标号为x 的非终结点 记作v 进行替换时 如果主图中原来 从v 出发经过一条标号为p 的边可以到达某结点 且该结点标号为p 那么替换后 要从替换图中的x 结点引一条标号为q 的边指向该结点 若d i n 则边的方向相反 这一描述是针对图的生成过程的 在对图进行归约时可以等价地得到嵌入方法 下面是一个e d n c e 文法的例子 利用它进行推导可以得到所有的二叉树 其 中每个结点到其孩子结点有边相连 每个叶子结点有一条边指向根结点 图2 4 是 河海大学硕士学位论文 第二章图文法形式化方法 文法的产生式 其中p 1 的连接说明为空 p 2 的连接说明为 拌 幸产 乙i n 群 r r 1 o u t 拌 r r x 2 o u t p 3 的连接说明为 幸 乙i 1 1 撑 扩 z o u t 连接说明中的拌和 代表没 有标号的结点和边 图2 5 是由它推导出一棵二叉树的过程 吖 哆黔 r 1 8 口 x 音7茜 xi i l 1 1 2 3 x 口 图2 4 一组e d n c e 产生式 r 冀 r 一 盱 s 口 墙7 舀x 0 肖 苦 x 一冀弋 r 一 r j i 一f 孑 秀夕一 爹 j 岛 b f 知一分 图2 5 二叉树推导过程 在解决成员判定问题时 现有的归约算法针对的是满足合流 c o n n u e n c e 条件 的n c e 文法 所谓合流 是指对一个图文法来说 当归约过程中同时出现多个图 柄时 无论先选取哪个进行归约最终得到的结果图都是相同的 若文法满足这一条 件 只要找到一个图柄 就可以对其进行替换 并且不需要回溯 这样一来 算法 的复杂度比较低 但对合流条件的依赖使得这类方法的适用范围受到一些限制 2 5 本章小结 本章首先介绍了图文法形式化方法中的基本定义和图文法研究中的一些关键问 题 然后对针对这些关键问题对现有的几种图文法进行了简要介绍 其中丰要是针 对上下文无关图文法和上下文相关图文法对图文法解决嵌入问题的方法进行了说 圉 两 卣 x 河海大学硕士学位论文第二章图文法形式化方法 明 最后 2 4 节给出了一个简单的图文法实例 借以对图文法研究中的一些问题进 行了较为直观的描述 1 4 河海大学硕士学位论文第三章基于边的上下文相关图文法e g g 第三章基于边的上下文相关图文法e g g 如前所述 嵌入问题是图文法研究中的一个基本问题 在本文的第二章 对l g g 和r g g 解决嵌入问题的方法进行了简单介绍 这两种文法都利用图中一些元素的 对应关系解决了嵌入问题 但还都存在一些不足之处 l g g 将所有的上下文结点都 拉入了产生式中 这就使得产生式的结构比较复杂 另外由于在面临不同的上下文 结点时要使用不同的产生式才能进行表达 因此如果为每一种上下文结点都单独定 义一条产生式的话 会导致产生式的数量很大 l g g 引入的通配符可在一定程度上 解决这一问题 但在很多情况下要实现原有产生式所表达的语义 所需要使用的通 配符数量也可能是很大的 这并不能从根本上解决这一问题 同时 l g g 所给出的 归约算法的复杂性很高 在实际问题中很难加以应用 r g g 由于定义的是双层结点 的结构 因此看起来不直观 更重要的是 在利用这一文法对图进行变换时 需要 先将一般意义下的图转换成r g g 定义下的图 这一转换过程中包含了如何设置双 层结点以及如何将连到该结点上的边分配到各个小结点上等问题 本文给出了一种基于边的形式化方法来定义上下文相关图文法 称为 e g g e d g e dg r a p hg r a m m a r 提出e g g 形式化框架的出发点之一是让产生式能有 效地表达抽象的上下文结构信息 而尽量少地涉及具体的上下文语义信息 我们认 为这样定义的文法抽象程度高 简单且直观 也有利于进一步对图文法自动生成的 研究 e g g 承袭了l g g 和r g g 在产生式两端定义一些图的元素 并利用这些元素 建立对应关系来解决嵌入问题的思想 但这种元素仅用边 结构信息 而略去了边 的一端的上下文结点 语义信息 从检索文献可知 之前也有人在图文法中借用边 来处理问题 如h r g 超边替代图文法 和s t a m r a m m a r 中有一些类似的工作 但 这两种文法并不是通过两组边之间的对应关系来解决图文法面临的嵌入问题 而且 它们的产生式左端本质上都是以一个非终结点为中心的 因而不是典型的上下文相 关图文法 3 1 基本定义 在对图文法进行形式化定义时 通常是利用集合来进行描述的 l g g 和r g g 均是如此 本文亦采用这一方法进行相关的定义 本文提出的上下文相关图文法是 河海大学硕士学位论文 第三章基于边的上下文相关图文法e g g 使用边作为产生式两端的对应元素 指出上下文信息 为了实现这一目的 在构建 文法时引入了悬边的概念 所谓悬边 是指有一端没有落到任何结点上的边 本文 中 把所讨论的图从一般意义下的图拓广到可能带有悬边的图 称为悬边图 与此 对应的 在e g g 中对图文法的一些定义作了改变 下面给出e g g 中相关的形式化 定义 定义3 1g 巧历 毋力是标号集l 上的一个图 其中 v 是图的结点集 由 终结点集玢和非终结点集助两部分组成 e 是图的边集 z 是图中结点的标 号函数 指出了每个结点的标号 j z 一矿和 z 一 分别指明了图中每一条边的 起点和终点 为了方便起见 我们用符号g v g e g 1 g s 和g t 分别表示一个图的各个 部分 下面的定义都采用这一记法 定义3 1 给出的是一个一般意义下的图 不含 悬边 图中的结点带有标号 边带有方向而不带标号 下面定义的是可以含有悬边 的图 定义3 2 夕 以层必 砖 砌称作是标号集l 上的一个悬边图 其中 v 是悬 边图的结点集 由终结点集乃和非终结点集厢两部分组成 z 是悬边图的边集 它包含悬边集z 和非悬边集z z 又分为起点悬边集盈和终点悬边集五两部分 两 者分别代表起点没有指定的边和终点没有指定的边 m 是悬边图中悬边的标记集 矿j z 是结点的标号函数 j z 动 和 z 动啼 是边的起点函数和终 点函数 所 z h 是一个双射 称作悬边图的标记函数 在定义3 2 中 悬边集z 允许是空集 此时与之相关的标记集m 也就是空集 而标记函数m 不再有意义 因此 定义3 1 描述的图可以看作是定义3 2 描述的悬 边图的一个特例 下文中 在不特别指明时 所提到的图都是不带悬边的图 悬边 图则包含了带悬边的和不带悬边的图 同样 在不特别指出是悬边时 提到的边都 指的是非悬边 对于一个悬边图 把除掉它的悬边集之后得到的图称作是它的核图 记作砌 把和悬边有关联的结点称作悬边图的关联结点 对于每个关联结点 把以它为起点的悬边的个数称作它的关联出度 记为锄 力 即 1 6 河海大学硕士学位论文第三章基于边的上下文相关图文法e g g 如 力 i 后p 否 而 以l 把以它为终点的悬边的个数称作它的关联入度 记为 姒功 即姒力 陋f 人而 以i o 另外为了描述方便 把和悬边没有关联的结 点的关联出度和关联入度都记为0 在上面定义的基础上 下面给出基于边的图文 法中产生式的定义 定义3 3 由两个悬边图弘和9 通过符号 连接而得到的形如纺 跏的一个 结构是一个产生式 其中q 车跏肜 q 和跏分别称作产生式的左端和右端 特别的 产生式的左端也可以是文法的初始图 此时产生式的右端必须是不带悬边 的图 如图3 1 所示即为一组产生式 1 i 匝五卜 叶 互互 圃 2 l 五 白 l 吖互五叵 土一 哑k 善二 丑l 4 j 五 一生一 一上一 丘i i i 丑 一 面三 l 一上 巫口 三一 l 至卫二卜 k 5 圆 豳 6 上 皿三一 j 匝k 耄 徊三一 图3 1 一组e g g 产生式 产生式的作用是用来对图进行变换 这种变换需要基于一定的条件 其中同构 是最基本的条件之一 同构的意思是说在两个图的结点和边之间存在一一对应关系 对应结点具有相同的标号 并且对应边的起点和端点恰好是对应结点 其形式化定 义如下 定义3 4 对两个图 形互z 以力和口 矿 f i 来说 如果存在