（计算机软件与理论专业论文）基于线图的自下向上句法分析器的实现.pdf

中文摘要 摘要 现代汉语句法分析是面向信息处理的现代汉语研究的热点之一。句法分析在 自然语言处理( n l p ) 中，起着承上启下的作用。它即是词法分析的后续，同时 它也是语义分析的基础。因此在汉字输入、语音听写机、文语转换( r r t s ) 、搜索 引擎、信息抽取( i e ) 、信息安全和机器翻译( m t ) 那样的、有能力处理大规模 真实文本的实用化系统中起着重要的作用。 本文所阐述的系统是文语转换系统( 1 _ r s ) 中文本分析的一部分它和词法 分析一起作为文语转换系统的第一步工作。句法分析以分词的结果作为输入， 经过句法分析器之后，生成句法树，作为下一步工作韵律标注的指导。最 终改善机器语音合成的自然度。 本文在简要说明了汉语句法分析的研究背景之后，重点介绍了基于规则的句 法分析研究以及基于统计的句法分析研究状况，同时对汉语句法分析的困难进 行了综述；深入研究了句法分析理论之后，在线图算法( c h a n g o r i t h m ) 的基 础上提出了基于逆概率的自底向上算法的改进。并给出了相关算法。 系统中包括规则加载模块，句子加载模块，句法树的显示模块，规则训练模 块。规则形式采用限制的上下文无关文法，同时采用开放式原则，即只要满足 限制的上下文无关文法形式的规则都可以引入规则可以从文件或数据库中加 载，所以它不但可以应用于r i s 系统中，同时可以作为其他关于句法分析的实 用系统的组成部分。 关键字：文语转换、句法分析、上下文无关文法、线图算法、逆概率 a b s 仃a c t abstra ct c h i n e s es ”t a c t i ca i l a l y s i sh a sb e e nb e c o m i n go n eo ft h eh o n e s tt 叩i c so f c h i n el a n g i i a g cs d e n c er 髓e a r c h c h i n e s es y n t a d i ca l l a l y s i sp l a y sa ni m p o n a n t r o i ei nn a t u r el a n g u a g cp r o c e s s ni sb o t ht i l ee n d0 fw o r da u t o - s e g m e n t a t i o na n dt h e s t a n0 fs e m a n t i c 锄a i y s i s s o ，i l h 勰b e e na p p l i e dp o p u l a r l yf o rc l i i 鹏s ei n p u t ，t t s ， s e a r c he n 西n e s ，m ，m rs y s t e m 锄d 咖 i n t h i s p a p c r ，t h cs y s t 啪i s a p a n o f 下r s i ta n d s e m a n t j c a n a l y s i sa r c t h es t a n r r s 1 l l l ei n p u t0 ft h i ss y s t e mi st h c 俐m l to fm ew o r di ns e n t c n c ct h a tb u i l tb y a u t o s e g m e n t a t i o i i 船dt h eo u t p u to fi ti st h es ”t a c t i c 仃c e s i tc a np m v i d ct h eh e l p f o r t h cn e x tj o b ，w h i c hi sr h y t h ml a b e l a sar e s u l t ，“c a l ic o n d u c et oi m p m v i n gt h e s p e e c hn a t u m l l y a f t e ri i l t r o d u c c dt h et h e o f ) ，o fs ”t a c t i ca n a l y s i s ，t l l i st h c s i sd e p i c t st h es y n t a c t i c a n a l y s i s r c s e a r c h t h e o r yw h i c hi n d u d e s t h e椰l e - b 勰c dm e t h o d柚dt h e s t a t i s t i c a l - b 勰e dm e t h o di nd e t a i l a tt h es a m et i m e ，id e s 口i b et h ed i f f j c u l t yi n c h i n e s ep a 略i n g a tl 够t ，id e s i 印an e wa r i t h m e t i cw h i c hb a sl h ec h a na r i t h m c t i c 1 i o uc a n6 n dt h ed e t a i l e dc o d ci l lt h i st h e s i s t h i ss y s t e mi n c l u d e sm l el o a d i n gm o d u l e ，s e m e n c ci o a d i n gm o d u l e s y n t a c t i c t r e e sd i s p l a y i n gm o d u l e ，a n dr i i l et r a i n i n gm o d u l e t 1 l em l e sf o 帅i st h el i m i t e dc f g 1 1 l es y s t e mi sd e s i g n e dw j t ho p e n e dp f i n c i p l e ，t h a ti s ，y o uc 趾e x t c n dt h cs y s t e mb y t r a i n i n gi t sm l e s o ，y o u n 丘n dt l l a tt h en l l ew h i c hw j i lb el o a d e dc a nc o m e 劬m d a t a b a o rl i l e s o ，i tc o u l db eu s e dn o to n l yi n 丁r sb u ta l i no t h c rs y s t e m sw h i c h b e l o n gt os ) ，i l t a c t i ca n a l y s i s k e y w o r d t t s s y n t a c t i ca j i a i y s i s p c f gc h a r ta l g o r i t h m i n v e r s ep r o b a b i l i t y 专用术语注释表 专用术语注释表 标记代码标记名称及其实例 n p名词性短语，如：政府办公室，多彩的生活 v p动词性短语，如：出去一下，行动起来 a p 形容词性短语，如：很高兴的，特别详细的 d p副词性短语，如：很多很多，非常漂亮 p p介词短语，如：从昨天，除了小说以外 b y区别词性短语，如：公共，广大 t p时间词性短语，如：昨天早上，本世纪末 s p处所词性短语，如：田地里，书本中 m c p数词准短语，如：五万六千 m p数量短语，如：七八种，五六样 a d j形容词，如：冰凉、宏伟、热情 d 副词，如：曾经、正在、将要 d e的词。如：这是我做完的、我是班长叫来的 n o u n名词，如：计算机、桌子、家 u t l助词，如：一样、也罢、而已 v t动词，如：升迁、吃、看见 m 数词，如：五、千、万 p 介词，如：自从、关于、根据 q量词，如：种、本、辆 f代词，如：我们、大家、这里 s处所词，如：家里、塞外、山脚 t时间词，如：晚上、昨天、平安夜 w标点符号，如：。，! n l 内容目录 图目录 图1 1 语音合成系统组成部分 图1 2 语言的层次划分及相互关系 图2 1 不同的句法分析树 图2 2 四种文法的关系 图2 3 上下文无关文法对应的两种句法树 图2 4 依存结构的依存树 图2 5 句法分析结果表现形式 图2 6 词性不同时对应的句法树 图3 1c h a r t 算法的核心流程描述 图3 2c h a r t 算法举例分析结果 图3 3s 髀帅r 句法分析器 图3 4 层叠有限状态自动机 图4 1 系统流程图 图5 1 句法分析器界面 图5 2 点击句法分析按钮系统错误提示 心 = 2 侈 勰 n 配 ” ” 缸 内容目录 图5 3 树型显示结果 图5 4 规则训练模块界面 图5 5 规则加载模块流程图 图5 6 句法分析模块流程图 图5 7 规则训练模块流程图 图5 8 。孩子喜欢狗”的句法树 i 姐 铊 铊 如 船 内容目录 表目录 表2 1 乔姆斯基体系语法层次 表3 1c h a r t 算法示例所用词典和规则 表3 2c h a r t 算法中产生的活跃边和非活跃边 表3 3 产生式及其出现的概率 表4 1 产生式表p a r s e r d b 表4 2 词性标签表l a b e i 表4 3 词表w o r d 3 5 表5 1p l c 算法、c h a r t 算法和p c f g 算法的区别 v m 加 筋 凹 如 鲐 弱 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：黏每东 ”年了月5j 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签学位论文作者签 复遍香， 名：名： 解密时年月日 间： 各密级的最长保密年限及书写格式规定如下： 内部5 年( 最跃5 年。可少于6 年) 秘密1 0 年( 最匠1 0 年，可少于1 0 年) 机密2 0 年( 最蚝2 0 年，可少于z 0 年) 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：爱络毒 ”6 年宁月5 f 日 第二章题目 1 1 1 论文背景介绍 第一章概述 第一节论文背景知识介绍 句法分析作为1 1 s 文语转换技术的一部分，有着重要的意义。它在r r s 系 统中起着至关重要的作用。好的句法分析器可以很大程度改善语音合成的自然 度。同时，它还是自然语言理解的重要组成部分。下面就t t s 文语转换技术和 自然语言理解做一简单的介绍。 1 l 1 1t t s 文语转换技术简介 从第一台计算机诞生到现在，计算机已渗透到了人类生活的方方面面。在这 种形势下，如何让计算机能够智能化地与人通讯，使人机交互更加自然方便成 为了现代计算机科学的一个重要研究课题。其中语音技术作为研究的热点之一， 受到了国内外一些科研单位高度重视，并对汉语语音技术进行了大量的研究， 取得了丰富的成果。 语音合成技术是实现人机语音通信，建立一个有听和讲能力的口语系统所 必需的关键技术。使电脑具有象人一样的昕、说的能力，是现代社会的迫切需 要，有着广泛的市场前景。 文语转换( t c x tt os p e e c h ，下r s ) 技术，是语音合成技术的延伸，是基于声 音合成技术的一种声音产生技术。它可用于语音合成和音乐合成。它能把计算 机内的文本转换成连续自然的语声流。若采用这种方法输出语音，应预先建立 语音参数数据库、发音规则库等。需要输出语音时，系统按需求先合成语音单 元，再按语音学规则或语言学规则，连接成自然的语流。它涉及到声学、语言 学、统计分析、人工智能、数字信号处理等多个学科的技术。要解决的主要问 题就是如何将文字信息转化为可听的声音信息，也就是说让电脑可以像人一样 开口说话【。 为了合成出高质量的语音，除了依赖于各种规则，包括语义学规则、词汇规 则、语音学规则外，还必须对文字的内容有很好的理解，这将涉及自然语言理 第二章题目 解的问题。从这一点讲，文语转换系统实际上也可看作一个人工智能系统。文 语转换过程是先将文字序列转换成音韵序列，再由语音合成器生成语音波形。 其中第一步涉及语言学处理，例如分词、字音转换等，以及一整套有效的韵律 控制规则；第二步需要先进的语音合成技术，能按要求实时合成出高质量的语 音流 2 l 。 当前，语音合成的研究已经进行很多年，它是对书面语进行处理，将其转换 为流利的，可理解的语音信号。同时并不只是由正文到语音信号的简单映射， 它还包括了对书面语言的理解，以及对语音的韵律处理。一般认为，语音合成 系统包括三个主要的组成部份：文本分析模块、韵律生成模块和声学模块。其 结构如下图所示。其中文本分析包括词法分析、句法分析、语法分析和语义分 析。它属于自然语言处理( n l p ) 的一部分。 蝴 图1 1 语音合成系统组成部分 1 1 1 2 自然语言理解 提到文本分析，就不能不提到自然语言的理解。 自然语言理解一直是人工智能学科内引人注目而又困难重重的一个核心研 究课题。由于它的难度很大，至今仍未能达到很高的水平。随着社会的日益信 息化，人们越来越强烈地希望用自然语言同计算机交流。从宏观上看，自然语 言理解是指机器能够执行人类所期望的某些语言功能。这些功能包括：( 1 ) 回答 有关提问；( 2 ) 提取材料摘要；( 3 ) 不同词语叙述；( 4 ) 不同语言翻译。因此自然语 言理解系统可以用作专家系统、知识工程、情报检索、办公室自动化的自然语 言人机接口，有很大的实用价值。 要研究自然语言理解，首先必须对自然语言的构成有个基本认识。 语言虽然表示成一连串的文字符号或者一串声音流，但其内部事实上是一 2 兰三兰望旦 个层次化的结构，从语言的构成中就可以清楚地看到这种层次性。因此，语言 的分析和理解过程也应当是一个层次化的过程。许多现代语言学家把这一过程 分为5 个层次：语音分析、词法分析、句法分析和语义分析和语用分析。虽然 这种层次之间并非是完全隔离的，但是这种层次化的划分的确有助于更好地体 现语言本身的构成【朋 语音分析 语音分析则是根据音位规则，从语音流中区分出一个个独立的音素，再 根据音位形态规则找出一个个音节及其对应的词素或词。 词法分析 。 其主要目的是找出词汇的各个词素，按逻辑习惯切分成独立的单词，从 中获得语言学信息。 句法分析 是对句子和短语的结构进行分析。方法很多，有短语结构语法、格语法、 扩充转移网络、功能语法等等分析的目的就是找出词、短语等的相互关系 以及各自在句子中的作用等，并以一种层次结构来加以表达。这种层次结构 可为反映从属关系，直接成分关系，也可是语法功能关系。 语义分析 通过分析找出词义、结构意义及其结合意义，从而确定语言所表达的真 正含义或概念。在语言自动理解中，语义愈来愈成为一个重要的研究内容。 语用分析 就是研究语言所在的外界环境对语言使用所产生的影响。它描述语言的 环境知识、语言与语言使用者在某个给定语言环境中的关系。 图1 2 语言的层次划分及相互关系 第二章题目 从词法层次、句法层次、语义层次到语用层次，层层相扣，纠缠在一起，组 成一个复杂庞大的系统，任何人只能在某个层次上深入研究。目前在研究词法 分析、句法分析、语义分析、语境分析等技术中，分别取得了一定的成果，但 还远不能达到实用的要求。 1 1 2 问题提出 语音合成系统首先处理的是文字，这也是整个工作的第一步。文本分析的主 要功能是使计算机能认识待分析的文字，首先需要划分这些文字，然后根据划 分的结果分析文字的组成方式，即是什么结构的句子。然后根据词典划分和句 子的分析来标注韵律，通过这种方式告诉计算机这些文字的发音规则。另外， 还要让计算机知道，在文本中，哪些是词，哪些是短语或句子，发音时应该到 哪里停顿及停顿多长时间等。所以整个文本分析可以分为三个主要阶段： 1 整理纠错阶段。将输入的文本扫描一遍，查找其中的拼写错误。 2 词法分析阶段。分析文本中词边界，并根据切分的结果标注词性，待下 一步分析。 3 句法分析阶段。根据分词的结果配合词性，对句子的结构作深入的研究。 其中句法分析阶段是至关重要的阶段。根据本系统，我们要求探讨其文本的 结构，需根据结果能对下一步工作韵律的标注起到指导作用。根据句法分 析的结果可确定发音时语气的变换以及不同音的轻重方式。 由此可见，句法分析是整个t t s 系统中的重要环节。一个好的句法分析器 可很大程度上改善句子发音的自然度，使之更贴近人的发音习惯。 此外，在诸如智能拼音语句输入、手写和语音自动识别输入；文章的校对； 简体和繁体中文的自动转换；信息检索和信息摘录；文本分类和自动文摘：语 音合成；自然语言的理解和自动翻译；自然语言接口等领域，都需要对包含词 法分析，句法分析，语义分析等相关内容作进一步研究。其中句法分析是关键 步骤之一。因而，汉语句法分析是中文信息处理的基础，在中文信息处理系统 中具有广泛的应用前景。 4 第二章题目 第二节论文内容组织 本文所阐述的理论、技术是文语转换系统( r r s ) 中文本分析的一部分。它 和词法分析一起作为文语转换系统的第一步工作。句法分析以分词的结果作为 输入，经过句法分析器之后，生产句法树，作为下一步工作韵律标注的指 导。最终改善机器语音合成自然度。 结合系统本文共分5 部分： 第一部分主要对论文背景知识作简要介绍。包括r r s 文语转换技术和自然 语言理解两方面的概述，同时论述了系统所用到的相关技术。 第二部分主要介绍句法分析理论的基础知识，包括它的任务和作用。研究表 明，上下文无关文法是研究句法分析的最佳方法此外，本部分还探讨了句法 分析结果的表现形式。最后，本文论述了汉语句法分析所面临的困难 第三部分分析了句法分析的分析方法和分析策略。综合国内外的研究状况， 总结了最新的主流算法。 第四部分则根据前述的理论，结合了自己的分析，在最流行的线图( c h a n ) 算法的基础上提出了改进意见，在此基础上设计并实现了句法分析器系统。系 统中包括规则加载模块，句子加载模块，句法树的显示模块，规则训练模块等。 第五部分是对系统的总结与展望，根据系统中存在的不足，提出进一步改进 方案。 第三节系统所用技术 1 3 1 饼n e t 甜是一种最新的、面向对象的编程语言。它使得程序员可以快速地编写各种 基于m i c r o s o f t n e t 平台的应用程序，m i c r o s o f t n e t 提供了一系列的工具和服 务来最大程度地开发利用计算与通讯领域。 正是由于饼面向对象的卓越设计，使它成为构建各类组件的理想之选 无论是高级的商业对象还是系统级的应用程序。使用简单的雠语言结构，这些 组件可以方便地转化为x m l 网络服务，从而使它们可以由任何语言在任何操作 系统上通过l l l t e m c t 进行调用。 最重要的是，珊使得c + + 程序员可以高效的开发程序，而绝不损失c c + + 第二章题目 原有的强大的功能。因为这种继承关系，睇与c 肛+ + 具有极大的相似性，熟悉 类似语言的开发者可以很快的转向c 拱。 新兴的网络经济迫使商务企业必须更加迅速的应对竞争的威胁。开发者必须 不断缩短开发周期，不断推出应用程序的新版本，而不仅仅是开发一个“标志性” 的版本。甜在设计时就考虑了这些问题。它使开发者用更少的代码做更多的事， 同时也不易出错。 1 3 2s q ls e e r s q l s e n ，c r 2 咖是一项全面完整的数据库与分析产品。从借助浏览器实现的 数据库查询功能到内容丰富的扩展标记语言( x m l ) 支持特性均可有力地证明， s q ls e r v 盯2 0 0 0 成为全面支持w 曲功能的数据库解决方案。与此同时，s o l s e n ，c r2 0 0 0 还在可伸缩性与可靠性方面保持着多项基准测试纪录，而这两方面 特性又都是企业数据库系统在激烈市场竞争中克敌致胜的关键所在。无论以应 用程序开发速度还是以事务处理运行速度来衡量，s q ls e r v e r2 0 0 0 都堪称最为 快捷的数据库系统，而这恰恰是该产品成为灵活企业首选解决方案的原因所在。 区别于f o x p r o 、a c c e s s 小型数据库，s q ls e n ，e r 是一个功能完备的数据 库管理系统。它包括支持开发的引擎、标准的s q l 语言、扩展的特性( 如复制、 o l a p 、分析) 等功能。而像存储过程、触发器等特性，也是大型数据库才拥有 的。 6 第二章题目 第二章句法分析理论研究 第一节句法分析的概述 1 句法分析的任务与作用 因为人是自然语言的主体，人们可根据长期生活经验和知识分析一个句子 的确切含意，而计算机并不具备这种能力。自然语言( 特别是汉语) 的语句内 部的结构往往是要通过知识的运用来“解读”的，而计算机只能靠编程语言来 进行“语法分析”。例如，“开汽车的老板”和“开老板的汽车”都是“v p + n p ” 的样式。然而我们很自然地把它们分别解读为“( 开汽车的) 老板”和“开( 老 板的) 汽车”。这是因为我们有“老板可以开汽车”而“汽车不能开老板”的 常识。计算机如果没有这种常识和运用这些常识的本领，那么它就没有办法正 确分辨语句内部的结构1 4 l 。 句法分析系统的主要任务是识别一个语言的句子和确定输入句子的结构，即 确认句子是否合乎给定的语法而为合法的句子，识别句子各个部分能否生成句 法树。例如给定文法g 和该文法描述的语言l ： ( 1 ) 给定一个字符串s ，判定s 是否属于k ( 2 ) 给定一个字符串s ，如果s 属于l ，给出s 对应的树结构； 例如分析这句话：小王和小李的妹妹结婚了。按照词法分析我们可以得出如 下分析，小王n p 和，c 小李n p 的d e 妹妹n p 结婚v p 了u t l 口从这个分析的结 果中我们可以得出不同的语法树。 图2 1 不同的句法分析树 7 b 第二章题目 计算机可得出这两种句法分析树，所以对计算机而言，这两种分析结果都算 正确。然而，一般的情况下，我们会把b 分析结果视为正确结果。这是根据常 识妹妹一般不会是小王和小李两个人的，所以小王和( 小李的) 妹妹结婚更符 合逻辑。 由此可见，只有词法分析是不够的，我们必须建立起句法分析器，对句子的 结构作深入了解，这样我们才能初步“理解”句子的含意，为下一步工作做好 基础。当然，句法分析不是万能的，对于某些句法分析中面临的歧义问题只能 依靠语义分析解决。 2 句法分析与语义分析和语境分析的联系与区别： 语法分析有狭义和广义之分。狭义的语法分析就是指句法分析，广义的语法 分析则包括句法分析、语义分析和语境分析。人们大致上采用两种方式使用自 然语言进行交流。一种是“意合法”，发话者的几个关键的词，就可以让听话 者捕捉到有关的信息，这当然绝对依赖于当时的环境。另一种是“结构法”， 即人们正常说的、写的句子虽然表面上看来只是音节或词的线性序列，但实际 上是有一定的结构的。在这两种方式中“结构法”是基本的方式【5 1 0 目前计算机能处理的也就是这样的有合法结构的句子，其中心任务就是通过 句法分析、语义分析和语境分析得到句子结构的形式化的机内表示。句法分析、 语义分析与语境分析，这三者之间的关系应当是以句法分析为主，辅以必要的 语义分析和语境分析，以消除歧义结构。句法分析固然解决不了关于理解的全 部问题，但是反映客观世界的语义系统即使能建立起来，也会十分庞杂，语境 分析更是没有边界，很难形式化，因而也不宜对语义分析与语境分析期望过高， 正确的策略应是将三者有机地结合起来。汉语的形态虽然不发达，但反映汉语 结构规律的形式系统还是存在的，只是研究得还不充分，对自然语言处理还有 很多潜力可以发挥。因而这也是当前研究的重点之一【乳。 3 句法分析的层次 如果按语言理解的深度划分，可以分为深层结构( d e e ps t m c t u r c ) 和表层或 浅层结构( s u r f a c cs t n l c i u r c ) 两个层次： 浅层句法分析：能够正确提取语句的内部结构，但是并不理解其中所有语块 或者词汇的含义。 第二章题目 深层句法分析：不仅能够正确理解语句的“字面上的”含义，而且还能理解 “言外之意”或者“隐含着的意义”。 人们一般使用的是句子的浅层表示，它的表现形式非常丰富，数量庞大，难 于统计，但是若干个表层表示不一样的句子的深层表示可能是相同的。如： 1 1 他已经解决了这个问题。 2 ) 这个问题他已经解决了 3 ) 他已经把这个问题解决了。 。 4 ) 这个问题已经被他解决了。 针对这种情况，尤其是自然语言的互译，就需要在分析句子的表层表示的基 础上探究其深层含意。 第二节句法理论基础 句法分析一般都依赖于某种语法体系。语法体系的形式丰富多彩，各种语 法形式都有各自的特点。其中形式语法理论是热点之一，形式语法理论的目的 是试图用精确的数学模型( 形式语言) 来刻画自然语言。形式语法体系也同样 多种多样。形式语法可分为以下凡类【6 l ： 乔姆斯基语法体系 一转换生成语法 标准理论 一管辖与约束理论 ， 最简方案 使用简单范畴的语法体系 一索引语法 树粘接语法 一定子句语法 使用复杂范畴( 特征结构) 的语法体系 一功能合一语法 一词汇功能语法 一中心词驱动的短语结构语法 不使用范畴的语法体系 依存语法 9 第二章题目 一范畴语法 词汇语法 攒语法 工程性语法体系 p a t r u - g 语言 一分层约束语法 不同的语法体系产生的句法结构形式不尽相同。 形式语言虽然在描述人工语言方面取得了很大的成功( 如程序设计语言) ， 但在描述自然语言方面还很不成功。这里简要介绍几种典型的语法形式。 2 2 1 乔姆斯基语法体系 美国著名语言学家乔姆斯基( n c h o m s k y ) 首先提出了短语结构语法p s g ( p h m s c s t m c t l l f c g n m m a r ) ，将自然语言分成四种不同的形式文法：正则语法、 上下文无关语法、上下文有关语法、无约束短语结构语法，统称为乔姆斯基体 系。这四种语法所产生的语言依据包含关系构成了严格的层次体系。一个p s g 形式定义如下： 一个p s g 是一个四元组： v ，n ，s ，p ，其中v 是终结符的集合( 字母表) ， n 是非终结符的集合，s n 是开始符号，p 是产生式规则集。它所接受的语言 就是由开始符号s 通过p 中的规则所可以导出的所有终结符串的集合。 表2 1 乔姆斯基体系语法层次 匾两一 f i 磊谳磊磊磊一 匾匾磊赢 r “r 一 ，i 2 型i 上下文无关语法 医； 磊葚一 ll l 识别自动机产生式规则形式 l 图灵机 a b 钱性有界自动机a a b - a 佃 l 下推自动机队 丫 j 蒜赫一墨蠹”二= 1 0 第二章题目 乔姆斯基体系中的四种语法分别对应着四种文法，即o 型、l 型、2 型和3 型文法。0 型强于1 型，l 型强于2 型，2 型强于3 型，这几类文法的差别在 于对产生式施加不同的限制。 乔姆斯基四种形式语法所导出的语言具有以下关系川： 图2 2 四种文法的关系 乔姆斯基语法层次体系中的四种语法及相应文法形式具体说明如下： 设g = ( v ，t ，p ，s ) 为文法。 正规语法( 对应3 型文法) ： 若产生式p 中每个生成式都有如下形式：a a 或a - a b ，其中a 是终 结符，a ，b 属于非终结符，则g 称为3 型文法。所对应的语法是正规语法。 正规语法的语法生成句子时是严格地顺着一个方向扩展的，形式最严 格，生成的语言最简单，分析起来也最容易( 时间复杂度是线性的) ，可 以用有限状态自动机进行分析虽然具有逻辑上的简洁性，但它不足以担 负起描写自然语言的重任，其分析能力也是最弱的。 上下文无关语法( 对应2 型文法) ： 若产生式p 中每个生成式都有如下形式：a a ，其中a 是终结符和非 终结符的集合，a 属于非终结符，则g 称为2 型文法。 上下文无关语法是计算语言学的重要研究对象，它虽然不足以刻画自然语 言的复杂性，但由于其形式简单，分析效率高( 多项式时间复杂度) ，同时又 是可递归的，可以构造有效的句法分析器来进行句子的分析，实际上是句法分 析中使用最广泛的一种语言形式。，利用上下文无关文法可以判断有歧义结构 的句子。如：五个公司的职工。我们可以理解成五个( 公司的职工) ，也可以 理解成( 五个公司的) 职工。分别对应着不同的语法树。此外，对于具有相似 1 1 第二章题目 结构的语法的形式，如：“打开仓库的大门”和“看守仓库的工人”都是 v _ p + n p + d e + n p 的形式。但句法结构分别是“( 打开( 仓库的大门) ) ”和“( ( 看 守仓库) 的工人) ”。 ，委飞想 图2 3 上下文无关文法对应的两种句法树 我们后面将要介绍的句法分析算法大多也都是基于上下文无关语法的。 上下文敏感语法( 对应i 型文法) ： 若产生式p 中每个生成式a b 都满足i a i | b i ，则g 称为1 型文法。 上下文敏感语法的能力比上下文无关文法能力要强，它能担负描写自然语 言的重任。它可以分析出上下文无关文法无能为力的问题。但它还不能很 好的被形式化，上下文敏感语法将使语法定义变得更为复杂，且一般不能 高效地进行分析。而且分析过程复杂，其分析的时间复杂度是非多项式的 ( n p 问题) 。所以目前这种文法的应用还不是很成熟，不能应用于实际中。 不受限短语结构语法( 对应0 型文法) ： 若产生式p 中每个生成式。不加任何限制，则g 称为o 型文法。 由于o 型文法的产生时几乎没有什么限制，它的生成能力太强，会生成 难以数计的不合格句子。不受限短语结构语法也是能力最强的语法。它甚 至不是一个可判定性问题( 实际上是一个半可判定问题) ，这种语法形式在 实际中无法得到应用。 乔姆斯基的形式语法理论是一个不断演变、不断发展的过程。在1 9 5 7 年， 乔姆斯基提出了“转换生成语法理论( t g ) ”，1 9 7 0 年，发展成为“标准理论”， 在1 9 8 1 年，乔姆斯基又提出了“管辖一约束理论( g b ) ”，1 9 9 2 年，提出了“最 简方案( m p ) ”i ”。 乔姆斯基体系有着非常旺盛的生命力，它可以解释很多其他理论很难解释的 语言现象。但是乔姆斯基语法理论越来越复杂，使得形式化的工作变得非常困 难。现在有许多非乔姆斯基体系出现。 第二章题目 2 2 2 其他语法体系 广义短语结构语法g p s g ( g e n e r a i i z e dp h r a s es t r u c t u r eg r a m m a r ) g p s p ( 广义短语结构语法) 是g g a f d e r ，g p u l l u m 等于二十世纪七十年代在 短语结构语法基础上提出的一种语法体系，它不同于c h o m s k y 的“转换生成语 法”采用的表层结构和深层结构框架，g p s g 主张句子结构只有一个表层结构， 在短语结构语法的基础上采用特征值来描述语法，同时克服了传统p s g 对许多 语法现象无法解释的问题【9 】o g p s g 由三个部分构成，句法规则部分、特征制约部分和语义解释部分。广 义短语结构语法采用复杂特征来表述句法，所有的句法都由 构 成。g p s g 通过短语结构规则来描写句子的树形结构，同时又通过特征系统对树 形结构进行制约，使其在整体上正确反映语言现实。这一树形结构又通过特定 的语义解释系统而得到句子的模型论语义解释。 在g p s g 中，规则并不直接生成树型结构，每条规则生成一个“候选”的 局部树型结构，通过一系列严格的合格性条件的检验后，合格的加入到整个句 子的树型结构中，不合格的即被丢弃。 g p s g 广义短语结构语法较之p s g 和转换生成理论，有其许多优点，一方 面它仅在同一个表层结构上通过特征值的处理弥补了p s g 的许多局限，没有采 用转换生成理论两个结构的分析方法，另一方面它采用了在规则集上多种比较 严格的合法性约束，保证了生成的结构尽可能地符合文法。但是g p s g 的规则 表示比较复杂，有不少语法现象仍然不能描述。 中心词驱动的短语结构语法( h p s g ) 1 9 8 4 年，o 盯lp o l l 姐d 提出了中心词驱动的短语结构语法( h e a d d r i v 蛐p h r 猫c s t r u c t u g r a m m a f ，简称h p s g 。也称核驱动的短语结构语法。h p s g 是在广义 的短语结构语法的基础上提出的，它基本上继承了广义短语结构语法的原则， 并根据自然语言处理的实践进行了重要改进。这种新的语法理论的突出特点， 就是特别强调中心语在语法分析中的作用，使整个语法系统由中心语来驱动。 其基本特点有：1 ) 强调中心词在短语结构规则中的作用。包括：中心语一 一补足语规则，中心语一指示语规则，中心语一修饰语规则。2 ) 产生式规 则+ 特征结构+ 合一运算。3 ) 基于中心词的属性特征传递。4 ) 以同样的形 第二章题目 式化方式表达句法知识和语义知识。 词汇功能语法( k x i c a lf u n d i o n a lg r 锄m a r ) 词汇功能语法是j b f c s n 锄和r m 1 ( a p l 瓶于1 9 8 2 年提出的。其基本特 点有；依托短语结构语法已有的树结构，通过自底向上( b o t t o m u p ) 层层传递 的方式把词汇所负载的各种信息传播、汇集到上层节点中去，最终形成关于一 个句子的完整的结构信息和功能信息描述。其分析结果包括两种： c 结构( n s t i t u e ms t r u c t i i r c ) ：对句子的句法结构树描述；它是语言的外部 结构，它表示单词的形式，形态，单词之间的组成方式，短语结构的组成方式等。 f - 结构( f i l n c t i 蚰a ls t r u d u ) ：对句中各成分的功能描述；f 结构是语言的 内部结构，它表示谓词与各个论元的句法功能，代词的照应关系等。 c 结构和f 结构是两个具有不同形式的独立体系，词汇功能文法把它们明确 的区别开来，一部分一部分地分别进行描述，然后又把它们合在一起，使人们对语 言的结构获得一个总体的印象。 其最主要的特点是：基于表层结构，力图直接由观察到的语言现象来进行描 述和解释，而不依赖于抽象的深层结构。这样，在进行句法分析时只需要单词中所 具有的各种具体的语言信息，而不作抽象的论述。 h p s g 和l f g 属于非乔姆斯基阵营的语法理论中比较有生命力的两种。他 们与乔姆斯基语法理论的本质差别在于没有转换规则( 乔姆斯基后期的理论中 又称为d 一移动) ，没有浅层结构和深层结构的区别。 从计算机实现的角度看。这两种理论都采用了特征结构这种形式来表达复 杂的语言学知识并采用合一算法进行规则的推导。与乔姆斯基的语法理论不同， 这两种语法理论都又很好的可实现性。因此这两种理论的发展一直和计算机的 结合非常紧密【”。 依存语法( d e p e n d e n c yg r a m m a r ) 依存语法是法国著名语言学家特思尼耶尔( t c s n i e r c ) 于1 9 5 9 年在其所著的 结构语法基础中提出。依存语法也是一种使用非常广泛的语法形式。依存 语法的核心思想是：参加组成一个结构的成分之间是不平等的，一些成分依附 于另一些成分，每一个成分只能依附于至多一个成分。依附与被依附的关系就 决定了结构的性质。与短语结构语法( p s g ) 的最大不同在于，依存语法的句法 1 4 第二章题目 结构表示形式不是一棵句法层次结构的句法树，而是一棵依存树：依存树上的 所有结点都是句子中的词，没有非终结符结点。 例如句子“勇敢的我愿意尝试新鲜事物”的依存结构如下图所示： 图2 4 依存结构的依存树 动词是句子的中心，动词支配其他成分，它本身不受支配；直接受动词支 配的有名词词组和副词词组；名词词组是动词的行动元( a c t a n t ) 应该说，依存语法描述的是句子中词与词之间的直接关系，而且这种关系 是有方向的。实际的应用系统中，一般都会给依存关系加上句法或语义的标记m 。 链语法( l n kg 阳m m a r ) 链语法由美国c m u 计算机学院的d 明i e ls l e a t o r 和美国c o l u m b i au n i v e 略i t y 的d a v yt c m p c r l e y 共同提出。一部链语法( u l l l 【g m m m a r ) 就是一个单词的集合， 其中的每个单词后面记录着各自的链接要求( l i n k i n gf c q u i r c m e n t ) 。这些链接要求 可以通过一系列链接子表达式( f o 咖u l ao f c o 蚰e c t o r s ) 指定 链语法的一个显著特点是分析的结果不是一棵句法树，而是一个有向图。 它不是建立在树结构的基础上，而是将语言知识完全落实到词汇基础上，通过 词语的链接( 踟k ) 属性，来对句子进行分析。 链语法的另一个特点是没有句法规则，只有几条简单的原则，用于规定句 法成分之问互相结合的方式。链语法的语法知识都存放在词典中。 跟其他形式语法系统相比，链语法是持强词汇主义观点的形式语法系统。 它并不强调语言成分的层次组合关系，而是从词汇的局部着眼，力图揭示：一个 句子中任意两个词之间是否有联系，以及是什么联系1 9 j 。 范畴语法( c a t e g o r i a i g r a m m a r ) 1 5 第二章题目 范畴语法的特点在于，把句法分析的过程变成了一种类似分数乘法中进行 的“约分”运算。把语言中的各种成分对应为某种“类型”“范畴”，把语言 结构的构造过程对应为“类型”“范畴”之间的演算过程。 在范畴语法中，也没有规则，只有几条简单的原则，规定范畴之间如何进 行“约分”，所有的语法信息都表现在词典中。核心思想是把语言中的各种成 分对应为“量纲”或“类型”，把语言结构的构成过程同相应成分的对应量纲或类型 的演算过程。 功能合一语法( f u n c t f o n a fu n 墒c a t j o ng r a m m a r ) 功能合一语法是m k a y 于1 9 7 9 年提出的，他最早把合一运算引入语法理 论。其基本特点有：a ) 最大的特点就是词条定义，句法规则、语义信息以及句 子的结构功能表示全部都可以用复杂特征集来表示，复杂特征集在f u g 中被称 作功能描述( f d ) 。b ) 弱化线性序结构关系；c ) 强调功能结构；d ) 对所有语言单 位统一采用f d 形式描述；e ) 适合于生成( g e n e r a t i o n ) 它试图以单一的形式结构模式来描述特征组合、功能分配、词条和组成成 分的顺序等，达到对句子的完全功能描述。它既可用于分析，又可用于生成，因 此它具有双向性。 定子句语法( d e f i n i t ec l a u s eg r a m m a r ) 定子旬语法是对c f o 的一种简单扩充。定子旬语法可以直接转换成p m l o g 语句。现在大部分p m l o g 语言都实现了对定子旬语法的支持，在p r o i o g 语言的 支持下，定予句语法可以直接实现语言的识别、生成、分析，而不需要另外编 程。 此外还有树邻接语法( 1 r e ea d j o i n i n gg r a m m a r ) 和词语法( w j r dg r a m m 盯) ， 这里就不一一叙述。 2 2 3 句法分析结果的表现形式 句法分析结果的表现形式多种多样，其中最为直观的要算句法树，即树型 表示法形式了。此外还存在链型图表示法，系联图表示法，句型图表示法，魔 方图表示法，层次结构图表示法和起点、终点数表示法。见下图： 1 6 第= 章题目 链型圈 系联图 魔方图 树型图 层次 结构图 翼煮婺匪五三互j 互三亘j 蔓玉兰王互因 图2 5 句法分析结果表现形式 第三节汉语句法分析所面临的困难 应该说，当前的计算机的“智力”比人类差得远，要教会这样一个“傻瓜” 理解自然语言，既需要提出一个合理的可以实现的实现目标，又需要有一套特 别设计理论和方法。计算语言学家为此进行了艰苦的探索，建立了各种模型。 国外印欧语系在此方面的研究起步比较早，成果也相对丰富许多。 对于汉语来说，这个任务则更为艰巨。在一些应用领域( 如信息库的检索界 面、机器翻译系统) 中，从事汉语信息处理的研究者几乎都是借用国外已有的语 法理论( 如上下文无关语法，扩充转移网络，语义语法，格语法，语义网络，广 义短语结构语法，词汇功能语法，依存语法等等1 解释一部分汉语的语法现象， 应该说真正立足于汉语语言事实的形式化的语法理论框架至今尚未建立起来， 众多的学者都在期望着这个课题的突破性进展【1 0 】。 相对于印欧语系，汉语在语法上有一些独自的特点，仅仅从形式上看，这种 特点主要体现在以下几个方面： 语序 1 7 第二章题目 不同于英语和其他语种