（计算机应用技术专业论文）基于概率上下文无关语法的句法分析研究与实现.pdf

摘要 本文论述了基于概率的上下文无关语法的句法分析的原理及实现过程。本文 首先回顾了自然语言的发展历史和应用范围，同时介绍了句法分析在自然语言中 的重要的地位和本文的主要工作。 然后介绍了句法分析的常用的分析方法，并对本文的基于概率的上下文无关 语法的句法分析器所采用线图分析法作了重点介绍，分析了这种方法的原理以及 优点。 本文的句法分析器是基于概率上下文无关语法的，这种方法是统计分析模 型中比较成功的一种模式。在本文的第三章详细介绍了p c f g 的排除句子歧义的 原理，并用具体实例加以阐述。基于概率的分析，当然最重要的就是概率的提取 问题，在本文的第四章给出了提取概率的详细算法及实例，解决了基于概率上下 文无关语法的三个重要问题。即采用向内向外算法，在给定一部概率上下文无关 语法的前提下，计算句子的概率：采用v i t e r b i 算法，在给定一部概率上下文无 关语法以及句子前提下，找出最为可能的分析树。采用向内一向外算法，为语法 规则选择概率，使得训练句子的概率最大。 在对真实的句子进行句法分析的时候会遇到很多问题。本文在第五章，针对 一些具体问题提出了一些解决方案，取得了一定的成效。主要有以下几个方面。 1 ) 根据汉语，既缺乏形态变化，又缺乏作为句法标志的黏着成分的外在特征， 本文采用了短语本位的思想。 2 ) 针对汉语的具体特点，在本文中设计了预处理系统，系统利用特征词在 对句子进行综合分析之前预测句子的句法结构，换句话说，预处理实际上是部分 句法分析，它起着导引综合分析的作用，避免了不必要的计算。 3 ) 在本文中针对基于统计句法分析中数据稀疏问题，采取了数据平滑技术， 使该问题得以缓解。 4 ) 在汉语中特定的句法范畴与特定词类之间的共现关系，在本文的句法分析 器中，句法分析的歧义消解引入这类共现信息。即本文提到的制约法消歧，也就 是利用句法、语义等制约条件排除不能满足制约条件的结构，从而达到消歧目的。 在第六章列出了本旬法分析器实验结果，并与其它几种统计句法分析模型进 行了比较分析。 最后，本文分析了本系统的存在的缺陷及一些改进措施。 关键词：线图句法分析统计p c f g a b s t r a c t t h i sd i s s e r t a t i o nd i s c u s s e st h et h e o r ya n dr e a l i z a t i o no ft h ep r o b a b i l i s t i cc o n t e x t f r e eg r a m m a r - b a s e d s y n t a c t i cp a r s e r a tf i r s t ，t h i sp a p e rl o o k sb a c kt h eh i s t o r yo ft h e n a t u r a ll a n g u a g ep r o c e s s i n ga n di t s a p p l i c a t i o nf i e l d sa n di l l u s t r a t e st h a ts y n t a c t i c p a r s e rh a sv e r yi m p o r t a n c ep o s i t i o no ft h es y n t a xp a r s e ri nt h en a t u r a ll a n g u a g e p r o c e s s i n g a tt h es a m et i m e ，t h e m a i nw o r ki nt h i sd i s s e r t a t i o ni sg i v e n i nt h es e c o n ds e c t i o n ，i tm a i n l yd i s c u s s e st h es y n t a c t i cp a r s i n gi nc o m m o nu s e t h ec h a r tp a r s e rh a sal o to f a d v a n t a g e s ，s ot h i sm e t h o di su s e di no u rs y n t a c t i cp a r s e r a n di sd e t a i l e dp r e s e n t e d o u rs y n t a c t i cp a r s e ri sb a s e do np r o b a b i l i s t i cc o n t e x tf r e eg r a m m a r , f o rt h i s m o d ei st h eb e t t e ro n ei nt h es y n t a c t i cp a t t e r n i nt h et h i r ds e c t i o nw ed i s c u s st h e m e t h o dh o wt or e m o v et h ea m b i g u i t yw i t hp c f ga n du s ea ne x a m p l et o e x p l a i n c l e a r l y t h em o s ti m p o r t a n tt h i n gi nt h ep c f g i st h a th o wt og a i nt h ep r o b a b i l i t yi n o r d e rt os o l v et h i sp r o b l e m ，t h i sd i s s e r t a t i o np o i n to u tt r e ea l g o r i t h m si nt h ef o u r t h s e c t i o na n dh o wt os o l v et h et h r e eb a s i l i c ap r o b l e m si np c f gf o re x a m p l e ，w h e na p r o b a b i l i s t i cc o n t e x tf r e eg r a m m a ra n dt h es e n t e n c ea r eg i v e n ，w eu s et h ei n s i d e a l g o r i t h mt op i c k u pt h ep r o b a b i l i t yo f t h er u l e ；w h e nw ew a n tt o a c q u i r et h eb e s t s y n t a c t i cp a r s i n gt r e e ，w eg a i nt h ep r o b a b i l i t yb yu s i n g v i t e r b ia l g o r i t h m ；a tl a s t ，w e u s ci n s i d e - o u t s i d ea l g o r i t h mt oc h o o s et h ep r o b a b i l i t yo ft h er u l ef o rt h eg r a m m a ri n o r d e rt og a i nt h em a x i m a l p r o b a b i l i t yo f t h e t r a i n e ds e n t e n c e s w e m a y m e e tal o to f p r o b l e m s ，w h e nw e d e a lw i t ht h er e a ls e n t e n c e sw i t ht h e s y n t a c t i cp a r s i n g t h e r ep o i n t so u tm a n y r e s o l v em e t h o d sa i m i n ga ts o m e p a r t i c u l a r d i f f i c u l t i e si nt h ef i f t hs e c t i o n t h em a i n a s p e c t sa r e a sf o l l o w s 1 ) c h i n e s eh a v el i a l ef o r mc h a n g e d a n dt h ef l e x i b l e n e s so ft h el a n g u a g e so r d e r , s oiu t i l i z et h ep h r a s e b a s e dm o d e t os o m ee x t e n t ，i tc a ng e to v e rd i s a d v a n t a g e si n c h i n e s e 2 ) i nm ys y n t a c t i cp a r s e r , id e s i g naf r o n tp r o c e s s i n gs y s t e mf o rt h ep a r t i c u l a r c h a r a c t e ro ft h ec h i n e s e w ec a nu t i l i z es p e c i a lw o r d si nc h i n e s et of o r e c a s tt h e s e n t e n c e 。ss t r u c t u r eb e f o r et h es y n t h e s i sp a r s i n g , t h i si st os a y , t h ef r o n tp r o c e s s i n g s y s t e ma c t u a l l y i st h ep a r t s y n t a c t i c p a r s i n g t h em a i nf u n c t i o n i st oi n d u c tt h e s y n t h e s i sp a r s i n ga n d r e d u c e sag r e a td e a lo f c a l c u l a t i o n sq u a n t i t y 3 ) iu s et h ed a t as m o o t h i n gt e c h n o l o g yt os o l v et h ed a t as p a r s ep r o b l e mi nt h e s t a t i s t i c - b a s e ds y n t a c t i cp a r s i n ga n da c h i e v es o m e i m p r o v e m e n t s 4 ) t h e r ea l w a y sh a v es p e c i a lr e l a t i o n sb e t w e e nw o r d si nc h i n e s e ，s oiu s et h i s i n f o r m a t i o nt oe l i m i n a t e a m b i g u i t y t h a t i st h em e t h o dt h a ti sc a l l e dr e s t r i c t e d d i s a m b i g u a t i o n t h i sd i s s e r t a t i o n t h ee x p e r i m e n tr e s u l t so ft h i ss y n t a c t i cp a r s e ra r el i s t e di nt h es i x t hs e c t i o na n d g i v es o m ea n a l y s e st o w a r dt h i sr e s u l t a tt h es a m et i m e ，t h e r ei sac o m p a r ea n a l y s i s w i t ht h eo t h e rs t a t i s t i c a lp a r s i n gm o d e l st h r o u g ht h ed a t ag a i n e df r o m e x p e r i m e n t a tl a s t ，t h i sd i s s e r t a t i o np o i n t so u tt h ed r a wb a c ko fo u r p r o g r a ma n ds u b m i t s s e v e r a lp o s s i b l es o l u t i o n s k e y w o r d s ：c h a r tp a r s e r , s y n t a c t i cp a r s e gs t a t i s t i c ，p c f g i i j 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：遭蟑日期：沙乒年，2 月6 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 日期：汐勺尹年2 月z 日 基于概率上下文无关语法的句法分析研究与实现 1 1 自然语言处理 i 1 1 自然语言处理概述 第一章绪论 自然语言处理( n a t u r a ll a n g u a g ep r o c e s si n g ，n l p ) ，也称自然语言理 解或计算机语言学，它是研究如何利用计算机来理解和生成自然语言。通过建 立形式化的数学模型，来分析、处理自然语言，并在计算机上用程序来实现分 析和处理的过程，从而达到以机器来模拟人的部分乃至全部语言能力的目的。 自然语言处理是根植于计算机科学、语言学和数等学多学科。因此，自然语言 处理成为一门介乎语言学、数学和计算机科学之间的边缘学科。 自然语言处理是从计算的角度来研究语言的性质；将语言作为研究对象。 所谓从计算的角度来看语言的性质，就是要求将人们对语言的结构规律的认识 以精确的、形式化的、可计算的方式呈现出来，而不是像其他语言学研究那样， 在表述语言的结构规律时一般采用非形式化的表达形式；所谓将语言作为计算 对象来研究相应的算法，是研究如何蚍机械的、规定了严格操作步骤的程序来 处理语言对象( 主要是自然语言对象，当然也可以是形式语言对象) ，包括一 个语言片断( 比如词组、句子或篇章) 中大小语言单位的识别，该语言片断的 结构和意义的分析( 自然语言理解) ，以及如何生成一个语言片断来表达确定 的意思( 自然语言生成) ，等等。 语言学上对语言有这样的层次划分：第一层次是语音和文字，即基本语 言信号的构成：第二层次是词法和句法( 合称“语法”) ，即语言基本运用单 位的构成和组合的形式规律；第三层次是语义，即语言所要表达的概念结构； 第四层次是语用，即语言与语言使用环境的相互作用。 1 1 2 自然语言处理所用技术和方法 自然语言处理的核心技术是语言分析技术，即将句子( 数量无限) 变换成 由词语( 数量可控) 及其抽象形式( 数量有限) 构成的用某种数据结构( 句法 树、复杂特征集或语义网络) 表示的内部形式( 数量有限) 。 语言分析技术可以分为基于规则与基于统计数据两大类。这两类技术 曾有过一番孰优孰劣的竞争，目前学术界已普遍认为应当综合应用这两类 基于概率上下文无关语法的句法分析研究与实现 技术。概率语法通过语料库统计给每条语言规则加上概率值，语言规则便 有了，柔雠，不再是啡此即，彼，。概率语法是有机结合这两类技术的较好理 论体系。为了完成这种统计，事先必须按照人给出的语言规则加工语料库 ( 至少要加工一部分训练语私d ，这说明统计方法也需要规则的指导两者 之间的结合和互相利用是必然的趋势。 语言分析可以划分为词法分析、句法分析、语义分析、篇章分析等步 骤。对象单元由小到大，从句子向篇章发展。实际上只有在篇章的范围内 分析，省略、指代和句子的固有歧义等问题才可能解决。 自然语言处理研究方式可分成下面四个基本过程 s 1 ：研究者以特定的方式对自然语言的规律进行抽象，以计算机能够处理 的形式来表述关于自然语言的规律得到语言知识k ； s 2 ：针对特定的语言知识表示形式，研制适合的分析和处理算法； s 3 ：根据算法编制计算机可执行的自然语言处理程序p 。这样的程序加上 语言知识，加上计算机硬件系统，共同构成一个自然语言处理系统( n l p s ) ； s 4 ：用这样一个自然语言处理系统对自然语言进行分析处理，根据反馈的 结果调整原来的设计，改进n l p s 。 1 1 3 自然语言处理的主要应用 自然语言( 书面的和语音的) 机器理解成为当今人工智能中最活跃的领域 之一。自然语言处理广泛应用于网络超容量文本数据的获取和分析：网络信息 的纯洁化和安全处理；机器入语音对话；大型数据库自然语言查询：专家系统 自然语言接口；c a d ，c a i 和o a 的人机交互系统；计算机自动书写、摘要提取、 文档自动分类和文书管理系统；大型工业操作过程的自动化语言；机器翻译和 机助翻译；模式识别( 文字和语音) 语言学再处理；话语自动翻译；文学与社 会科学的文档和语料计算机自动处理；网际互联网信息过滤、主题识别、文本 分类和文本挖掘：网上交叉语言和自然语言信息检索等。它成为了当前最热门 的研究课题之一。 表格1 - i 表示的是自然语言处理的不同层次 1 1 4 自然语言处理的发展历程 1 1 4 1 国外主要成果 国外关于自然语言理解方面的研究起步较早，一些卓有成效的语言学家、 逻辑学家和心理学家都在自然语言理解中的语法、句法及语义分析方面提出了 2 基于概率上下文无关语法的句法分析研究与实现 一系列较为系统的方法。 自然语言理解的研究从2 0 世纪5 0 年代开始到7 0 年代，可以说基本上停 留在实验和纯理论的探讨阶段。到了8 0 年代有较大的发展，大约从1 9 8 3 年开 始，国外自然语言软件进入了商品市场，标志着自然语言处理的研究进入了一 个新的阶段。2 0 世界末国际互联网语言工程产品作为一种新的产业在这个世界 上开始崛起。但是，总的说来，知识表示和知识处理问题在2 0 世纪之前都没 有在根本上有所突破。2 1 世纪将是计算语言学界大展鸿图，解决问题的全新时 代。表卜1 说明了自然语言在目前发展情况和应用。 表1 1n i p 不同层次 n l p 不同层次 研究适用人员范围 应用系统 数字图书馆、电子商务、电子政务、远程教软件企业 育、语言学习 应用技术研究 自动问答、机器翻译、信息检索、文本挖掘、 自动校对、信息提取 自然语言处理研究者 基础研究 分词、词性标注、短语切分、句法分析、语 义分析、篇章理解等 资源建设 语言学家 语料库建设、语言知识库建设 1 i 4 2 国内主要成果 通过2 0 多年的不懈努力，我国的自然语言处理的研究水平有了很大的进 步，并取得了丰硕的成果，大体可以总结如下： 1 ) 机器翻译：以冯志伟教授为代表的计算语言学学者早期在机器翻译研究方 面作了大量的工作，并总结了不少珍贵的经验和方法，为以后来的计算语 言学研究奠定了基础。 2 ) 语料库研究：清华大学的黄昌宁教授领导的计算语言实验室，主要从事基 于语料库的汉语理解。近年来，在自动分词、自动生成语法规则、自动统 计字词的使用和关联频率方面作了不少很有价值的论文。 3 ) 语篇理解研究：东北工学院的姚天顺教授和哈尔滨工业大学的王开铸教授 等在计算语言学的语篇理解方面的研究也取得了一定的成就。 4 ) 受限汉语：北京信息工程学院的周锡令教授主持的受限汉语的研究为自然 语言处理提出的一种新思路。他认为短期内计算机还很难做到真正的理解 自然语言，在继续对自然语言理解方面研究的同时，应该研究受限汉语， 基于概率上下文无关语法的句法分析研究与实现 这样可以让研究成果较快的实用化。 5 ) 知网：由董振东先生提出的一种汉语知识表示方法。知网把客观世界看作 是很多的概念构成。概念与概念之间有有各种各样关系，这些关系相互交 织就构成了个网。要表示一个客观世界，就是要确定这些概念、概念的 属性以及概念之间的关系。 6 ) 概念层次网络：由黄曾阳先生提出的一种自然语言理解的理论框架。这个 理论框架是以语义表达为基础的，它对语义的表达式概念化的、层次化、 网络化的，所以称它为概念层次网络理论。该理论把认知结构分为局部和全 局两类联想脉络，认为对联想脉络的表述是语言深层( 即语言的语义层面) 的根本问题。这一理论的提出为语义处理开辟了一条新路。 1 2 句法分析 1 l2 。1 句法分析在自然语言处理中的地位 从理论上讲，自然语言处理应该按照词、句子和篇章三个层次来展开研究。 由于其中句子处理在三个层次中具有承上启下作用，也就是说，它可以带动词 处理和篇章处理，所以，句子处理是自然语言处理过程的一个重要阶段。句子 分析过程是连接各个单词的意义来构成表示一个句子意义结构。句法分析需 要依照多方面的知识才能确定，包括所使用的语言知识，语句所涉及的领域知 识，即背景知识和惯用知识等，因此，它的难度是不言而喻的。 自然语言与人工语言的不同在于自然语言中包含着大量的歧义。自然语言 处理的过程实质上就是一个解决歧义的过程。而句法分析的过程可以解决自然 语言处理过程中存在的一部分歧义问题，比如：词性歧义、生词引起的歧义、并 列结构歧义、介词短语的附着对象歧义、代词的指代歧义、句子连词歧义等。 这样，歧义的解决无疑可以对进一步的自然语言处理提供强有利的帮助。因此 对自然语言句法分析的研究将是自然语言处理的一个核心内容。 随着信息社会的到来，人们对自然语言处理的需求日益迫切，因而对句法 分析的研究也具有重要的实际意义。对自然语言句法分析的研究将对自然语言 处理的各种问题提供帮助，它是解决自然语言理解的一个重要手段之一。 1 2 2 句法分析发展历程和现状 早期的句法分析工作始于2 0 世纪5 0 年代，1 9 5 0 年w e a v e r 设计实现的一 个以简单“查字典”为基础的机器翻译原型系统，该系统的失败使人们认识到 在机器翻译的过程中需要更高水平的知识表示方法，由此展开了对自然语言旬 基于概率上下文无关语法的句法分析研究与实现 法分析的研究。 5 0 年代末到6 0 年代初c h o m s k y 的转换语法和形式化理论为下一代的自然 语言处理提供了一种新的解决方案。如s a d s a m 利用c h o m s k y 的形式化论生成 了一个可以处理大约1 7 0 0 个词和有限的英语语法的句法分析器。但s a d s a m 存在着低效及对词汇和语法数量的限制。 6 0 年代自然语言处理的主要技术是关键词分析和模式匹配方法。比如 b a s e b a l l 系统、s i r 系统和s t u d e n t 系统中都采取了在文本中查找简单的模式 或某种正则表达式的方法。模式的特点是：对于模式中包含的现象可以较好地 处理，但一旦遇到模式中没有考虑的语言现象，则做缺省处理，缺省的效果往往 较差。因此在处理大领域的语言问题时，模式的方法难以胜任。 7 0 年代初，w o o d s 提出了转移扩张网络法( a t n ) ，增加了正则表达式的能力， 同时克服了用有限状态机表达上下文无关文法时存在的限制。然而a t n 方法严 格依赖于特定的应用领域，移植十分困难。 8 0 年代初期开始，国际计算语言学界先后出现了一些新的语法理论。其中 比较著名的有广义短语结构语法( g p s g ) 、词汇功能语法( l f g ) 、树邻接语法( t a g ) 等。 近几年来，随着语料库语言学的不断发展和标注语料库规模的不断扩大， 许多研究人员开始尝试着直接利用语料库中的标注信息进行语法分析，开创了 一条进行自动句法分析的新路。在英语方面，典型的研究工作包括： 1 ) 折r b o d 的面向数据分析( d a t ao r i e n t e dp a r s i n g ) 技术； 2 ) 模拟退火( s i m u l a t e da n n e a l i n g ) 分析方法； 3 ) d a v i dm m a g e r m a n 的概率型判定树方法； 4 ) e b r i l l 的基于转换( t r a n s f o r m a t i o n b a s e d ) 的处理等。 在汉语方面，中文信息处理在进入八十年代后，又比较大的发展，特别是 在汉字信息处理方面，而且相应的在全国成立了一些研究机构。但是，句法分 析刚刚起步，其难度将远远超过分词和词性标注。句处理不仅面临着复杂的语 音问题、句法规则的问题，更面临着复杂的语义问题、知识背景问题。 1 3 本文的主要工作 本文对基于概率的上下文无关语法的句法分析进行了分析研究。在本句法 分析器中采用了线图分析法进行句法分析。采用向内向外算法，在给定一部概 率上下文无关语法的前提下，计算句子的概率；采用v i t e r b i 算法，在给定一 部概率上下文无关语法以及句子前提下，找出最为可能的分析树。采用向内一 向外算法，为语法规则选择概率，使得训练句子的概率最大。 基于概率上下文无关语法的句法分析研究与实现 在对真实的句子进行句法分析的时候会遇到很多问题。本文针对一些具 体问题提出了一些解决方案，取得了一定的成效。主要有以下几个方面。 1 ) 根据汉语，既缺乏形态变化，又缺乏作为句法标志的黏着成分的外在特 征，本文采用了短语本位的思想。 2 ) 针对汉语的具体特点，在本文中设计了预处理系统，系统利用特征词 在对句子进行综合分析之前，预测句子的句法结构，换句话说，预处理实际 上是部分句法分析，它起着导引综合分析的作用，避免了不必要的计算。 3 ) 在本文中针对基于统计句法分析中数据稀疏问题，采取了数据平滑技 术，使该问题得以缓解。 4 ) 在汉语中特定的句法范畴与特定词类之间的共现关系，在本文的句法分 析器中，句法分析的歧义消解引入这类共现信息。即本文提到的制约法消歧， 也就是利用句法、语义等制约条件排除不能满足制约条件的结构，从而达到消 歧目的。 最后列出了本句法分析器实验结果，并进行了分析，与其它统计句法分析 模型进行了比较分析。 6 基于概率上下文无关语法的句法分析研究与实现 2 1 句法分析概述 第二章句法分析 所谓句法分析是指判断输入的单词序列能不能构成合乎语法的句子，抽取 合乎语法的句子的句法结构。也就是应用句法规则和其它知识，将该输入句子 中单词之间的线性次序，变成一个非线性的数据结构，如短语结构树或有向无 环图等。 一般来说，一个句法分析系统通常由两部分组成： 1 ) 形式语法体系 形式语法体系主要有匹配模式、扩充转移网络、树嫁接语法、基于合一运 算的语法、基于词的语法、把上述几种理论结合等等。 2 ) 分析控制机制 分析控制机制主要有：早期的模式匹配技术、基于短语结构语法分析算法 ( 包括：e a r l e y 算法，富田胜分析算法、线圈分析算法、确定性分析算法等等) 、 基于扩充转移网络的分析算法、链分析算法等等。 2 2 句法分析的主要内容与功能 2 2 1 主要内容 通常认为，句法分析的主要任务是：给定一个输入句子，以语言的语法特征 为主要知识源，生成一棵短语结构树，通过树的形式指明输入句子各部分之间 的关系。其研究的主要内容包括： 1 ) 句子中包含那些词语? 2 ) 每个词语的句法范畴是什么? 如名词、动词、形容词等等。 3 ) 句子中更大的成分是什么? 句子中包含哪些短语或词组，如名词短语、 词短语、介词短语等等。 4 ) 句子中各成分或短语怎样组合或附着而构成整个句子的句法结构? 2 2 2 主要功能 句法分析的主要功能有以下两点。 基于概率上下文无关语法的句法分析研究与实现 1 ) 确定语句是否合乎语法 确定哪些语句按句法规则是合法的，哪些语句不是。对于合乎语法的语句， 并且能为它所找到的任何一个符合语法的句子建立一种与其句法结构相应的 数据结构。 2 ) 使句法结构规则化 句法结构规则化就是将大量可能的结构映射到较小的结构集上。这样就可 以简化下一步的处理( 即语义分析) 。例如，句子中的些成分可以被省略或 “被置零”。此外，如果恰当地选择句子结构，那么在句法分析的输出中，操 作一操作数，例如动词一主语，动词一宾语，可以明显的表示出来。 2 3 句法分析的主要研究方法 目前为止，句法分析的研究大体分为两种途径：一是基于规则的处理方法， 这种方法有的以一定的形式文法系统加上“复杂特征”来表述自然语言中大小 成分的句法信息和它们的组合原则，有的试图“以概念化、层次化、网络化( 简 称h n c ) 为基础”来提供概念组合、语义表述的规则；二是基于经验的语料库统 计方法，这种方法是以各种统计数据来显示语言成分间的组合可能性。 2 3 1 基于规则的方法 基于规则的方法，是以知识为主体的理性主义( r a t i o n a l i s m ) 方法。该方 法以语言学理论为基础，强调语言学家对语言现象的认识，采用非歧义的规则 形式描述或解释歧义行为或歧义特性。 在句法分析的研究过程中，基于规则的方法曾一度是句法分析的主要方法， 从5 0 年代到8 0 年代末，出现了一些有代表性的以规则为基础的系统。 在语料库句法分析方法出现之前，句法分析的研究基本上是一种基于规则 的方法，而规则的获取是一个十分繁琐的过程，它需要大量的人工操作，完全依 赖于开发规则的知识工程师的语言知识和经验，即便是个经过训练的语言工 程师也难以写出能覆盖较多语言现象的语法规则。通常知识工程师只能通过实 验更多的句子来提高系统的性能，但这种方法不能保证系统的性能随着调试句 子增多而提高，有时句子的增加反而会对系统的性能产生负面影响。人类总结 的规则不完备、不一致，规则多了相互冲突，难以对抗复杂的语言现象，因此 基于规则的方法，很难找到一种系统的途径，提高规则开发的效率。 2 3 2 基于统计的方法 8 基于概率上下文无关语法的句法分析研究与实现 为解决基于规则的方法在知识获取方面存在的困难，8 0 年代末研究者转而 求助于机器学习的方法，出现了基于统计的句法分析方法，例如 l m a g e r m a n ，1 9 9 4 1 c o l 1i n s ，1 9 9 7 等。 基于统计的方法分为有指导的和无指导的两种。有指导的方法依靠一个手 工标注的句法分析树库做训练数据，获得句法分析的知识；无指导的方法则使 用没有经过标注的数据，进行训练。尽管无指导的方法省略了手工标注语料的 繁重劳动，但用于学习的数据本身都是没有正确结果的，无指导方法其结果自 然比有指导方法相差很多。所以无指导的方法通常用来辅助手工标注语料。 不同的语法形式，对应的句法分析算法也不尽相同。 2 4 句法分析的分析策略 1 ) 回溯与并行处理 由于词的兼类和自然语言的歧义，迫使分析器在分析一个句子时，要在多 重选择中做出判断，选择的策略有两种，一种是回溯，一种是平行处理。回溯 的策略是先从一条路经上进行下去，直到发现行不通时，再回溯到到先前的某 一点，从另一条路经上搜索，多次回溯、搜索，直到成功为止。这是深度优先 算法。并行的策略也称广度优先算法，即同时搜索所有可能的路径，最后得出 正确结果。 2 ) 确定性算法和非确定性算法 马库斯提出的确定性算法是一种典型的无回溯处理方法，其最大的特点是 在任何情况下任何结构一旦构造出来，便是摄终输出的句法结构的一部分。换 句话讲，在任何情况下只有一个确定的分析路径，即分析器只有一种选择，没 有回溯。 在分析过程中需要进行回溯或伪并行的分析算法称为非确定性算法，不需 要回溯或伪并行的算法称为确定性算法。确定性算法效率优于非确定性算法， 但自然语言极其复杂，分析过程中很难避免回溯。 3 ) 自顶向下和自底向上 句法分析的过程也可以理解为句法树的构造过程，可分为自顶向下和自底 向上分析法。所谓自顶向下分析法也就是先构造句法树的根结点，再逐步向下 扩展，直到叶结点；所谓自底向上分析法也就是先构造句法树的叶结点，再逐 步向上合并，直到根结点。 自顶向下的方法又称为基于预测的方法，也就是说，这种方法是先产生对 后面将要出现的成分的预期，然后再通过逐步吃进待分析的字符串来验证预 期。如果预期得到了证明，就说明待分析的字符串可以被分析为所预期的句法 9 基于概率上下文无关语法的句法分析研究与实现 结构。如果某一个环节上预期出了差错，那就要用另外的预期来替换( 即回溯) 。 如果所有环节上所有可能的预期都被吃进的待分析字符串所“反驳”，那就说 明待分析的字符串不可能是一个合法的句子，分析失败。自底向上的方法也叫 基于归约的方法。就是说，这种方法是先逐步吃进待分析字符串，把它们从局 部到整体层层归约为可能的成分。如果整个待分析字符串被归约为开始符号s ， 那么分析成功。如果在某个局部证明不可能有任何从这里把整个待分析字符串 归约为句子的方案，那么就需要回溯。 在本文的句法分析中采用了线图分析法，这种方法具有直观和灵活的特 点，线图分析算法的时间复杂性对于自然语言句法分析来说效率比较高。 2 5 线图分析法 2 5 1 概述 在自然语言处理中较为常用的是线图( c h a r t ) 分析算法。线图分析法 ( c h a r tp a r s i n ga l g o r i t h m ) 的核心是线图( c h a r t ) 表示法，线图表示法具 有简单、直观的特点。通过修改线图分析法的分析策略，可以方便地模拟很多 种分析算法，如自顶向下的分析方法、自底向上的分析方法、左角分析方法等 等。 2 5 2 线图的表示方法 线图有两种表示方法，如下： 线图表示法1 ：线图是一个无环有向图( d a g ) ，其中结点是输入句子中词 与词之间的每一个间隔为一个结点；结点的标记往往用一个序号来表示；边 ( 弧) 是对应于句子中的一个短语，边两端的结点给定了短语的边界，边的方 向总是从左到右。边上面不仅要标记短语的类型，还需要标记产生该短语的规 则；说明是在汉语分析中，为了兼容词语切分的歧义，常常将汉字之间的间 隔作为一个结点。 线图表示法2 ：如图2 1 所示( 以句子“我是县长派来的。”为例) ： 1 0 基于概率上下文无关语法的句法分析研究与实现 s 专n p v p 图2 - 1 线图的第二种表示 上述记录分析成功的短语的边称为非活跃边。在线图中，还有另一种形式 的边，用于记录一条规则不完全分析的结果，称为活跃边，如表2 1 所示： 表2 1 线图边的表示 记录方式边状态匹配程度起点终点对应词串 活跃s 一n pv p 0o 活跃 s n p v po1我 非活跃 s + n pv p 03我是县长 活跃边的引入，可以减少规则匹配中的冗余操作，提高句法分析的效率。 s 专 2 - 2 线图的分析 2 5 3 线图分析算法 在线图分析算法中，除了“线图( c h a r t ) ”以外还有一个重要的数据结构， 基于概率上下文无关语法的句法分析研究与实现 称为“日程表( a g e n d a ) ”。c h a r t 分析的过程就是一个不断产生新的边的过程。 但是每一条新产生的边并不能立即加入到c h a r t 中，而是要放到日程表( a g e n d a ) 中。日程表( a g e n d a ) 实际上是一个边的集合，用于存放已经产生，但是还没有 加入到c h a r t 中的边。日程表( a g e n d a ) 中边的排序和存取方式，是c h a r t 算法执 行策略的一个重要方面。c h a r t 算法就是一个由日程表驱动的不断循环的过程， 其基本流程如下： 1 ) 按照初始化策略初始化a g e n d a 2 ) 如果a g e n d a 为空，那么分析失败 3 ) 每次按照日程表组织策略从a g e n d a 中取出一条边 4 ) 如果取出的边是一条非活跃边，而且覆盖整个句子，那么返回成功 5 ) 将取出的边加入n c h a r t 中，执行规则匹配策略和规则调用策略，将产 生的新边又加入到a g e n d a 中 6 ) 返回第( 2 ) 步 线图分析算法的初始化策略：c h a r t 分析算法开始执行以前，要先将a g e n d a 初始化。对于不同的句法分析策略，初始化策略也不相同。自底向上分析的规 则调用将所有单词( 含词性) 边加入到a g e n d a 中：自顶向下分析的规则调用将 所有单词( 含词性) 边加入到a g e n d a 中，对于所有形式为s w 的规则，产生一 条形式为 的边，并加入到a g e n d a 中。 在c h a r t 算法中，边是逐条从a g e n d a 中加入到c h a r t 中的，将每一条边从 a g e n d a 中取出并加入到c h a r t 中时，都要执行以下规则匹配策略： 如果新加入一条活跃边形式为： ，那么对于c h a r t 中所有形式为： 的非活跃边，生成一条形式为 的新边，并加入到a g e n d a 中； 如果新加入一条非活跃边形式为： ，那么对于c h a r t 中 所有形式为： 的活跃边，生成一条形式为 的新边，并加入到a g e n d a 。 上面a 、b 为非终结符，w 1 、w 2 、w 3 为终结符和非终结符组成的串，其中w 1 、 w 2 允许为空，w 3 不允许为空。 对于不同的句法分析策略，规则调用策略也不相同： 自底向上分析的规则调用策略：如果要加入一条形式为 的边到c h a r t 中，那么对于所有形式为b cw 2 的规则，产生 一条形式为 的边加入到a g e n d a 中： 自顶向下分析的规则调用策略：如果要加入一条形式为 的边至u c h a r t 中，那么对于所有形式为b w 的规则，产生 基于概率上下文无关语法的句法分析研究与实现 一条形式为 的边，并加入至l j a g e n d a 中。 线图分析算法的日程表组织策略：通过日程表组织的不同策略，可以分别 实现深度优先和广度优先等搜索方法。 深度优先的日程表组织策略，将日程表按照堆栈的形式，每次从日程 表中取出最后加入的结点； 广度优先的日程表组织策略，将日程表按照队列的形式，每次从日程 表中取出最早加入的结点。 前面的讨论中忽略了两个细节，在实现一个系统时应该考虑到下面两个细 节： 可能通过多种途径生成一条完全相同的边，所以每次从a g e n d a 中取出 一条新边加入c h a r t 时，要先检查一下c h a r t 中是否已经有相同的边， 如果有，那么删除这条边，直接进入下一个循环。 为了生成最后的句法结构树，每一条边中还应该记录该条边的子句法 成分所对应的边。 c h a r t 算法具有直观和灵活的特点，通过修改分析过程中的一些具体策略， c h a r t 析算法可以模拟很多种其他句法分析算法。 2 5 4 5 9 法分析实例 在本例中，产生式规则是： 1 ) s n pv p 2 ) n p ，a i ha d jn 3 ) n p 一a r tn 4 ) n p + a d jn 5 ) v p a u xv p 6 ) v p vn p 分析句子为“t h el a r g ec a r l c a nh o l dt h ew a t e r ”其中，各词的词性 是： t h e ：h r t l a r g e ：a d j c a r l ：n a u x v ( 兼类) h o l d ：v w a t e r ：n v 为了更好的理解这个例题，下面将给出相应的线图。初始化时代理为空。 按照分析算法，可得下述步骤： 基于概率上下文无关语法的句法分析研究与实现 1 ) 读入“t h e ”，成分a r t l 被放在代理表上 选择a r t l ：( t h e 从l 至l j 2 ) ： 增加活动弧n p a r t a d 3n 从1 n 2 ； 增加活动弧n p - - a r t n 从1 到2 ； a r t i 插入到线图。 这两条活动弧文法自动规则得到的。 2 ) 读下一个词“l a r g e ”，成分是a r t l 选择a r t i ( 1 a r g e 从2 至t 3 ) ； 增加活动弧n p a d j n 从2 到3 ： a d j 插入线图，则增加新活动弧n p a r ta d s n 从2 至i j 3 ； 第一条弧是执行分析算法3 家加入的，而第二条弧是第一条活动弧的延伸， 利用了弧延伸算法。此时的线图如图2 - 3 所示。 3 ) 下一个词“c a n ”有三个词性( 成分) n 1 ，a u x i 和v 1 建立。 选择n 1 ：( c 3 n 从3 至r 4 ) ； 在步骤3 没有活动弧加入，再两条弧延伸算法生成，产生两个n p 被加入代 理表中，第一条从l 至l j 4 的n p ，是由规则n p a r ta d jn 构造的；第二条从2 至t j 4 的n p ，是由规则n p a d jn 构造的，现在n