（计算机软件与理论专业论文）线图分析法的一种改进方法.pdf

线圈分析法的一种改进方法 线图分析法的一种改进方法 硕士生：邹文杰 指导教师：姜云飞教授 摘要 线图分析法是分析自然语言的一种经典方法。和其他完全句法分析技术一 样，线图分析法的效率不高。基于线图分析法的语法分析系统大多数是所谓的“玩 具”系统。本文针对线图分析法的低效率，提出了一种改进的方法。 研究是基于软件研究所的w o r d h e l p 项目。该项目的目标是开发个针对英 文的语法检查器。为了提高线图分析器的效率，我们弓 入了单词以某种词性出现 的概率作为种启发信息，帮助系统从众多的词性标注方案中挑选出较有可能被 线图分析器接受的方案，并优先将这些方案优先发送给分析器。实验的结果的表 明，这种方法提高了整个系统的效率，虽然提高的幅度还不足以让线图分析器进 入实用的领域。但如果有更好的语料库和字典，这是一种很有希望的方法。而且 这种优化方法还可以用在其他类型的自然语言句法分析器上。 关键词：线图分析法，词性标注，句法分析 堡璺坌塑堡塑二登受! 塑堡 am e t h o df o ri m p r o v i n gc h a r tp a r s i n g n a m e ：w e n j i ez o u s u p e r v i s o r ：p r o f y u n f e ij i a n g a b s t r a c t c h a r tp a r s i n gi sw e l lk n o w na so n eo ft h et e c h n i q u e sw h i c ha r eu s e dt op a r s e n a t u r a ll a n g u a g e s j u s tl i k eo t h e rc o m p l e t ep a r s i n gt e c h n i q u e s ，t h es y s t e m sb a s e do n c h a r tp a r s i n ga r ea l w a y s t o y s y s t e m sb e c a u s eo ft h e kl o we f f i c i e n c y t h i sp a p e rp u t f o r w a r dam e t h o dw h i c hi sa i m i n gt oe n h a n c et h ee f f i c i e n c yo ft h ec h a r tp a r s e r s o u rr e s e a r c hi sb a s e do nt h ew o r d h e l pp r o j e c t ，w h i c hp u r p o s e sd e v e l o p i n ga g r a m m a rc h e c k e rf o re n g l i s h i no r d e rt oi m p r o v et h ee f f i c i e n c yo ft h ec h a r tp a r s e r ， t h ep r o b a b i l i t yo ft h ep o s ( p a r to fs p e e c h ) o faw o r dw a si n t r o d u c e dt oh e l pt h e s y s t e mt os e l e c tt h et a g g i n gs c h e m e ，w h m hi sm o r el i k e l yt oh ea c c e p t e db yt h ec h a r t p a r s e r t h ee x p e r i m e n t a lr e s u l ts h o w st h a tt h i st e c h n i q u ee n h a n c et h ee f f i c i e n c yo ft h e c h a r tp a r s e r a l t h o u g ht h ei m p r o v e m e n ti sn o tg r e a te n o o g ht on 珀k et h ec h a r tp a r s e r c o m ei n t op r a c t i c a lu s e b u tw i t hab e t t e rc o r p u sa n dd i c t i o n a r y , t h i si sap r o m i s i n g w a yw h i c hl e a d st oi l o r ee f f i c i e n tp a r s i n g a n dt h em e t h o dc a na l s ob ea p p l i e dt o o t h e rk i n d so f p a r s e r sb e s i d e sc h a r tp a r s e r k e yw o r d s ：c h a r tp a r s i n g ，p a r t o f - s p e e c ht a g g i n g ，p a r s i n g 线图分析法的一种改进方法 1 1 背景知识 第一章引言 语法检查最初是编译原理上的概念，它主要是确保用户编写的程序符合他所 用的程序设计语言的规范，以便编译器能正确地生成代码。1 9 5 4 年美国 g e o r g e t o w n 大学与i b m 公司合作，在i b m7 0 1 型计算机上进行了将俄语翻译成 英语的试验【1 1 。从此，以机器翻译为核心的自然语言处理( n a t u r a ll a n g u a g e p r o c e s s i n g ) 引起人们广泛的兴趣。初期的机器翻译对语言本质认识过于简单， 如g e o r g e t o w n 大学与i b m 公司所作的试验只是将俄语单词直接转换成英文单 词。很快人们就发现对语言的这种简单认识并不能让机器翻译成为现实。翻译是 语言在很高一个层次上的应用，它是同一个语义用不同的语言表达的问题，绝不 是简单的单词替换或句法的转换。在机器翻译遇到挫折后，人们开始重视自然语 言处理的基础研究，例如词法分析，句法分析等。语法检查几乎是句法分析的同 义词。句法分析的任务是分析一个句子的结构。如果把一个句法分析器( p a r s e r ) 做成一个识别器( r e c o g n i z e r ) ，识别能生成符合要求的分析树( p a r s et r e e ) 的 句子，那么这就是语法检查器( g r a m m a rc h e c k e r ) 。在一九八五年，语法检查被 确定为自然语言处理的七个主要应用之- 2 1 。这时候语法检查( 或句法分析) 已经是自然语言处理的一个重要的研究方向。 语法检查是建立在句法分析的基础上的，因此语法检查的问题可以归结为句 法分析的问题。句法分析随着句法理论的发展而发展。其中乔姆斯基( c h o m s k y ) 的句法理论对自然语言处理影响最为深刻。在乔姆斯基的理论里，语言成了一个 逻辑系统，可以通过一定形式的规则来识别和生成语言。虽然乔姆斯基的理论不 是十全十美，也有很多其它不同的句法理论( 如树连接语法( t r e ea d j o i n i n g g r a m m a r ) 【3 】、链语法( l i n kg r a m m a r ) 【4 ，5 】等) 。然而，乔姆斯基的理论还是 主流，自然语言语法的一般是用乔姆斯基理论中的下文无关文法( c o n t e x t - f r e e g r a m m a r ) 描述的。很多经典的分析算法都是基于上下文无关文法，例如广义 线圈分析法的一种改进方法 l r 分析法、e a r l e y 算法1 7 】、线图分析法( c h a r tp a r s i n g ) 等。为了提高分析器的 效率，又提出了部分分析技术( p a r t i a lp a r s i n g ) 。部分分析技术有时候也叫组块 分析( c h u n k i n g ) 【8 ，9 】，它放弃对句子整体结构的分析，改为对句子的局部结 构进行分析。另外，有些方法还引入统计的方法，改善基于规则的分析器健壮性 不好的问题。 对自然语言的分析分大致可以分为词法分析，语法分析和语义分析这几个层 次。一般要对高层进行分析，毖须先经过低层的分析。所以进行句法分析之前还 要进行词法分析。词法分析有两个任务，一是从输入串中切分出单词 ( t o k e n i s a t i o n ) ，二是给每个单词标上相应的词性( p a r t - o f - s p e e c ht a g g i n g ) 。对 于英文，第一个任务比较简单，因为英文句子中单词是用空格隔开的。第二个任 务对于所有语言来说都是个难点。词性标注最主要是要解决单词兼类问题。针对 这个问题，提出了很多词性标注的方法。基于这些方法开发出的某些词性标注器 ( t a g g e r ) 取得了9 0 以上准确率，如c l h w s 0 0 ，b r i l l st a g g e r 1 1 等。总的 来说，基于概率的词性标注器一般能取得更高的准确率，也是目前词性标注方法 的主流。 1 2 本文的研究内容及组成 词性标注研究一般假设待标注的句子是正确的句子，如果给出一个错误的句 子让词性标注器进行标注可能造成不可预计的后果。对于语法检查系统，它所处 理的句子往往不能预先知道句子是正确还是错误的，这很不利于词性标注的进 行。很多语法检查器采用穷举所有可能的词性标注方案的方法，然而这样做的效 率是很低的。本文提出一种改进方法，提高语法检查系统的效率。并通过实验系 统的验证改进后效率提高的幅度。 本文的结构如下： 第一部分介绍了语法检查相关的背景知识和论文的结构。第二部分介绍自然 语言处理基本的理论和相关的技术，并介绍了两个语法检查系统。第三部分提出 对线图分析法的改进方法。第四部分说明实验系统的体系结构。第五部介绍系统 2 线图分析法的一种改进方法 的具体实现过程。第六部分对实验数据进行分析。第七部分是实验的结论和下一 步工作的展望。 3 线圈分析法的一种改进方法 第二章语法检查的研究 2 1自然语言处理与语法检查 自然语言处理( n a t u r a ll a n g u a g ep r o c e s s i n g ) 也叫计算语言学( c o m p u t a t i o n a l l i n g u i s t i c ) 。它几乎和电予计算机同时诞生。1 9 5 4 年。美国g e o r g e t o w n 大学与 i b m 合作，在1 b m 7 0 1 型计算机上进行机器翻译的试验。他们以词对词的方式将 俄语翻译成英语。随后以机器翻译为核心的自然语言处理引起了人们的兴趣。然 而，因为当时对自然语言的本质认识不深和计算机的性能有限，在6 0 年代自然 语言处理的研究陷入了低谷。7 0 年代，一些关于自然语言新的理论的出现，重 新唤起了人们对自然语言处理的兴趣，而且人们也不仅仅将自己局限在机器翻译 的领域，更多地关注自然语言处理在其他领域的应用。2 0 世纪9 0 年代以后，人 类社会进入了信息时代，计算机已经成为了常用工具。人们希望能够更方便地与 计算机进行交流，甚至要求计算机能“理解”人类的语言。而这时候计算机的性 能比起6 0 年代已经有了一个质的飞跃。因此，许多与自然语言处理相关的系统 开始进入了实用领域，如微软拼音输入法、语音识别系统等就是自然语言处理系 统成功应用的例子。 语法检查在计算机领域很早就有广泛的应用。编译器在编译程序前都要对程 序进行语法检查，而且编译原理中的语法检查技术已经相当成熟。然而，程序设 计语言和自然语言有很大的不同。程序设计语言是一种受限的没有歧义的语言， 它无论在规模和复杂度上都不能和自然语言相提并论。针对自然语言的特点提出 了很多独特的算法。 语法检查是和自然语言处理中的句法分析密切联系起来的。语法检查的最主 要目的是判断一个句子是否符合语法，而判断根据就是句法分析的结果。可以说 语法检查正是句法分析的一种简单的应用。讨论句法分析前，首先要介绍一些计 算语言学的基本理论。 4 线图分析法的一种改进方法 2 2计算语言学的基本理论 2 2 1 形式语言理论 要研究语言首先要解决怎样表示语言的问题。对于语言的表示可以用下面的 三种方法1 1 2 ： 1 ) 穷举语言中的所有句子 2 ) 语法 3 ) 自动机 语法可以用来生成和识别正确句子，而自动机只能用来识别正确的句子。通 常一般用形式语法来描述语言。形式语法的定义如下： 定义2 1 形式语法g 是一个四元组c ，尸，s ) ，其中k 表示非终结符号集，表 示终结符号集，p 表示重写规则集，s 表示开始符，s 。 句子就是由语法g 从开始符s 派生出来的终结符序列。语言就是g 所能够 产生出来的句子的集合。 乔姆斯基( c h o m s k y ) 对产生式施加不同的限制，把形式语法分成四类【1 3 】： 1 10 型文法( 短语文法) g = c ，p , s ) 是一个0 型文法。如果每个产生式 a 口 都有：口( u ) 且至少含有个非终端符号，卢( ku ) + 。 2 ) 1 型文法( 上下文有关文法) g 的任何产生式a 辛卢满足h s ( 其中i a i 和例分别是a 和卢的长度) ； 产生式s - - 例外。s 不出现在产生式的右部。 3 ) 2 型文法( 上下文无关文法) g 的任何一个产生式是a - - 芦，a ，卢( u ) 4 13 型文法( 正规文法) 线图分析法的一种改进方法 g 的任何一个产生式为a 口b 或a 口，其中口+ ，a 、b e 0 型文法因为生成能力过强，会生成大量不合自然语言语法的句子，所以不 能用来描述自然语言。3 型文法生成能力过弱，自然语言的很多语言现象无法描 述。上下文有关文法比上下文无关文法的生成能力要强，但上下文有关文法使语 法定义变得很复杂，而且很难高效地分析，所以一般采用上下文无关文法描述自 然语言。 2 2 2 自然语言分析的层次 对自然语言的分析分下面几层1 1 4 1 ： a t o k e n i s a t i o n ( 分词1 ： 从输入字符串切分出单词。本文研究的是英文的语法检查，因为英文单词间 隔一个空格，所以这步骤较为简单。但对于词间没有间隔的语言( 例如中文) 这 步骤时一个难点。 b p a r t o g s p e e c ht a g g i n g ( 词性标注1 ： 给单词指定其对应的词性。这一直是研究的热点和难点。每个单词在某个句 子中只能对应一个词性( 歧义句除外) 。但作为一个独立的单词，有些单词会有 多种词性。如何从多个词性标记中选择一个适合的标记就叫标注消歧 ( d i s a m b i g u a t i o n ) ，这是一个难点。 c p a r s i n g ( 句法分析) ： 对词性标记序列进行句法分析。 d s e m a n t i ca n a l y s i s ( 语意分析) ： 从语意的角度分析句子。 e d i s c o u r s e a n a l y s i s ( 篇章分析) ： 对句子问的关系进行分析。 对于语法检查主要考虑的是分词、词性标记和分析这三层。语意分析和篇章分析 在语法检查中较少用到，但也有些研究用到后两层的知识作为辅助。 线图分析法的一种改进方法 2 3 语法检查的相关技术 计算语言学有三种基本的研究方法。他们分别是理性主义、经验主义、理性 主义和经验主义相结合。理性主义是将自然语言看作是一个符号处理系统，通过 预先设定的规则处理语言。经验主义是通过对真实文本的统计得到语言现象的数 据，然后用这些数据分析其他文本。将上述两种基本方法结合起来就是第三种方 法。 理性主义方法有时候也叫规则方法，由于有形式化的系统表示语言知识，在 特定的应用范围( 如编译程序) 能取得很好的效果。但基于规则方法的方法所描 述的语言知识颗粒太大，很难描述自然语言中细微的不规则的信息。另外，当规 则库上一定规模的时候，如何维护规则的一致性是一个难题。经验主义方法也叫 统计方法。通过对真实文本的统计获得语言知识，能够反映语言细微复杂的信息。 但基于统计的方法往往很难反映语言的整体结构。两者相结合的方法能吸收两者 的优点，但一定程度上也带有两者的缺点，具体效果取决于实际开发和所应用的 领域。 语法检查有两大关键技术：一是词性标注g g - m g ) ，二是句法分析( p a r s i n g ) 。 2 3 1 词性标注 自然语言中单词数目众多，如果直接以单词来处理显得不太现实。因此有必 要将单词分类，然后用单词所属的类别进行分析。一般将单词分为名词、动词、 代词等词类。这是我们所熟知的划分类别。也可以分得更细，在大的词类下面再 细分为很多的子类。分类后，给每个类别一个特定的标记，这就是词性标记。词 性标注的目的就是指出一个句子中每个单词所属的类别，也就标出它们的词性标 记。词性标注的难点在于解决词的兼类问题。某些单词在长期的使用中形成了多 重词性。例如，“p l a y ”可以作为动词也可以作为名词。这种有多重词性的单词 只占所有英文单词很小的一部分，但一般这些单词是常用的单词，因此在真实文 本中出现的概率是很大的。兼类词的数目和词类划分有关，般词类划分越细兼 7 线圈分析法的一种改进方法 类词就越多。然丽对于一个没有歧义的句子而言，每个位置的单词只能有一个词 性。针对兼类词的问题，人们提出了很多方法，开发了很多词性标注器( t a g g e r ) 。 ( 一) 基于规则的词性标注方法 这种方法主要是用手工的方法定义一些规则，通过上下文的信息进行标注消 歧。例如，可以定义规则“如果一个词的左邻接词是冠词且右连接词是名词，那 么这个词是形容词”。通过这种上下文信息就能判定词的词性。k l e i n 和s i m m o n s 用这种手工定义规则的方法开发的词性标注器在小样本测试中取得了9 0 的准 确率 1 5 。但同样是基于规则的t a g g i t 系统在b r o w n 语料库里测试却只有7 7 的准确率口6 。可见基于规则的系统健壮性不太理想。 ( 二) 基于统计的标注方法 对于单词串w = m w 2w 3 和它对应的词性标记t 2 t l t ：t ，t 。，所谓的词性 标注就是在给定的w 下求出t 出现的概率，即求p ( t | w ) 。使p ( t 1 w ) 最大的词性 标注串t 就是所求的词性标注串。根据贝叶斯公式有： p ( t i w ) ：p ( t ) p ( w i t ) 2 一l p ( w 1 p ( w ) 是w 在训练集出现的概率，它对所有标注结果都是一样的。因为只需要知道 p ( t w ) 是否最大，而无须计算准确的值，因此p ( w ) 可以省略。于是公式2 一l 简 化成： m a x ( p ( t l w ) ) = p ( t ) e ( w l t ) 2 2 再作假设，每个单词与这个词本身词性有关。公式2 2 中等号右边的第二项可以 简化为： p ( w 胁善p ( w i 2 - 3 由公式2 - 2 和公式2 - 3 得： m a x ( p ( t | w ) ) 29 ( 7 善p ( w 2 4 因为 p ( t ) = p ( t 1i t 。) p ( t 2i t l , t o ) p ( l f f 一。f i 一2 ，) 2 - 5 假设每一个词性标记只与其前一个词性标记相关( 二元模型) ，公式2 5 就可以化 8 线图分析法的一种改进方法 简为： 由公式2 4 和公式2 - 6 可得： p ( t ) 5 善p ( t j 2 - 6 腿x ( p ( t 1 w ) ) 5 善p ( t ； t l 一- ) 善p ( w ji ) 2 7 wq p ( t ；i t l _ 1 ) 和p ( w ；| f f ) 分别用下面的公式估算 1 即m i 护等鬻嚣器z s 盹i u 2 塑慧裟揣掣z 一。 对于给定的单词串，通过公式2 7 ，2 - 8 和2 - 9 就可以求出词性标注串的概率了。 然后最大概率的词性标注串就被看作是该单词串的正确词性标注。 c l a w s 1 0 就是用这种方法进行词性标注的，它在l o b 语料库中取得了9 6 的准确率。但随着单词串长度的增加，可能的词性标注串的数目按指数级增加。 因此对单词串求它的最大概率词性标注串的效率是很低的。在上面基本方法的基 础上，提出了改进的算法。v o l s u n g a 算法【1 7 】和v i t e r b i 算法【1 8 】采用了动态 规划的思想来解决效率问题。 ( - - - ) 基于转换的错误驱动的词性标注方法 错误驱动的词性标注方法本质来说是一种基于规则的方法。它在进行词性标 注的时候是按照规则进行标注的。但与普通的基于规则的方法不同，它的规则并 不是通过人来定义的，而是通过在大量的真实文本中“学”来的。从某种意义来 说这种方法也是一种统计的方法。基于这种方法的系统在对u p e 蚰w s j 语料库 的标注取得了9 7 的准确率【1 9 】，超过了其他基于统计的方法。该方法的组成如 下： 1 ) 转换规则 转换规则由改写规则( r e w r i t i n gr u l e ) 和激活环境( t r i g g e r i n ge n v k o n m e n t ) 组成1 1 】。例如： 改写规则：将一个词从动词( v ) 改为名词( n ) ； 9 线图分析法的一种改进方法 激活环境：该词左边第一个紧邻词的词性是量词( q ) ，第二个词的词性是数词 ( n 1 ) ； 上面就是一个转换规则的实例。它其实就是一个改错规则，这些规则运用的 时候是有顺序的。 2 ) 规则模板 规则模板是用来产生规则的，它是由人来指定的。下面是规则模板的一个例 子： 改写规则：将当前词的词性标记从x 改成y ： 激活环境：( 1 ) 当前词前( 后) 面的一个词是标记是z ： ( 2 ) 当前词前( 后) 面的第二个词是标记是z ； ( 3 ) 当前词前( 后) 面两个词中有一个的词性标记是z ： 其中x ，y ，z 是任意的词性标记。 根据上恧的模板，裁可以将具体的词性标记代入x ，y 和z 中生成具体韵转 换规则。系统通过学习就能从生成的规则中选出有用的规则。 3 ) 规则的学习 这神词性标注方法的核心是学习规则。除了上述的规则模板，进行规则的学 习还需要一个标注好了的语料库c 0 和一个初始的词性标注器( i n i t i a l t a g g e r ) 。对 初始的词性标注器没有任何要求。它可以是上面所说任意一种标注器，甚至可以 是将所有单词标注为一种词性的标注器【1 】。将来学习到的规则就是要帮初始词 性标注器改正错误的。学习的过程描述如下： a 用初始词性标注器对c o 进行标注，得到新的标注好的语料库c 。，统计出标注 错误的个数，； b 对c f ( i z l ) 逐条应用改写规则，对比c o 记录使标注错误到最少的改写规则正， 这就是当前找到的规则。如果所有规则都不能使错误减少，学习结束； c 将t 应用到c 。，得到c ，。转到b 步骤； 算法结束后就能, t 4 一组有序的规则，学习过程的流程图如图2 。1 1 2 0 。 1 0 线图分析法的一种改进方法 对新的语料进行词性标注的时候，首先用初始标注器处理待标注的语料。然 后按顺序应用学习到的改写规则，最后得到词性标注的结果。 自然语言是复杂的，对句子进行词性标注能够在一个更高的层面分析语言现 象，而不至于迷失在数不尽的语言现象的实例中，所以词性标注是绝大多数自然 语言的句法分析系统必须进行的步骤。但在上述介绍的词性标注方法都是考虑怎 样对一个正确的句子进行正确的词性标注。然而，对语法检查来说，要处理的句 子不一定是正确的，甚至经常是错误的。对于一个错误的句子用上面的方法进行 词性标注的话会产生不可预计的后果，影响语法检查的效果。 2 3 2 句法分析 图2 1 语法检查必须经过句法分析。句法分析研究的是怎样得到一个句子的句法结 构。如果说基于统计的方法在词性标注主流技术的话，那么基于规则的方法是句 法分析的主流。 线图分析法的一种改进方法 目前句法分析算法按分析的方向可以分为白底向上( b o t t o m - u p ) 和自顶向下 ( t o p d o w n ) 两种算法。自底向上的算法是采取规约的方法，看句子里的成分是 不是符合某条规则的右部，符合的话就把它规约成该规则的左部。不断地进行规 约，如果最后能够规约出开始符( s ) ，那么这个句子是正确的，并且能够得到句 子的语法结构；否则，这句子就是错误的。自顶向下的算法正好和自底向上的算 法相反。它从开始符( s ) 根据规则推导，如果最后能推导出所要分析的句子， 那么就能得到句子的语法结构。这两种方法本质上都是推导句子对应的分析树， 只是推导的方向不同而已。而任何一个正确的句子都是至少对应一棵以开始符 ( s ) 为根的分析树的。例如，句子“lv i s i tm yf r i e n d s ”对应的分析树如图2 2 。 如果一个句子有歧义的话，它可以对应多棵分析树。但对于语法检查而言，歧 义句可以被认为是语法正确的句子。下面介绍一些经典的句法分析技术。 圈2 2 ( 一) l r 分析法 l r 分析法是编译原理的一种经典方法，它被广泛地应用到各种程序设计语 言的编译器中。l 代表的是从左到右( 1 e f - t o r i g h t ) ，r 表示反向的最右( r i g h t - m o s t ) 推导，即最左规约。l r 分析器的模型如图2 3 1 2 1 1 。 l r 分析法的基本思想1 2 2 是：在规约的过程中，一方面记住已经移进和规约 线圈分析法的一种改进方法 出的整个符号串，即记住“历史”，另一方面根据所用的产生式推测未来可能碰 到的输入符号，即对未来进行“展望”。l r 分析法用到的栈存放着当前分析器的 状态和先前规约出来的语法符号。l r 分析器的控制器根据当前栈顶的元素和当 前输入字符查询分析表，然后根据分析表的指示对栈或输入缓冲进行下一步操 作。整个分析器的核心是分析表。 分析表是一个二维表。通过分析器的状态号和字符表的字符就能定位分析表 的任何位置。表中的元素存放着分析器四种可能的动作，分别是移进、规约、接 栈分析表 输出 图2 3 受和报错。分析器确定了栈顶元素和输入字符后只要查询分析表就能知道下一步 的动作。分析表的构造是很复杂的，而且可以有不同的分析表。常见的有s l r 分析表，l a l r 分析表和规范l r 分析表( c a n o n i c a ll r ) 。采用这三种分析表的 分析器分别叫s l r 分析器、l a l r 分析器和规范l r 分析器。这三种分析器处理的 能力和系统的花费各不相同。s l r 分析器的处理能力最弱，但系统花费最小；而 规范l r 分析器的处理能力强，但系统花费最大。l a l r 分析器处于两者之问，因 此l a l r 分析法应用最为广泛。 无论哪一种l r 分析法都只能处理上下文无关文法的一个子集。当超出了这 个子集就会产生冲突，即分析表有些表项包含的动作不唯一。出现冲突后，分析 线圈分析法的一种改进方法 器就不能决定到底应该选择哪一个动作。所以l r 分析法不能直接处理自然语言。 富田胜算法 2 3 是对l r 算法的一种改进。对于l r 分析法的冲突问题，该算法引 入了并行的思想来解决。当一个表项包含的动作不唯一的时候，分析进程就分裂 成几个子进程，同时对所有动作进行分析。该算法还提出了子树共享和局部歧义 压缩的分析树表示技术，降低了算法的空间复杂废。 l r 分析法因为其无回溯的性质，在分析时的效率很高。但l r 分析法建立分 析表的过程十分繁琐和复杂，而且对于自然语言来说巨大的分析表的存取也是一 个问题，所以l r 分析法实际的应用并不多。 ( 二) 厄尔利( e a r l e y ) 算法 厄尔利算法是一种自底向上的分析算法。与l r 分析法不同，它可以用来处 理上下文无关文法。厄尔利算法用项目来表示已经建成的完整或部分成分结构 【1 2 。项目是指在规则右部插入圆点的规则。圆点前面的部分已经成功匹配，圆 点后面部分还没有匹配。例如：s - ) n p - v p 表示n p 已经成功匹配，v p 还有待 匹配。 厄尔利算法用字符问的间隔表示字符串的起始位置。例如句子“lg ot o s c h o o l ”可以表示成下面钓形式： 0il g o 2t o3s c h o o l4 厄尔利算法的对每一个间隔建立项目集。项目集不但包括项目，还有项目中 成功匹配部分的起始间隔。对于一个有n 个单词的句子就有n + 1 个项目集。厄尔 利算法本质上就是求一个句子所有项目集的方法。 厄尔利算法【1 2 】： 输入：上下文无关文法g = ，待分析符号串w = w 1 w 2 k ，其中 w l 咋，待分析符号的字符间隔为0 ，1 ，2 ，n 输出：w 的项雕集。l ，。 步骤： a ) 首先构造j 。 ( 1 ) 初始化：形如 属于i o 1 4 线图分析法的一种改进方法 ( 2 ) 扩展：如果 n 于i o ，b - - ) r e p ，那么 t g 属于厶( a ，芦可为空，1 3 为非终结符) ( 3 ) 重复执行( 2 ) 直到没有项目可以添加到l 中 b ) 在已经构造完厶j ，。的基础上构造， ( 1 ) 移位：如果 属于j ，。，b 是输入字符的第j 个字符，那么 属于j ； ( 2 ) 扩展：如果 f f 禹 t i j ，b 是输入字符串的第j 个字符， b 专y e p , 那 a y ，j 也属于f f ( 3 ) 如果 属于，并r 口a f t ，i 属于l ，那么 属于，；。其中：口，卢可为空，a ，b 为非终结符，b 为终结符 ( 4 ) 重复( 1 ) ( 2 ) ( 3 ) 直到没有新的项目可以添加到i i 为止 例如，分析句子“0i1 g o 2t o3s c h o o l4 ” 字典： i ：p r o ng o ：vt o ：p r 印 s c h o o l = n 规则集： i s - - n p v p i i n p - - ) p r o n i i i 专v p r 印 i v n p - 9 n v v p - - v pn p 线圈分析法的一种改进方法 分析过程如表2 - 1 ，ol，2 p r o n o ，3 4 p r o n ，3 n ，3 n 3 表2 1 如上表所示在，。中找到 ，它是从0 位置开始并且左部是开始符 s ，因此这句子时正确的。 厄尔利算法能把所有的分析树找出来( 如果存在的话) 。算法的时间复杂度 是0 ( h 3 ) 【2 4 】。 ( 三) 线图分析法 线图分析法和厄尔剩算法根相似，也是用单词闯的间隔表示字符串的起始， 用圆点将规则分隔成已匹配部分和未匹配部分。和厄尔利算法一样，线图分析法 也能够处理上下文无关文法。线图分析法的独特之处在于引入了线圈和边的概 念，使分析过程变得直观，基于线图的分析器实现起来也相对简单。 线图分析法只是某一类算法的总称，在具体步骤上采用不同策略就衍生出不 同的算法。只要是正确的句子就能用线图分析法找到其对应的分析树。基于上述 的好处，本文的实验系统采用了线图分析法。线图分析法的具体介绍见第三章。 ( 四) 基于概率上下文无关语法的句法分析 上述所有分析就是都是完全基于规则的。一般规则是由语言专家总结出来。 虽然这些规则具有一定的代表性，但单凭人工定义的规则很难反映自然语言中的 1 6 线图分析法的一种改进方法 一些细节。所以，基于规则的方法往往缺乏柔性，对一些不规则的语言现象无能 为力。 正是基于这种考虑，提出了概率上下文无关语法( p r o b a b i l i s t i cc o n t e x t f r e e g l a l n l n a r ) 。概率上下文无关语法是上下文无关语法的一种扩充。它和上下文无 关语法的不同在于每个规则都有一个概率值。规则的概率不是随意给定的，而是 通过对大规模的语料库的统计获得的。 概率上下文无关语法被用作句法歧义消解( s y n t a c t i c a m b i g u i t y r e s o l u t i o n ) 。 当一介句子有歧义的时候，能够推导出硬棵分析树。上述所有的方法都不能凳辨 歧义旬中哪一种结构才是正确的结构。在概率上下文无关语法中，可以通过计算 每棵分析树的概率来消除歧义。分析树的概率定义为，推导该树所用到的规则概 率的乘积。 ( 五) 部分分析技术 上述所有方法都是完全分析技术( c o m p l e t ep a r s i n g ) ，它们共同的目标是得 到句子完整的分析树。然而，无论从时间复杂度还是空间复杂度上看，完全分析 技术的花销是巨大的。基于完全分析技术的分析器很少得到实际的应用。还有， 在真实的文本当中，句子往往是不完整的，这在口语中尤为明显。如果用完全分 析技术是不能接受这些句子的，系统的健壮性就得不到保障。基于上面两个原因， 提出了部分分析技术( p a r t i a lp a r s i n g ) 。 部分分析技术放弃了生成完整的分析树，只分析句子的浅层结构，因此也叫 做浅层分析( s h a l l o wp a r s i n g ) 。它是一种牺牲分析深度，换取效率的策略。部分 分析法一般分析名词短语，动词短语等局部结构。 2 4 现有系统的介绍 1 ) m i c r o s o f lw o r d m i c r o s o f tw o r d 是当前流行的字处理软件，语法检查模块作为它的一个辅助 工具。w o r d 对英文日常书写中常见的错误非常敏感，在很多测试中都取得了很 1 线图分析法的一种改进方法 好的效果。w o r d 不但提供语法检查，而且提供修改意见以指导用户改正句子错 误。在新的版本，在某些情况下能自动帮用户修改错误。w o r d 在初期版本是用 基于规则的方法进行分析，在后期版本加入了统计的方法。因为w o r d 语法检查 的优异性能，它成为很多系统的参照物。 2 ) w o r d h e l p w o r d h e l p 是由中山大学软件研究所开发的英文辅助学习系统。系统所采用的 方法是实例和规则相结合的【2 l 】。系统开发的。目的是给予英语学习者和佼用者 适当的帮助，通过对错误语法的认识使他们达到提高英文写作能力。在测试样本 中取得了比w o r d 更高的准确率。但因为w o r d h e l p 系统主要是采用错误实例匹 配的方式检查错误，必须附带一个庞大的错误实例数据库，造成检查的效率很低。 另外，w o r d h e l p 脱离了其专用的领域，准确率会大大的下降。 线圈分析法的一种改进方法 第三章对线图分析法的改进 3 1 线图分析法概述 在一般的自底上( b o t t o m - u p ) 移迸一归约( s h 谴- r e d u c e ) f f j 分析方法会遇到 一个问题，就是有可能一个句子存在一棵完整分析树。却不被发现。而一般的自 顶向下( t o p d o w n ) 的递归下降( r e c u r s i v e d e s c e n t ) i 筘j 分析方法会遇到效率的问 题。它要求不能出现左递归的规则( 例如：a - a b ) ，否则分析器会陷入无尽的 循环中。如果规则存在左递归，必须用某种方法消除。线图法( c h a r tp a r s i n g ) 避 免了上面的两个问题。它采用了动态规划( d y n a m i cp r o g r a m m i n g ) 的思想，在分析 的过程中保存分析的中间结果。 线图法的组成部分主要有： 1 ) 线图( c h a r t ) ：线图主要来表示已经成功建立的成分( 包括终结符和非终结符) 和起止位置。 2 ) 议程表( a g e n d a ) ：用来记录刚得到的重写规则的左部。对于议程表有两种处 理策略，先进先出或先进后出。 3 ) 活动边集( a c t i v ea r c ) ：活动边集用来保存只匹配了一部分的规则。 在分析的过程中，语法规则被标记成点规则( d o tr u l e ) 的形式。例如：a b c 表示a - - y b c 规则中“”以前的部分已经被成功匹配，“”以后的部分还没有匹 配。有两个特殊的情况，a - y b c 表示该规则已经匹配完毕，a 专b c 表示该规则 还没有匹配到。 在进行分析之前，首先将句子( 或词性标记序列) 表示成如下的形式： 0w 1 1w 22w 3 3 。i - 1w ii 其中，w i 是句子的单词( 或者是单词的词性标记) ，w i 前后的数字表示边的起 始位置。线图分析算法的形式化描述如下【1 】： 算法3 - 1 线图分析法的一种改进方法 1 把单词串( 或词性标记串) s 读入缓冲区 2 如果缓冲和议程表不为空，则重复下面几步 a ) 如果议程表为空，则读入一个单词( 或词性标记) ，然后将这个输入 符号连同起始位置放入议程表 b ) 从议程表弹出栈顶的边( 其代表的成分为e ，起始位置是仍，艺) ) c ) 从规则集中查找形如a - ) e b 的规则( e ，曰( u ) ) ，在活动边 集增加起始位置为( e ，只) 的边，并且标记为a g e b d ) 把刚才从栈顶弹出来的边加到线图( 只，只) 位置 e ) 检查所有的活动边，找到位置为( r ，只) 且标记为c 专d ef 的活动 边( e ，f 是终结符或非终结符) ，在活动边集增加一条位置为( b ，巴) 且标记为c - de f 的边( c 是终结符；d 是终结符或非终结符) d把所有起始位置为( 晶，b ) 且标记为g - hi 的边，并将它加入到议 程表( g ，h ，i 都可以是终结符或非终结符) 对于正确的句子，算法结束后至少能找到一条覆盖整个句子的边，而且该边 所代表的规则的左部为开始符s 。 例3 1 通过对句子“ia mam a n ”的分析过程来说明线图分析法的工作机 制。 规则待分析句子 s n p v n pv a mia m am a r n p - p n nn 专n l a l l n p - 9 d tnd t - a p n n 专】 首先，因为议程表空按照a ) 读入“i ”，然后将i 和其起始位置【0 ，l l 放) k 议 程表，于是有分析格局： o 123 4 根据b ) 将栈项的边弹出。根据c ) 我们找到p n n - i ，并且将当前位置【o ，l 】和 线图分析法的一种改进方法 p n n 放入议程表。于是有下面的分析格局： 0 按照d ) 有 234 4 4 4 厂 目 厂 h i 一 然后执行e ) 可以用【o ，1 1 s 专n p - v n p 和【1 ，2 1 v - a m 合成【o ，2 1 s - n p v n p ， 得到如下的分析格局： 园 目 线图分析法的一种改进方法 s 专n p - v n p 34 厂 卜一 l i _ j 对例1 1 1 而言，当算法结束的时候能找到边【0 ，4 】s - ) n p vn p ，这表明该句 子对于上述的语法规则来说是正确的，即存在一棵完整的分析树( 如图3 1 ) 。 3 2 线图分析法的改进 图3 1 线图分析法主要是指引入了线图结构记录中间分析结果的一类算法，具体处 理的过程有很多策略。例如对议程表可以采用后进先出的策略或先进先出的策 略；对整个分析而言，可以采用自底向上的策略、自顶向下的侧策略或者是两者 相结合的策略。还有更为特殊的c k y ( c o c k e k a s a m i - y o u n g e r ) 算法，它要求规则 是乔姆斯基范式( c h o m s k yn o r m a lf o r 啦，即规烈只有a 专bc 积a - ) w 两种形 式，其中a 是非终结符，w 是终结符，b 、c 既可以终结符也可以是非终结符。 n ii ml。 s iv ii|i 线圈分析法的一种改进方法 因此c k y 算法最后得出来的分析树是一棵二叉树。 自底向上的线图分析法的最坏时间复杂度是o ( k + _ r 1 3 ) ，其中n 是句子的单词 数，k 是常量，k 依赖于所使用的算法 1 3 。因此自底向上的线图分析法比一般 自底向上的分析法的效率低 1 3 。但只要句予是在某个规则集上是正确的话，线 图法就能找出它所有完整的分析树。而且线图法只要求上下文无关语法( c o n t e x t f r e eg r a m m a r ) ，允许语法规则存在左递归的情况，避免了陷入死循环。 但线图分析法是一种完全句法分析技术( c o m p l e t ep a r s i n g ) ，它的目标是分 析句子的完整结构，所以总体的效率还是很差。很多利用完全句法分祈技术的构 建的语法分析器都只能是玩具系统( t o ys y s t e m ) 1 。一般实用的语法分析系统 都是采用部分句法分析技术( p a r t i a lp a r s i n g ) 。部分句法分析是通过牺牲分析 的深度来换取系统的效率，所以部分分析技术只能确定一个句子的某些部分时正 确的，并不能确定整个的句子是否正确。 对于线图分析法的低效率，本文提出一种改进方法，希望能够提高线图