（教育技术学专业论文）限定领域的基本陈述句句法分析.pdf

天津师范大学硕士学位论文摘要 摘要 本文是机器人辅助打台球项目的一部分，在实现机器人打台球的工作中， 怎么样让机器人与人进行交流和沟通，是我们需要解决的一个问题。 因为汉语是一种分析型语言，汉语的分析过程是一个语法知识、语义知识 以及常识性知识公用的过程。如何在语料中表达句子中蕴涵的复杂知识，如何 使机器学习的方法获取这些复杂的不同层次的知识，并把它应用于句法分析成 为了一个热点问题。所以，句法分析在自然语言处理领域中具有十分重要的地 位，句法分析的好坏直接影响着句子进行语义的分析。因此，围绕着句法分析 的系统实现成为了本文研究的主要内容。 本文分析了汉语自身的特点，指出了汉语句法分析所面临的困难。对于基 于规则的句法分析技术和研究句法分析工作的重要意义做了较全面的综述，并 在此基础上设计了基于c h a r t 分析算法的句法分析方法，实现了一个汉语句法分 析系统。通过这个句法分析系统，生成句法分析树，从而达到理解语句的目的。 关键词：自然语言理解，句法分析，c h a r t 算法 天津师范人学硕士学位论文a b s t r a c t a b s t r a c t 1 1 1 i ss y s t 锄i sp a no ft l l er o b o t a s s i s t e dp l a 如n gt h eb i l l i 矾sp r o j e c t ，mo r d e rt o r e a l i z e dm er o b o tp l a y i n gt h eb i l l i a r d s ，w es h o u l dr e s 0 1 v e dh o wt om a l ( er o b o t sa i l d h u m 锄e x c h a j l g e sa i l dc o i i l 】叭i n i c a t i o n c h i n e s ei sat y p eo fl a i l g u a g e ；m ec h i n e s el a l l g u a g ei sap r o c e s so fk n o w l e d g e s y n t a x ，s 锄a 1 1 t i ck n o w l e d g ea n dt h ec o m m o ns e n s ek n o w l e d g eo f t 1 1 ep r o c e s s h o w t oe x p r e s st 1 1 es 肌t e l l c ec o 印u sc o n t a i n e di nt h ec o n l p l e xl ( i l o w i e d g e h o wt om a k et 1 1 e m a c l l i n cl e a n l i n g 廿l em “h o d st 00 b t a i nd i 岱舶m tl e v e l so fc o m p l e x i t yo ft l l e l ( 1 1 0 w l e d g ea n dt 0a p p l yi tp a r s i n gb e c l o m eah o ti s s u e c l 髓d y ，p a r s i n g i 1 1t l l e6 e l do fm i t u r a ll 锄g u a g ep r o c 懿s i i l gh a v cav e 叫i i l l p o r t a n t p o s i t i o i l s ) ，i l _ t 强锄a l y s i so ft l l ei i l l p a c to ft l l es e n t c ef o rg o o d0 rb a ds 锄a n t i c 锄a l y s i s n e r e f o r e ，a r o u n dp a r s i n gt 1 1 es y s t e m sb e c o m e l em a i l lc o n t e n to f l i s p a p e r i i l l i sp a p 锄a l y s i so ft l l ec h a r a c t 甜s t i c so ft h ec h i n e s el a i l g u a g e ，c m n e s e l 锄g u a g cp a r s i l l gp o i m e do u tf a c c dt l l ed i 伍c u l t i 器n o w t l l i sp a p e ra l s 0i n n 。o d u c 懿 m ep a r s i n gm l e s - b 硒e ds y s t 锄i n v o l v i n gs e v e r a lc 0 删 n o i l l yu s c da l g o r i u 1 1 s 锄d t c c l l r l 0 1 0 酉骼，a 1 1 dt l l ep a r s i n gt e c t l i l o l o g yc 0 舢【i l o m y1 l s e da 1 9 0 r i m m sa r e 觚a 1 ) ，z e d m e i fc h a m c t 甜s t i c s t h j ss y s t e m a t i ce x p o s i t i o no fh o wt 0c o i l s 仇l c t 锄a l g o r i m mb a s e d o nt l l ec h a r to ft h es y n t a c t i ca l l a l y s i ss y s t 锄t h r o u g ht h i ss y s t 锄，w eh o p et o g e l l e r a t eap a r s et r e e ，s ow ec 柚a c h i e v em ep u l p o s e o fu 1 1 d e r s t a l l d i n gt h es e n t e i l c e s k e yw o r d s ：n a 仙r a ll a i l g u a g ep r o c e s s i n g ，c h a r tp a r s i n g 撕t h m e t i c ，r e g u l a r e x p r e s s i o n i i 独创性声明 本人声明所早交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得苤盗! 至基盘堂或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意。 签名：趣篮 日期： 学位论文版权使用授权书 本人完全了解天津师范人学有关保留、使用学位论文的规定，即：学校有权将学位论 文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、 汇编以供奄阅和借阅。同意学校向国家有关部门或机构送交论文的复印什和磁盘。 ( 保密的论文在解密后应遵守此规定) 签名：煎整导师签名：妻! 查丛日期： 天津师范人学硕i ：学位论文第一章引言 1 1自然语言处理概述 第一章引言 自然语言处理似l p ，n a t u r a ll a n g u a g ep r o c e s s i n 曲，也称自然语言理解或计 算语言学，它是通过建立形式化的数学模型来分析、处理自然语言，并在计算 机上应用程序来实现分析和处理的过程，从而达到通过计算机来模拟人的部分 乃至全部语言能力。 自然语言不同于人工语言，表现在： ( 1 ) 自然语言中充满着歧义，而人工语言中的歧义是可以控制的。 ( 2 ) 自然语言的结构复杂多样，而人工语言的结构相对简单。 ( 3 ) 自然语言的语义表达千变万化，迄今还没有一种简单而通用的途径来 描述它，而人工语言的语义可以由人来直接定义。 ( 4 ) 自然语言的结构和语义之间有着错综复杂的联系，一般不存在一一对 应的同构关系；而人工语言常常可以把结构和语义分别进行处理，人工语言的 结构和语义之间有着整齐的一一对应的同构关系【1 1 。 同时，对于自然语言的处理也不同于传统的语言学上对语言的处理，表现 在： ( 1 ) 传统语言处理是一门经验学科，而自然语言处理既是一门理论学科， 又是一门实验科学。 ( 2 ) 自然语言处理要面对整个自然语言现象，因此，它必须研究计算机处 理语言的带有普遍性和总体性的一般问题；而传统的语言学家喜欢深入研究某 一特殊的语言现象，更加重视语言中的某个特殊问题。 ( 3 ) 传统的语言处理主要是描述性的，而自然语言处理要求的语言学理论 必须具有可操作性，要想操作，就首先要把一个句子中所有的信息，包括词法 的、句法的、语义的都形式化，变成机器可以识别的规则，这样它才能进行一 天津师范人学硕上学位论文第一章引言 步步的操作，最后达到理解这个句子的目的。自然语言处理最根本、最关键的 方法就是要指出各种语言形式出现和变换的条件。只有指出了条件，计算机才 可能根据有关的条件，执行相应的动作，从而使整个系统成为一个动态地执行 过程。不论哪一种计算机，在执行有关程序时，总免不了给它指出条件，有了 条件，并且让计算机知道究竟是什么样的条件，计算机才能执行相应的动作， 这就是可操作性，而计算机的任何操作都可以归结为一个公式：“条件一动作 偶对。要使自然语言的语法规则成为可供计算机执行的形式，就必须指出各种 语法现象出现的条件。 ( 4 ) 自然语言处理研究成果必须是要通过计算机自然语言处理来检验，自 然语言处理的理论要说得通，更要重视理论的实用性。而传统语言学则要求讲 道理，重视逻辑的完美性。 ( 5 ) 自然语言处理研究语言时必须先分析后理解，理解是分析的结果。而 传统语言学是先理解后分析，理解是分析的必要前提【2 1 。 由于自然语言及其在处理过程中的这些独特性质，使得自然语言处理成为 了人工智能的一大难题。 1 2 自然语言处理主要研究的内容 自然语言处理，研究如何让计算机理解和运用人类的自然语言，使得计算 机懂得自然语言的含义，并对人给计算机提出的问题，通过对话的方式，用自 然语言进行回答。自然语言理解系统可以用作专家系统、知识工程、情报检索、 办公室自动化的自然语言人机接口，有很多的实用价值。 按照语言学上一般的分析，语言可分为如下一些层次：语音、词汇、语法、 语义、语用。计算机在语言学上各个层次的应用便形成了语音分析、词法分析、 句法分析、语义分析和语用分析，这也是自然语言理解主要研究的内容。 ( 1 ) 语音分析：根据音位规则，从语音流中区分出一个个独立的音素，再 根据音位形态规则找出一个个音节及其对应的词素或词。 2 天津师范大学硕上学位论文第一章引言 ( 2 ) 词法分析：词法分析的主要目的是找出词汇的各个词素，从中获得语 言学信息。 ( 3 ) 句法分析：句法分析是对句子和短语的结构进行分析。句法分析的最 大单位是一个句子，分析的目的就是找出词、短语等的相互关系以及各自在句 中的作用等，并以一种层次结构来加以表达。 ( 4 ) 语义分析：句子是由词组成的，句子的意义与词义直接相关，但不等 于词义的简单相加。因此，还应考虑句子的结构意义。语义分析就是要找出词 义、结构意义以及其结合意义，从而确定语言所表达的真正含义或概念。 ( 5 ) 语用分析：语用分析的任务是研究语言所存在的外界环境对语言使用 所产生的影响。它描述语言的环境知识与语言使用者在某个给定语言环境中的 关系【3 1 。 1 3 自然语言处理的意义 自然语言处理这个研究方向在应用和理论两方面都有着重大意义。如果计 算机能够理解、处理自然语言，人、机之间的信息交流能够以人们所熟悉的自 然语言来进行，将是计算机技术的一项重大突破。另方面，由于创造和使用 自然语言是人类高度智能的表现，因此对自然语言处理的研究也有助于揭开人 类高度智能的奥秘，深化对语言能力和思维本质的认识。 1 4 限定领域内的自然语言理解及其特点 研究基于限定领域的自然语言理解，基于限定领域的汉语计算机理解的特 点，我们可以更加有目标性和针对性地对其领域内的语言进行分析，这为选择 最适合所在领域的自然语言理解理论提供了一些分析条件。 对一个具体领域的汉语的自然语言理解，又称为基于受限汉语的自然语言 理解。在基于受限汉语的计算机理解中，语言的词汇归纳对其汉语的语义分析 起着非常重要的作用，因为在有限的范围内，例如我们这个课题是关于台球教 天津师范人学硕：t 学位论文第一章引言 学的，内容上基于的是同一位作者的两本台球教材书，我们知道每个人的语言 表达方式都有其独特的特质，再加上语言的内容也是单一的，这也为我们分析 其汉语语言提供了条件。那么为了要让计算机能对特定领域的语言做到“理解， 因此要让计算机理解汉语必须获取相关的汉语语义知识。在这个领域的汉语知 识集的完整同时也起着决定性作用。这样，限定领域的汉语自然语言理解有着 以下的特点： ( 1 ) 词量有限。汉语语义系统中最基本的语义组织是词义，建立领域的理解 的词汇量，即确定一个描写词义的词量范围，使词义的描写或分析可以覆盖到 一定的流通面。在这个领域中，可以达到不会产生。不理解一和“误解的问 题。根据统计获得的词义和建立的词义库会在一定程度降低汉语的自动分析的 难度。 ( 2 ) 义项相对简单。任何词义都是对着词的义项而言的。在领域语言理解中， 通用词或者说高频词并非全部义项都常用，例如“把 字可以作名词( 如草把) 、 介词( 如把门关上) 、量词( 一把刀、一把米) ，而在特定的领域中，比如在数 学领域中使用时，“把 作为量词与名词的频率远远小于把作为介词的频率。另 一方面，整体语言中的部分词汇在领域中只有固定的意义，如机械领域中“许 用”不单独使用只是形成这些词“许用应力或后面跟着一些是应力的子类( 切 应力、压应力等) 等。 ( 3 ) 层级受限。词，句，段落形成具有一定的规律，并不完全孤立。词按照 一定的搭配组合组成一个句子陈述或说明一个主题事件，具有相同主题的句子 按照一定的逻辑关系组成了段落，更丰富说明一个主题事件。因此，这些内容 的理解是逐层进行的，从词的意思到段落的意思，对应每一部分内容存在的歧 义消除了，该部分内容就完全理解了。 1 5 句法分析概念 所谓句法分析是指判断输入的单词序列能不能构成合乎语法的句子，抽取 4 天津师范人学硕士学位论文第一章引言 出合乎语法的句子的句法结构【7 1 。也就是应用句法规则和其它知识，将该输入句 子中单词之间的线性次序，变成一个非线性的数据结构，如短语结构树或有向 无环图等。 句法分析是自然语言处理的一个基本问题，在许多自然语言处理任务，如 机器翻译、信息获取、信息检索、自动文摘等研究中都有重要应用。其研究的 主要内容包括： 句子中包含哪些词语? 每个词语的句法范畴是什么? 如名词、动词、形容词等等。 句子中更大的成分是什么? 句子中包含哪些短语或词组，如名词短语、动 词短语、介词短语等等。 句子中各成分或短语怎样组合或附着而构成整个句子的句法结构? 1 6 句法分析的研究现状 早期的句法分析工作始于2 0 世纪5 0 年代，1 9 5 0 年w 曲a e r 设计实现了一个 以简单“查字典”为基础的机器翻译原型系统，该系统的失败使人们认识到机 器翻译的过程需要更高水平的知识表示方法，由此展开了句法分析的研究。 句法分析的研究从技术上可以分为两种途径：基于规则的句法分析技术和 基于统计的句法分析技术。 基于规则的句法分析，强调语言学家对语言现象的认识，采用非歧义的规 则形式描述和解释歧义行为或歧义特性。这种方法由一套完整而周详的大规模 语法规则支撑，而规则的获取是一个十分繁琐的过程，它完全依赖于开发规则 的知识工程师的语言知识和经验。 基于统计的处理技术是从大规模语料库中获取语言分析所需要的知识，它 的基本思想是： ( 1 ) 使用语料库作为唯一的信息源，所有的知识( 除了统计模型的构造方 法) 都是从语料库中获得的。 5 天津师范人学硕士学位论文第一章引言 ( 2 ) 语言知识在统计意义上被解释，所有参量都是通过统计处理从语料库 中自动学习到的。 基于规则和基于统计这两种方法的区别主要体现在以下三个方面： ( 1 ) 它们在如何认识自然语言知识以及如何对其进行表示上存在不同。规则方 法主张以建立形式化知识系统的方式来表述知识；而统计方法则主张搜集实际 的语言材料形成语料库，将语料库本身看作知识。 ( 2 ) 它们在如何得到自然语言知识上存在不同。规则方法采用内省方式来检 验、调整、改进自然语言知识，使得该知识在自然语言处理系统中能有较满意 的效果；统计方法通常通过构造统计模型，由计算机对语料库中的语言现象进 行统计，得到统计规律意义上的知识。 ( 3 ) 它们在如何使用自然语言知识构造自然语言处理系统上存在不同。规则 方法主要以处理上下文无关的一些算法为主要方法；而统计方法主要发展基于 隐马尔可夫模型的自然语言处理算法。 在句法分析的研究中，基于规则的方法一直是句法分析的主要方法。从5 0 年代开始，出现了一些有代表性的以规则为基础的系统。5 0 年代末到6 0 年代初， c h m o s k y 的转换语法和形式理论为下一代的自然语言处理提供了一种新的解决 方案。如s a d s a m 利用c h o m s k y 形式化理论生成的可以处理大约1 7 0 0 个词和 有限的英语语法的句法分析器，但s a d s 川存在着低效率及对词汇和语法过 多的限制。 6 0 年代自然语言处理的主要技术是关键词和模式匹配方法。比如b a s e b a l l 。系统、s r i 系统、s 砌e n t 系统都采用了在文本中查找简单的模式或者某种正则 表达式的方法。模式的特点是：凡是模式中包含的语言现象都可以得到较好的 处理，一旦遇到模式中没有考虑的语言现象，则做缺省处理，缺省的效果往往 较差。因此在处理大领域的语言问题时，模式的方法难以胜任。 7 0 年代初，w o o d s 提出了转移扩张网络法( 心g u m e l l t e dt r a i l s i t i o nn e t 、】l ，o r k s ) ， 增加了正则表达式的能力，同时克服了用有限状态机表达上下文无关文法时存 在的限制，然而a n t 方法严格依赖于特定的应用领域，移植非常困难。 6 天津师范人学硕：l 学位论文第一章引言 在这期间，上下文无关文法( c f g ) 由于有高效的分析算法而成为广泛使用的 自然语言句法分析方法。但是c f g 处理自然语言时有生成能力过强的缺陷，使 用它进行句法分析容易产生多种有歧义的分析结果【8 】。 自此以后，国内外学者相继研究一系列基于规则的改进算法，以提高句法 分析的正确性。近年来，国内很多研究人员结合汉语特点通过改进国外的一些 成熟高效的句法分析算法开发了很多实用化的汉语句法分析器，他们主要使用 两种算法：l r 分析算法、c h a n 分析算法。也有一些学者吸收两个算法的优势 来达到追求高效率的分析算法的目标。本文采用c h a r t 算法来实现句法分析的过 程。 1 7 汉语句法分析所遇到的困难 有人把世界上的语言分成孤立语、曲折语、黏着语、复杂语四种类型，汉 语是孤立语的代表。孤立语的特点是缺乏词形态变化，语法规则较为灵活。其 具体表现在： ( 1 ) 汉语句子由汉字符串组成，字与字之间无空格； ( 2 ) 一个词在不同的上下文中具有多个不同的语法功能； ( 3 ) 汉语没有屈折变化形式的标志； ( 4 ) 构词规则可由很多不同的句法类型来实现； ( 5 ) 线性词序相对自由任意： ( 6 ) 词的语义复杂，多音词广泛存在； ( 7 ) 汉语中的词基本上没有词型标志； 。 这些特点对汉语的分析造成了一定的影响，使得汉语分析呈现出和英语( 以 及其它一些语言) 不同的特点。从汉语与其它语言的不同我们可以分析得到汉语 的句法分析所遇到的困难： ( 1 ) 汉语缺少形态标志，汉语的句子组成通常依赖虚词和词序，而不靠形 态变化。但是虚词在很多场合下并不是必不可少的，常常被省略掉；而灵活的 7 天津师范人学硕上学位论文第一章引言 词序又使得汉语的词类与句子成分之间不存在简单的一一对应的关系。结果， 汉语中的同一个句法成分可以由属于不同词类的词来充任，同一个词在句法结 构中又可以作不同的句子成分，形式上却没有任何不同的标志。因此，汉语的 词性兼类问题更为突出、更难解决。 ( 2 ) 词语边界识别是汉语句法分析首先要解决的问题。由于汉语的书写习 惯是基于字的，在汉语文本中，词与词之间除了标点、分段等符号外，没有其 它显性的界限标志。要分析汉语的句法结构，第一步要做的就是如何识别词语 的边界。 ( 3 ) 如何在句法歧义消解中引入词汇，特别是语义信息。上述分析表明， 汉语句法结构歧义产生的根本原因之一就是句法分析中缺乏足够的语义信息。 因此，引入语义模式是解决汉语句法歧义的重要途径之一。 ( 4 ) 知识获取问题是汉语句法分析实现大规模开放应用的瓶颈之一。汉语 可以利用的语言资源相对匾乏。同英语相比，汉语语言资源包括可计算的机器 可读词典( m i m ) 和熟语料建设相对滞后，特别是经过句法标注的大规模汉语树 库，这在一定程度上阻碍了汉语句法分析的发展。 1 8 课题背景 本文是属于机器人辅助打台球的一部分，在实现机器人打台球的工作中， 怎么样让机器人与人进行交流和沟通，是我们需要解决的一个问题。 机器人本身并不可能像人一样思考，所以要想实现机器人与人之间的交流， 首先得让机器人理解自然语言，即我们所说出得汉语。汉语是一种分析型语言， 汉语的分析过程是一个语法知识、语义知识以及常识性知识公用的过程。如何 在语料中表达句子中蕴涵的复杂知识，如何使机器学习的方法获取这些复杂的 不同层次的知识，并把它应用于句法分析成为了一个热点问题。 可见，句法分析在自然语言处理领域中具有十分重要的地位，句法分析的 好坏影响了句子进行语义的分析。因此，围绕着句法分析的系统实现成为了本 天津师范人学硕士学位论文第一章引言 文研究的主要内容。 1 9 本文的研究方法以及研究思路 本文的内容组织如下： 第一章对自然语言处理的概念、特点，句法分析的发展概况及其所遇到的 困难做了详细的介绍。 第二章比较了几种不同的句法分析方法，详细介绍了形式语法体系。 第三章句法分析模型的分析算法，详细介绍了c h a n 算法及其不足。 第四章汉语句法分析模型，详细介绍规则库的构建，以及正则表达式在规 则库中应用。 第五章句法分析系统的总体结构设计，对实现系统的整体结构设计的说明， 以及设计原则和实现的关键技术的介绍。 第六章结论和展望，对本文做的工作的总结和对未来的展望。 9 天津师范人学硕士学位论文第二章句法分析相关技术 第二章句法分析相关技术 2 1基于转移网络的自动句法分析【9 】 自动句法分析中使用的转移网络主要有递归转移网络和扩充转移网络，本 部分介绍这两种转移网络的基本原理以及它们在句法分析中的应用。 ( 1 ) 递归转移网络( r 1 n ) 。是对有限状态转移网络的一种扩展，在r 1 n 中每条弧的标注不仅可以是一个终结符( 词或词类等) ，而且可以是一个用来指明 另一个网络名字的非终结符。 说明： a r 1 附中任何一个子网络都可以调用包括它自己在内的任何其它子网络。 b 从生成能力来看，递归转移网络等价于上下文无关语法。 例如： 1 一，脾归s 卫 s 舻哆 n p弘。 图2 1r 1 n 递归转移网络 算法描述基本概念 子网名称：s ，n p v p 等： 状态节点：g o ，口”9 2 ； 出边：从当前状态向下一个状态转移的弧； 待分析字符串：w 2w 3 ； 递归栈：记录来自哪个子网，以及回到上层子网时应处的状态； 1 0 们rv 胪 ， 归 护 y 哆 哆 嗲 咿 咿 咿 毛 夏 毛 天津师范人学硕二l 学位论文第二章句法分析相关技术 当前状态： ( 2 ) 扩充转移网络。扩充转移网络( a 1 n ) 这种形式体系是1 9 7 0 年w w o o d 提出来的，并曾成功地应用于他的著名的l u n a r 系统中。a 1 n 语法属于一种 增强的上下文无关语法，它的基本思想是继续采用上下文无关语法来描写句子 的成分结构；但对语法中的个别产生式增添了某些功能，主要是描写某些必要 的语法限制和建立句子的深层结构。 a 1 n 在以下三方面对r t n 作了扩展和增强： a 添置了一组寄存器( r e 百s t e f s ) ，用来存储分析过程中得到的中间结果( 如局 部句法树) 和有关信息( 如名词短语的人称和数，某些成分的语义特征等) 。但设 置哪些寄存器完全取决于句法分析的需要，并没有硬性的规定； b 每条弧上除了用句法范畴( 如词类和短语标记) 来标注以外，可以附加任意 的测试( t e s t ) ，只有当弧上的这种测试成功之后才能通过这条弧； c 每条弧上还可以附加某些动作( a c t i o i l s ) ，当通过一条弧时，相应的动作便 被依次执行，这些动作主要用来设置或修改寄存器的内容。 2 2 基于上下文无关语法的自动分析【1 o 】 2 2 1 形式语言理论 形式语言学，也称代数语言学，它研究一般的抽象符号系统，运用形式模 型对语言( 包括人工语言和自然语言) 进行理论上的分析和描写。 在形式语言理论中，语言被看成是一个抽象的数学系统。乔姆斯基把它定 义为：按一定规律构成的句子或符号串的有限或无限的集合。 如何来描述一种语言? 有三种途径： ( 1 ) 把语言中的句子穷尽地枚举出来。如果语言中地句子数目是无限的， 用简单枚举的办法行不通。 ( 2 ) 文法一用来生成语言中无限的句子，而且只生成那些“合格的旬 天津师范人学硕：l 二学位论文第二章句法分析相关技术 子。 ( 3 ) 自动机能够对输入的语言符号序列进行检验，区别哪些是语言中 的句子，哪些不是语言中的句子。 由此，刻画某类语言的有效手段，是文法和自动机。文法用来生成语言的 句子，自动机用来识别语言的句子，就描述一种语言而言，两者是统一的。 2 2 2 形式语法 对下面的句子，如果用直接成分分析法予以切分，并对切分的结果作出结 构上的描写，就会得到图2 2 。 它表明，句子由名词短语和动词短语两部分组成，动词短语由动词和名词 短语组成，名词短语由名词组成。 爸爸 1 名词 1 名词短语 懂 动 计算机 1 名词 动词短语 句子 图2 2 句子“爸爸懂计算机”的直接成分分析结果 这个过程也可以表述为以下的形式： 句子一名词短语+ 动词短语 名词短语一名词 1 2 语 天津师范大学硕上学位论文第二章句法分析相关技术 动词短语一动词+ 名词短语 名词一爸爸 名词一计算机 动词一懂 这是一个普通的语法分析的例子。在整个分析过程中，有四个方面的内容： ( 1 ) 句法范畴，例如名词短语、动词短语、名词、动词等。它们表示句法 单位的类别。 ( 2 ) 词，例如爸爸等。它们是句子切分的最终成分。 ( 3 ) 句法成分之间的相互关系，例如句子一名词短语+ 动词短语等。 ( 4 ) 在句子分析中，“句子这个句法范畴跟其它句法范畴相比，具有独 特的意义，它是句子切分和分析的出发点。 2 2 3 形式语法的定义【1 1 】 一种形式语法g = ，其中，s 表示起始符，表示非终端 语符集，巧表示终端语符集，p 表示重写规则集，由有限个规则组成。 句子：由语法g 。从起始符s 可派生出来的终端语符列就构成了由g 0 生成的 句子。 语言：所有由语法g o 从起始符s 可派生出来的终端语符列就构成了由g 。生 成的语言。 2 2 4 乔姆斯基层级和自然语言 文法、自动机和语言的关系，如表2 1 所示： 天津师范大学硕上学位论文第二章句法分析相关技术 表2 1 文法、自动机和语言关系 类型 文法 自动机语言 0 型无约束短语结构文法图灵机递归可枚举语言 1 型上下文有关文法线性有界自动机上下文有关语言 2 型 上下文无关文法下推自动机上下文无关语言 3 型正则文法有限自动机正则语言 哪一种语言最宜于用来生成自然语言的句子? ( 1 ) o 型文法一生成能力过于强盛 由o 型文法生成出来的句子集合称作“递归可枚举语言。而自然语言是递 归语言，因为任何说本族语的人由他们具有的语言直觉能判断出哪些是合格的 句子，哪些是不合格的句子。 所谓的“递归可枚举语言，是指一个语法装置，经过若干个操作后，它能 确定属于这种语言的句子。对不属于这种语言的句子，它或者被“堵塞 ，或者 永不休止地转下去。可见，o 型文法的产生式几乎没有什么限制，它的生成能力 太强，会生成难以数计的不合格句子。所以用o 型文法来描述自然语言，必须 施加某些限制条件。 ( 2 ) 3 型文法一不足以担负起描写自然语言的重任 3 型文法的特点是它生成句子时是严格的顺着一个方向扩展的。由于在派生 过程中，每一个层次上最多只能在右端出现一个非终端语符，因此这类语法在 扩展中每一个阶段只能记住一个步骤的内容。 3 型文法不能担负起描写自然语言的重任是因为在自然语言中，常有成分和 成分之间有着句法形态上的依赖关系，但在句子上它们不一定是线性前后相续 的成分。由于3 型文法的“记忆”太狭隘，它只能记住一个步骤的内容，所以 它不能描述这样的句法依赖关系。 ( 3 ) l 型文法( 上下文有关文法) 上下文有关文法的生成能力比上下文无关文法的生成能力强。但是，通常 1 4 天津师范大学硕：i j 学位论文第二章句法分析相关技术 上下文有关文法将使语法定义变得更加烦琐，且一般不能高效的分析。对于上 下文有关语言类，除了其特殊情况上下文无关子类外，还不知道有哪些子集能 容易地进行分析。而上下文无关文法可以采用乔姆斯基范式这一有力的手段来 实现层次分析，把上下文有关的限制包含在非形式描述的全局语法和语义定义 中。所以，在自然语言描写中，人们还是愿意采用上下文无关文法。 ( 4 ) 2 型文法( 上下文无关文法) 能担负起描写自然语言的重任 2 型文法能处理具有嵌进结构的句子，并且乔姆斯基证明，任何上下文无关 文法，均可由产生式a _ b c 或a _ a 的文法生成，其中，a ，b ，c 矿，a 矿 l 即上下文无关文法具有乔姆斯基范式。利用上下文无关文法的这一性质， 可把上下文无关文法的推导树变成二叉的推导树。而自然语言的结构一般也是 二分的，所以上下文无关文法能够担负起描写自然语言的重任。 上下文无关文法的相关算法有e 砌e y 算法、花园幽径句的自动分析算法、 c y k 算法、富田算法、浅层句法分析。本系统采用的c h a n 算法，具体内容在 第三章介绍。 2 3 基于特征结构的自动句法分析【1 5 】 一个特征结构( f e a t u r es 仃u c t u r c ，f s ) 是一个特征描述二元组 ，其中前一项称作“特征名 ( 或“属性 ) ，后一项称作“特征值 ( 或“属 性值”) 。“特征名是一个字符串，“特征值”可以是一个字符串值或数值等原 子值类型( a t o m ) ，也可以是另一个特征结构，这就是所谓的特征结构的“嵌套 ； 两个特征可以共享一个值，这是所谓的特征值的“共享”。“嵌套 与“共享”( 也 有人称为“重入 ) 是“特征结构”的两个主要性质。 一个复杂特征结构( c o m p l e xf e a n 鹏s t m c t u r e ，c f s ，也称复杂特征集) 是 由一个以上的特征结构组成的特征结构列表( 1 i s t ) 。 复杂特征集的形式定义： q 为一复杂特征集，当且仅当q 可用 1 5 天津师范人学硕，l 二学位论文 第二章句法分析相关技术 2 4 基于依存语法的自动句法分析【1 6 】 依存语法也是一种使用非常广泛的语法形式。 与短语结构语法( p s g ) 的最大不同在于，依存语法的句法结构表示形式不是 1 6 天津师范大学硕士学位论文 第二章句法分析相关技术 一棵句法层次结构的句法树，而是一棵依存树。依存树上的所有结点都是句子 中的词，没有非终结符结点。例如句子“台球运动是一项竞技性运动 的依存 结构如图所示： 图2 4 依存结构图 可以看到，在依存关系树中，丢失了句子中词与词之间的顺序关系。 应该说，依存语法并不是一种严格定义的语法形式。依存语法没有明确定 义的规则形式，也没有明确规定依存关系是否要加上标记。实际的应用系统中， 一般都会给依存关系加上句法或语义的标记。 1 9 7 0 年，美国计算语言学家j 罗宾孙( j r b o i i l s n o ) 提出了依存语法的4 条公 理： ( 1 ) 一个句子只有一个成分是独立的； ( 2 ) 句子中的其它成分直接从属于某一成分； ( 3 ) 任何一个成分都不能从属于两个或两个以上的成分； ( 4 ) 如果成分a 直接从属于成分b ，而成分c 在句子中位于a 和b 之间， 那么，成分c 或者从属于a ，或者从属于b ，或者从属于a 和b 之间的某一成 分。 这四条公理比较准确界定了一个依存树所要满足的条件，得到了依存语法 研究者的普遍接受。 1 7 天津师范人学硕士学位论文第二章句法分析相关技术 2 5 基于概率的自动句法分析【1 7 】 在自然语言的计算机处理中，基于规则的句法剖析主要是使用乔姆斯基的 上下文无关语法。近年来对上下文无关语法的改进主要是给上下文无关语法的 规则加上概率，提出了概率上下文无关文法。 2 5 1n 元文法模型 卿呆1 阪疋，征一个语，口j 甲弟1 个侧出士见阴概率，条件地依赖十。已刚回的n 一 1 个词，即将一个词的上下文定义为该词前面出现的n 1 个词，这样的语言模 型就叫做n 元文法统计模型( n 一伊锄) 。设符号串s 由l 个符号h ，w 工 组成，s 发生的概率为 p s ) = p w i h ”w 3 1w 2 少p w 三”) = 向p ( w l ” n 元模型假设每个词w 的出现只与它前面相邻的n 1 个词形1 ) 形一。有 关，即郴2 血p 1 w 1 w f - l = p w l p w 21w ik p w 一ilw l h 一2 向p 1w l w 一- n 元樟型相当千n 一1 阶马尔可夫樟型 2 5 2 隐马尔可夫模型( h m m ) h m m 是马尔可夫的扩展，观察序列是状态的概率函数。它是一个双重随机 过程。 h m m 的形式化描述是h m m = ( s ，0 ，a ，b ，兀) 。 ( 1 ) n ，代表模型的状态数。在实际应用中，通常采用了对模型中的状态 集赋予一定的物理意义。这些状态是相互联系的，可以从一种状态转移到其它 天津师范人学硕上学位论文第二章句法分析相关技术 状态。状态集定义为s 2 s ，s ：，乱) ， t 时刻的状态为q t ( 2 ) m ，每个状态下不同的观察符号的数目。观察符号记为w 2 彬， ，) 。 ( 3 ) 状态转移概率分布a 。 口甜) ， 其中口驴2 p ( g = s i 吼2s ，) ，1 s i ，j sn ，口表示从状态i 转移到状态j 的概率，满足：口矿芝o ，v f ，j ，且y4 ，= l ，v f 。 7 ( 4 ) 观察值概率分布b 2 乃( k ) ) ，其中乞( k ) 表示在状态j ，下，时 刻出现的概率，即岛( k ) = p ( 在。时刻出现i 吼= j ，) ，1 s j sn ，1 sksm ， 6 ，( k ) 满足：6 ，( k ) 芝0 ，k ；且y6 ，( k ) = 1 ，w 。 7 厶 。 七 ( 5 ) 初始状态分布矢量兀= 五，其中7 c i = p ( ，= 。) ，l si5n ，即在仁1 叶o ； 时刻处于状态_ 的概率。i 满足：丫7 c i = l 。 2 5 3 统计决策树的语言模型( s d t ) 统计决策树通常包括两种类型的节点：中间节点和叶节点。每一个叶节点 包括唯一的概率分布，而每一个中间节点包括关于上下文的一个提问。一棵决 策树是一个“提问回答 机制：对一个事件，经过一系列的“提问回 答 逐步减少问题的不确定性，从而做出正确的决策，其中当前的提问与以前 的回答有关。给决策树的每个分枝赋一个概率值，就形成s d t 模型，与s d t 模 型相似的语言模型还有基于转换的语言模型。 1 9 天津师范人学硕： ：学位论文第二章句法分析相关技术 2 5 4 概率型上下文无关文法( p c f g ) 概率型上下文无关文法是一个结构化的概率型语言模型，它是上下文无关 文法( c f g ) 的一种扩展。如果c f g 的每一条规则与一个概率相联系，就构成 p c f g 。p c f g 是一个四元组，即：g = ，其中n 为非终结符集， t 是终结符集，p 是产生式集合，s 是丌始符。 产生式集合p 中的产生式形如a a ，p 。显然有f p ( ai a ) = 1 。 z 二一a 概率型上下文无关文法产生句子是从符号s 开始的，这和非p c f g 是相同 的。但是p c f g 的优点是在推导树产生的每一步都可以计算概率，这样可以量 化句子。概率型上下文无关文法的优点在于赋予每棵分析树一个概率，当句子 具有结构歧义时，可以利用该概率来选择句子的分析结果丁，即r = a r g m a x p ( d 。 分析树t 的概率就是生成t 所用到的所有产生式的条件概率的乘积： p ( d 2 兀p ( r ) ，e d ( n 其中，r 是产生式，d ( t ) 表示用于生成分析树t 的有序产生式集合。 2 0 天津师范火学硕士学位论文第三章句法分析模型的分析算法 第三章句法分析模型的分析算法 本章介绍课题中的c h 硪算法。自然语言的处理中，歧义的处理能力和分析 效率是评价句法分析系统的重要指标。因此，在我们基于规则的句法分析的系 统中，所设计和实现的算法是在综合考虑这两个因素的前提下提出的。 3 1一个简单的文法 c h a r t 分析算法是句法分析最通用、简单、直观的算法。c h a n 分析算法就是 一组结点和边的集合。 考虑一个句子：台球运动是一项竞技性运动。 规则库中的词条有： ( 1 ) n 一台球l 竞技性 ( 2 ) m 一一 ( 3 ) q 一项 ( 4 ) v 一运动l 是 所使用的规则为： ( 1 ) s _ n pv p ( 2 ) n p n p v p ( 3 ) n p _ n ( 4 ) v p v ( 5 ) v p _ v pn p ( 6 ) n p _ d pn p ( 7 ) d p - mq c h 抓是c h a r t 算法中最重要的数据结构。它是把词与词之间的间隔作为结 点，把词和短语当作连接结点的边。例如“台球运动是一项竞技性运动。这个 句子可以用c h a n 表示为： 2 l 天津师范人学硕七学位论文第三章句法分析模型的分析算法 s 呻n pv p 图3 1 c h a r t 的表示法 在图3 1 中，我们不仅标出了每条边的标记，还标出了产生该边的规则。 3 2 活跃边与非活跃边【1 9 1 我们注意到，在前面我们所举的例子，“你打红球边上的粉球。一和“你打 红球”都是由规则s _ n pv p 生成的，而且其中“n p 都是对应同一个结点 ( “你”) 。也就是说，这两次规则使用的过程中，有一个冗余的操作：将规 则右部的第一个结点n p 与同一个结点( “你 ) 进行匹配。如果规则很多，c h 矾 的结构很复杂，这种冗余是很严重的。那么，我们能不能消除这种冗余操作昵? 答案是可以。在c h a n 算法中，将边分为两种，一种叫做非活跃边，就是上图中 我们已经见过的这种边。另一种叫做活跃边，用于记录一条规则部分被匹配的 情形。于是，规则s _ n pv p 生成结点“你可以打红球 的匹配过程可以记录 为两条活跃边和一条非活跃边。 其中“匹配程度用规则中加入句点来表示，即用点规则来表示。所谓点 规则，是在规则的右部的终结符或非终结符之间的某一个位置上加上一个圆点， 表示规则右部被匹配的程度，其中圆点的位置表示规则已经匹配成功的位置( 从 左边开始) 。 天津师范大学硕上学位论文第三章句法分析模型的分析算法 表3 1c h a r t 的匹配过程 记录方式边状态匹配程度起点终点对应词串 活跃s 一n pv p 00 活跃 s ，n p v p0l 你 非活跃 s - n pv p 03 你打红球 用c h a n 表示如下： s 一n pv p 3 3 日程表( a g e n d a ) 图3 2c h a n 的点规则 在c h a n 算法中，还有一个重要的数据结构，称为“日程表( a g e n d a ) ”。 c h a n 分析的过程就是一个不断产生新的边的过程。但是每一条新产生的边 并不能立即加入到c h a n 中，而是要放到日程表( a g e n d a ) 中。 日程表( a g e n d a ) 实际上是一个边的集合，用于存放已经产生，但是还没 有加入到c h a n 中的边。日程表( a g e n d a ) 中边的排序和存取方式，是c h a r t 算 法执行策略的一个重要方面。 3 4c h a r t 算法的基本流程 c h a n 算法就是一个由日程表驱动的不断循环的过程： ( 1 ) 按照初始化策略初始化同程表( a g e n d a ) ； 天津师范大学硕- j ：学位论文 第三章句法分析模型的分析算法 ( 2 ) 如果日程表( a g e n d a ) 为空，那么分析失败； ( 3 ) 每次按照日程表组织策略从日程表( a g e i l d a ) 中取出一条边； ( 4 ) 如果取出的边是一条非活跃边，而且覆盖整个句子，那么返回成功； ( 5 ) 将取出的边加入到c h a n 中，执行基本策略和规则调用策略，将产生的新 边又加入到同程表( a g e n d a ) 中； ( 6 ) 返回第( 2 ) 步。 在这个过程中，各项基本策略都是可以调整的，通过调整这些策略，可以 得到改进的c h