基于自动机的汉语句法分析系统的研究09.1..doc

基于自动机的汉语句法分析系统研究摘要Abstract第1章 绪论1.1. 本文研究的目的和意义要使计算机与人能够通过自然语言进行交流，就要使计算机能够理解和运用自然语言，自然语言处理技术就是几十年来人们在这个方向上不断努力的产物。1句法分析是自然语言处理的一个基本问题。许多自然语言处理任务，比如机器翻译、信息获取、自动文摘等都要依赖句法分析的精确结果才能最终获得满意的解决。随着信息社会的到来，人们对自然语言处理的需求日益迫切，因而对句法分析的研究具有重要的实际意义。同时，句法分析中所使用的技术也有助于解决生物信息识别等与句法分析相似的问题。另一方面，语言是人类思维的载体，对自活语言的研究有助于研究人类智慧的本质，在处理语言的过程中，句法分析也是人们所面临的一个基本问题。因此对自然语言句法分析的研究具有重要的理论价值和深刻的哲学意义。本文的目的在于实现一个基于形式语言与自动机的汉语句法分析系统，并在该系统上研究句法消歧方法，以提高汉语句法分析的效率。1.2. 句法分析方法综述1.2.1. 基于规则的方法20世纪50年代末乔姆斯基的文法理论的提出，奠定了基于规则方法的基础。在此后30多年的时间里，出现了一些有影响力的基于规则的系统，例如早期的BaseBall系统、SIR系统、STUDENT系统以及后来的转移扩张网络法等。在中文处理方面，（Zhou，2000）3提出了一种典型的基于规则的句法分析方法。该方法采用短语结构的局部分析和依存分析相结合的方法。在句法分析的过程中，首先通过短语分析来对句子进行适当地抽象，减少处理时的句子结点数目，最后通过手工书写的规则来进行依存分析。他共定义了11类短语和17类依存关系，制定了1000多条短语识别规则和300多条依存分析规则。基于规则的方法主要通过人工组织语法规则、人工建立知识库，解决句法结构歧义的方法是通过一些条件约束和检查来实现的（Allen，1987）4。这种基于规则的方法在某一限定领域的应用是可行的。然而，规则方法本身存在着较大的缺陷，主要表现在：1.规则刻画的知识颗粒度过大，无法使用有限的规则来刻画几乎是无限的自然语言现象，而且很难处理自然语言结构的不确定性。2.不能保证各种自然语言规则间的相容性和一致性，随着系统中规则数量的增加，规则之间常常会发生矛盾和冲突。3.规则的获取是一个十分繁琐的过程，它完全依赖于开发规则的工程师的语言知识和经验，因此获取一套完整而周详的大规模语法规则非常艰难。基于上述原因，单纯使用规则方法无法解决处理大规模真实文本时自然语言的高度复杂性和歧义性。因此，进入20世纪90年代以后，句法分析的主流方法己从规则方法转向以统计方法为代表的经验主义方法。1.2.2. 基于统计的方法统计方法以数学模型和大规模语料库为基础，其核心思想是建立数学模型以表述某一种语一言现象，然后在大规模语料库中对模型进行训练，使其满足己经获知的经验知识，然后用训练好的模型对于未知的现象进行预测。几乎所有基于统计的方法都可以归结到上述的框架中去。与传统的基于规则的方法相比，统计方法有下述优点：1.它不依赖于人主观的先验知识，这也是本文认为统计方法最重要的优点。大规模语料库实际上和规则一样，都是一种知识的表征形式，不同的是语料库相比规则而言，有更强的独立性和客观性。2.统计方法将知识和算法分离。前面己提过，规则往往是由某方面的专家针对某一特定的应用所书写的指导原则，而同一个语料库可以为多种算法、多种应用服务，它是很独立的知识库。这样语料库的建立和完善可以和算法的设计并行，不仅节省了人力物力，也给一些标准化测试提供了基础。另外这项优点给基于统计方法的系统的维护和更新带来了很大的方便。随着应用的扩展，我们往往要考虑到新的语言现象，这时基于统计方法的系统只需要用更大的语料库重新训练一下模型就可以了，而基于规则的方法则需要增加大量的规则，而如上文以前提过的，这并非一件容易的事情。3.统计方法通过语料库给每条语言规则加上概率值，使得语言规则的使用便有了“柔性”，不再是“说一不二”、“非此即彼”。近十几年来，随着计算机硬件设备的飞速发展，其单位存储和计算成本大幅度降低，使一些基于大规模搜索和迭代的复杂算法能够在个人计算机上广泛地实现和应用；而随着行业信息化的普及和网络资源的迅猛膨胀，可用语料资源也大为丰富，这一切给基于大规模语料库的统计自然语言处理方法的实现提供了必要的硬件和软件环境。在这种条件下，大规模地收集语料并用计算机处理成为可能，语料库的建设和语料库语言学成为计算语言学新的分支而迅速崛起。作为统计句法分析基础的树库的建设也获得巨大的发展。在英语方面，以美国宾夕法尼亚大学开发的宾州树库（Penn treebank）较为著名，该树库从1991年第一版发布以来的十余年时间里，经过不断地维护和修正，目前己达到几百万字的规模，被公认为具有较高的一致性和标注准确性，是目前研究英语句法分析所公认的标注训练集和测试集。在汉语方面，中文的树库建设在近年来也到了广泛的重视和巨大的发展。如美国宾夕法尼亚大学的宾州中文树库，目前发布的树库规模为10万汉语词。台湾中研院的中文句结构树库，增加了对句子语义信息的描述，如句子的施事（Agent）和受事（Patient）等，目前发布的树库规模为约24万汉语词。由中文语言资源联盟（Chinese LDC）建设的树库（TCT 973）的规模为100万汉字，是到目前为止规模最大的中文句法树库之一（http：//）。大规模树库的建设和发展为统计句法分析提供了很好的知识获取来源和测试平台。当前，大多数成功的统计句法分析方法都是利用语料库来获得分析所需要的知识。其基本思想是：1、使用语料库作为唯一的信息源，所有的知识（除了统计模型的构造方法）都是从语料库中获得的。2、语言知识在统计意义上被解释，所有的参量都是通过统计处理从语料库中自动习得的（周强，1996）5。概率方法的广泛应用是统计方法的显著特点之一。概率方法的本质就是利用不同语言现象的统计分布来描述语言使用的一般模式，并由此选择输入句子的最可能的分析结果，更适合大规模文本的自然语言句法分析。根据采用信息的不同，可以把统计方法分为下面五类。. 概率上下文无关文法概率上下文无关文法（PCFG）模型是最典型的一种基于结构的概率方法。20世纪80年代以来，国内外学者对PCFG进行了深入的研究，包括对PCFG参数的推导和学习以及分析算法的研究。国外的研究起步较早，研究得也比较广泛。（Lari et al.,1990）6首先采用Inside-Outside算法自动估计PCFG参数；（Black et al., 1992）7等人以自底向上的CKY算法总结出PCFG的各种算法，包括Inside-Outside算法、Viterbi算法等；（Stolcke，1995）8将Earley算法与PCFG结合，给出了概率化的Earley算法。此外，（Corazza，1994）9对如何利用PCFG进行句法分析和计算句子的概率进行了深入细致的研究。国内的很多学者对PCFG用于汉语句法分析也做了大量的工作。（王挺，1997）10和（周强，1998）11用Inside-Outside算法研究了汉语的PCFG自动推导，在匹配分析机制上实现了无指导的EM 迭代训练算法。（朱胜火等，1998）12对原有的GLR分析表加以改造，能够利用分析过程的控制结构来计算有关的概率，实现了一种有效的概率上下文无关文法的分析算法。虽然PCFG具有形式简洁、参数空间小和分析效率高的优点，但是它忽略了消歧所需的上下文信息，因此其消歧能力有限。针对PCFG的问题，出现了下面几种模型：增加结构信息的概率模型，包含词汇依存关系的概率文法，引入语义信息的模型和依据历史的模型，分别在下面几节详细介绍。. 增加结构信息的模型实验表明，结构信息的引入有助于提高句法分析的结果。（Briscoe et al .,1995）13将合一语法同概率广义LR表（Probailistic Generalized LR）算法结合，以增加PCFG的上下文描述的能力。（Simmons et al.,1992）14首次提出上下文依存文法（the Context-Dependent Grammars，CDGs），并基于CDG针对英语受限子集实现了一个英语句法获取和分析系统。（Schabes，1992）15提出了一种概率树邻接文法（Probabilistic Tree-Adjoining Grammars， PTAGs）。这种文法在上下文无关文法中的标准替换规则的基础上，增添了一种附加原则，以提高规则的上下文敏感性，并且还改进了Inside-Outside算法使之能无指导地估计PTAG概率。（Su et al.,1995）16提出了一种基于简单上下文相关文法的编凡模型，该模型将归约项目左边M个符号和右边N个符号作为规则的上下文，同时认为紧随移进的归约动作是高度相关，而不考虑相邻动作的约束。面向数据的句法分析技术（DOP）由（Bod et al.,1997；2003）17,18首先提出，后逐渐深入和发展。该处理技术建立在包含大量语言现象的树库基础上。把经过标注的树库看作一个语法，从树库中抽取部分树并构造一个部分树的数据库。当处理新的语言现象时，通过重新组合这些部分树的方式来构造句法分析树。DOP方法与人们对句法分析的直觉相一致，但对给定的句子，其推导的搜索空间与句子长度成指数增长。Bod应用MonteCarlo技术在多项式时间内找到最优的句法树，但实际的句法分析的时间消耗仍然很大。在国内，张浩，2002）19研究了PCFG独立性假设的局限性，并在PCFG的基础上提出了三个逐层递进的与结构上下文相关的概率句法分析模型，它们考虑了分析树当中每个派生结点的结构上下文条件。（孟遥，2003）20设计了一个包含复杂特征的统计句法分析模型，综合考虑了上下文无关规则的结构特性、所处的上下文环境即复杂特征信息。. 基于词汇的概率方法基于词汇的句法分析方法根据包含在句子中的词的特性来区分句子的不同句法分析候选。基于词汇的句法分析的一种思路是考虑词汇之间的搭配关系，某些词的某-特殊组合比各自的其它偶然出现的组合更容易在句子中出现，也就是说，这些词汇的同现概率比较高。同现概率越高的词汇，越容易出现在同一句法结构中。这种同现关系通常采用互信息进行量化。（Magerman et al.,1991）21提出了一种基于广义互信息模型的短语自动划分算法。它依赖于下面的一个假设：给定句子中的短语成分边界可以通过分析句子中词类n-gram组合的互信息值加以确定。它的实验结果说明：这种方法对于短句的分析效果较好，而对并列结构以及长句子的分析则不够理想。然而，单纯依靠词性信息很难获得理想的句法分析结果。因此，将词汇语法理论和概率结合产生出词汇语法的概率版本是件很自然的事情。（Alshawi et al.,1996）22提出了一种基于核心词的概率句法分析模型，他认为一棵句法分析树山核心词及它的左右修饰成分组成。（Goodman，1997）23在概率上下文无关文法中引入了复杂特征，他规定所有规则前项只有两个结点，即二分形式的规则。每个非终结结点由一组属性一值对表示，允许表示词汇的合一关系，以及远距离的依赖关系。（Collins，1999；Chamiak，1997a；1997b）24,25,26等人采用中心词驱动的概率模型的方法，是近年来句法分析词汇化的典型代表。其基本思想是：句子是围绕着中心词来组织的，规则中的每一个非终结符结点与其核心词相联系，通过规则的概率体现核心词之间的依存关系。Collins于1999年得到的句法分析结果是目前公认的英语的最好结果之一。本文将在第四章详述这种模型的构造思想。在汉语方面，（Bikel，2000）27在4000句宾州中文树库上实验了Collin，的头驱动句法分析模型和一个概率TAG句法分析模型的汉语句法分析效果。（付国宏，2000）28结合汉语的特点，把语义信息引入到汉语句法分析中，提出了一个基于词义的概率上下文文法（LPCFG）的汉语句法分析模型，构造了一个以词义搭配模式为品质因数的Best-First线图算法。. 基于历史的模型基于历史的文法最早由（Black et al.,1992）7提出，其核心思想是把句法分析过程看作自顶而下、从左向右的非终结结点的扩展过程，非终结结点的扩展相当于一系列的产生式使用过程，产生式的概率依赖于句子中当前分析点的整个分析历史。（Jelinek et al.,1992）29描述了一个相似的历史模型，不同在于Black采用的是手工书写的规则，而Jelinek采用的规则是从树库中自动提取的。（Magerman，1994；1995）30,31是Jelinek工作的延续，他采用的决策树方法使得系统性能得到了较大提高。（Ratnaparkhi，1997）32采用最大熵的方法构造了一个基于历史的模型。. 语义辅助的句法分析模型语义辅助的模型把语义信息引入到句法分析模型当中。（Sekine et al.,1992）33描述了一个由语义辅助的句法分析器，它分析的过程考虑由核心词、语法关系以及谓词 论元所组成的三元组。（Jones et al.,1992）34设计的句法分析器在扩展结点的过程中不仅计算了规则的句法概率，而且考虑了其语义概率，语义以谓词论元的形式表示。（Alshawi et al.,1994）35描述的句法树由语法关系、属性以及语义搭配等组成，并给出了多个句法分析结果。综上所述，句法分析的研究表明，句法结构歧义的消除必须依赖多种信息，句法分析过程中的上下文结构信息，词汇信息以及语义信息都有助于歧义结构的消解。但如何很好地综合利用这些信息，需要根据所处语言的特点以及资源情况而定。1.3. 汉语句法分析研究现状1.3.1. 汉语的特点汉语有一个显著特点，即较为灵活。有人把世界上的语言分成孤立语、曲折语、粘着语、复杂语四种类型，汉语是孤立语的代表，孤立语的主要特征是缺乏词形变化，语法规则较灵活。汉语灵活的特点增加了汉语语言处理的难度。汉语的书面形式是连续书写的，词与词之间没有自然的界限，对汉语的分析首先要解决单词的切分问题。汉语是一种分析型语言，语义在汉语分析中起着举足轻重的作用。与俄语和英语相比，汉语在句法分析中需要更对的语义知识帮助消歧。朱德熙先生认为，汉语的语法体系与印欧语法体系是不同的。印欧语法体系中从词到短语是组成关系，而从短语到句子则是一种实现关系。汉语的语法学界对短语和句子的分界较为模糊，不少著作认为，短语和句子有一套共同的结构规则，短语加上一定的语调就成为句子。汉语缺少从词到短语再到小句最后组成句子的这种清晰的层次结构，在短语分析是将面对与整句分析同样困难的问题。21.3.2. 汉语句法分析面临的问题如前文所述，目前己知最好的汉语句法分析效果同其他西方语言相比还有一定的差距。而造成这种差距的主要原因之一是汉语语言本身的特点增加了对其进行分析的难度。汉语句法分析的主要困难可以总结为如下几点：1.汉语的词性兼类问题非常普遍。汉语是一种孤立型语言，缺少形态标识，汉语的句子组成通常依赖虚词和词序，而不靠形态变化。但是虚词在汉语句子中并没有实际的意义，常常被省略掉；而次序又相当灵活，使得汉语的词类与句子成分之间不存在简单的一一对应关系，相同意思的句子就会对应多个结构，也就是多个词序的句子。所以，汉语中的同一个语法成份可以由属于不同词类的词来构成，同一个词在句法结构中又可以作为不同的句子成份。因此，汉语的词性兼类问题更为突出且难于解决（俞士汶，1998；赵铁军，2000）36,37。2.汉语句法分析存在着一个特殊的分词问题。由于汉语句子的书写方式是以字为单位的，在汉语文本中，字与字之间除了标点、分段等特殊符号外，没有其它明显的界限标志。句法分析主要是以词为最小单元进行处理的，因此在分析汉语的句法结构之前，首要的任务就是对汉语文本进行自动分词处理，其切分的好坏必然影响句法分析的效果。3.汉语句法结构分析歧义产生的一个重要原因是单纯依靠词类信息无法解决一些固有的歧义问题。引入词汇信息、语义信息是解决汉语句法歧义的重要途径之一。4.大规模、包含多种信息的知识库的建立是汉语句法分析实现大规模开放应用的瓶颈之一。由于汉语的复杂性和需要更多的预处理，目前己经建立的并可以利用的语言资源与英语相比，相对比较匾乏。汉语语言资源中可计算的完备的机器词典，尤其是大规模的语义词典和熟语料的建立相对滞后，这在一定程度上阻碍了汉语句法分析的发展。1.3.3. 汉语句法分析的发展趋势正如上述问题的存在，要彻底解决这些问题，并实现句法分析研究的最终目标还有很长的路要走。国内外学者们对此进行了不断的探索和研究，提出了在当前条件下解决上述问题的可能的方案和发展方向，主要可以归纳为如下几点：1.统计方法己成为主流技术，尽管英语方面出现许多较为成熟的统计模型，可以为汉语分析所借鉴，但汉语的语言特点使得研究人员在借鉴其优点的同时，还应该结合汉语特点进行特殊处理。2.实现多方法、多特征或多知识源相结合的混合模型。这是句法分析研究发展的必然，是为了更好地解决句法分析过程的歧义问题。大量的实验证明，单一方法、单一知识很难有效地解决句法分析歧义问题。PCFG模型在句法分析中得到广泛的研究，但是为了提高算法的分析能力，如何描述超出PCFG模型的上下文约束的概率模型是目前句法分析研究的热点之一（冯志伟，1996）38。3.句法分析算法是实现句法分析模型的基础，模型的可行性，最终由分析算法决定。因此，如何提高分析算法的效率，这是决定句法分析能否实际应用的关键技术之一。4.汉语是一种分析型语言，汉语的分析过程是一个语法知识、语义知识和常识性知识共用的过程，充分利用所有可能的复杂知识，通过书写包含语义或者语言学常识的规则，将基于规则的方法和基于统计的方法相结合成为句法分析研究的必然。1.4. 本文的主要研究内容鉴于汉语句法分析的重要性和现实意义，本文旨在实现并研究一个基于形式语言和自动机的汉语句法分析系统，并研究在句法分析中如何对句法的局部歧义进行消解，提出可行的句法消歧解决办法。考虑到自然语言要用计算机来处理，需要用形式语言来描述，该句法分析系统基于形式语言和自动机来实现，并采用自下而上的语法分析方法进行句法分析。为了消除局部句法歧义，我们在分析表中引入冲突处理机制。此外，我们采用概率上下文无关文法的思想，为语法分析生成的语法树添加特殊的概率属性，以指导句法分析。本文的结构如下：第1章绪论主要介绍了本文的研究目的和意义，以及句法分析现有的方法、研究现状和发展趋势。第2章主要介绍本文需要的形式语言与自动机相关的基础理论知识。第3章主要介绍句法歧义的消解，包括常见的句法消歧方法，和本文解决句法歧义问题的方法和策略。第4章主要介绍该汉语句法分析系统的设计与实现。第5章对实验的结果进行分析，得出结论。第6章是对本文工作的总结和对未来工作的展望。第2章 形式语言与自动机2.1. 引言 形式语言是描述自然语言的重要工具，用计算机处理自然语言，必须对自然语言进行形式化描述，所以形式语言在本文的研究中起到了重要的基础作用。自动机是抽象分析问题的理论工具，在本文中将被用于词法分析和语法分析当中。本章将简单介绍作为本文理论基础的形式语言与自动机的相关理论知识。2.2. 形式语言描述形式语言是用来精确描述语言（包括人工语言和自然语言）及其结构的手段。形式语言学也称代数语言学。下面是本文常用的几个概念和形式语言文法的基本类型：1.产生式产生式也称规则，它是一个符号与一个符号串的有序对（A，），通常写作 A其中，A是产生式左部，它是一个符号；是产生式右部，它是一个符号串；“”表示“定义为”或“生成”，意思是左部符号用右部的符号串定义或左部符号生成右部符号串。2.文法定义2.1.1 文法定义成一个四元组G=（VN，VT，S，P），VN：非终结符号集；VT：终结符号集；S：开始符号；P：产生式集合。其中：VN VT=，S VN。P中产生式的一般形式为：A| A VN ，（VN VT）*“”表示“定义为”，“|”表示“或者”，它们都是元符号。该产生式的意思是：A被定义为或，可用或替换A。3.乔姆斯基文法分类乔姆斯基把文法分为4种类型，并分别称之为0型、1型、2型、3型。0型文法0型文法的产生式有以下形式：其中，（VN VT）+，（VN VT）*，产生式的左部和右部都是符号串，对它们基本上没有限制。0型文法又称为短语结构文法，它识别符号串的能力相当于图灵机。任何0型文法所生成的语言都是递归可枚举的。反之，递归可枚举集必定是一个0型文法语言。1型文法1型文法又称为上下文有关文法，其形式如下：A其中：AVN；、（VN VT）* （VN VT）+。此处、被认为是A的上下文，A可以在上下文中被替换。对1型文法有一个要求，就是1=|A|=|，即产生式左部的长度必须大于等于1且小于产生式右部的长度。 2型文法2型文法即上下文无关文法，其形式为：A其中，AVN，（VN VT）+。3型文法3型文法也称为正规文法，它有两种形式形式1：A AB形式2：A AB其中，A、BVN，VT *，A、B是非终结符，是终结符串，形式1也叫右线性文法，形式2也叫左线性文法。2.3. 有限状态自动机1定义有限状态自动机简称有限自动机，是一种具有离散输入输出系统的数学模型。它是一个由一个带有读头的有限控制器和一条写有字符的输入带组成。如图所示，读头从左向右移动，每当读头从带上读到一个字符时，便引起控制器状态的改变，同时读头右移一个符号位。控制器包括有限个状态，状态与状态之间存在着一种转换关系。每当在某个状态读入一个字符时，便使状态改变为另一个状态。状态转换包括如下几种情况：转换到它自身，即保持原状态不变；转换的后继状态只有一个；转换的后继状态有若干个。如果一个有限自动机每次转换的后继状态都是惟一的，称它是确定的有限自动机（DFA）。如果转换的后继状态不是惟一的，则称为不确定的有限自动机（NFA）。通常把有限自动机开始工作的状态称为“起始状态”，把结束工作的状态称为“终止状态”或“接受状态”。 q0q5 q1 有限控制器q4 q2 q3a1a2a3ai输入头输入带图 DFA原理示意图下面给出确定的有限自动机和非确定的有限自动机的定义。定义2.1.2 确定有限自动机（DFA）是一个五元组M=（K，S，F）。（1）K是有限的状态集合（如K=q0，q1，qn）它的每一个元素称为一个状态。（2）是字母表，它的每个元素称为一个输入字符 。（3）F是终态集合，它的每个元素都是一个终态，即“终止状态”或“接受状态”。（4）是K（笛卡尔积）到K的函数，称为转移函数。如（qi，a）=qj表示当前状态为Ki，输入字符为a时，将转移到下一个状态qj，qj称为qi的某一个后继状态。（5）S是唯一的一个初始状态，S K。定义2.1.3非确定有限自动机（NFA）是一个五元组M=（K，S，F）。其中：（1）K是有限的状态集合（如K= q0，q1，qn ）它的每一个元素称为一个状态。（2）是字母表，它的每个元素称为一个输入字符 。（3）FK是一个可空的终态集合。（4）是K*（笛卡尔积）到K的子集的转移函数： ：S*2S（5）SK是一个非空初态集。2NFA到DFA的转换任何一个NFA都可以确定化成一个与之对应的DFA。对于一个NFA，由于状态转换函数f是一个多值函数，因此总存在一些状态q，对于它们有f（q，a）q1，q2，q3，qn，它是NFA状态集合的一个子集，为了将NFA转换为DFA，把状态集合 q1，q2，q3，qn 看做一个状态A，也就是说，从NFA构造DFA的基本思想是DFA的每一个状态代表NFA状态集合的某个子集，这个DFA使用它的状态去记录在NFA读入输入符号之后可能到达的所有状态的集合，我们称此构造方法为子集法。下面具体给出NFA构造等价DFA的子集法。输入：一个NFA N。输出：一个接受（识别）相同语言的DFA M。方法：利用构造闭包的方法将NFA确定化为DFA。首先引入状态集合I的闭包的概念。设I是NFA N的一个状态子集，-CLOSURE（I）定义如下：（1）若sI，则s -CLOSURE（I）。（2）若sI，那么从s出发经过任意条弧而能到达的任何状态s，都属于-CLOSURE（I）。由定义可知，-CLOSURE（I）表示所有那些从I中的元素出发经过通路到达自身的。该集合对DFA来说是一个状态。这样，利用构造-CLOSURE（I）的方法就可以比较方便、直接地把NFA转换为一个等价的DFA。从NFA N=（K，S，F）构造等价的DFA M=（K，S，F）的基本方法是：首先将从状态S出发经过任意条弧的所能到达的状态所组成的集合作为M的初态S，然后从S出发，经过对输入符号a的状态转移所能到达的状态（包括读输入符号a之前或之后所有可能的转移所能到达的状态）所组成的集合作为M的新状态，如此重复，直到不再有新的状态出现为止。下面给出构造K及的算法描述如下：（1）置DFA M中的状态集K和F为集。（2）给出M的初态S=-CLOSURE（S），并把S置为未标记状态后加入到K中（未标记状态即新状态）。（3）如果K中存在未标记的状态T=q1，q2，qn，qiK，则进行如下变换（即求（T，a）的后继状态U）。1）对于每个a，置 J=（q1，q2，qn ，a） = （q1，a）（q2，a）（qn，a） U=CLOSURE（J） 如果U不在K中，则将U置为无标记的状态添加到K中，且把状态转移（T，a）=U添加到M中，如果U中至少含有一个元素是N的终态，则把U置为M的终态，即把U添加到F中。2）对T置标记（表示T不再是新加入K中的状态）。（4）重复进行步骤（3），直到K中不再含有未标记的状态为止。（5）重新命名K中的状态，最后获得等价的DFA M。3DFA的化简所谓一个DFA M 的化简是指寻找一个状态数比M少的DFA M，使得L（M）= L（M）。化简了的DFA M满足两个条件：（1）没有多余的状态。（2）它的状态集中，没有两个状态是互相等价的。所谓有穷自动机的多余状态是指从该自动机的开始状态出发，任何可识别的输入串也不能到达的状态。设DFA M=（K，S0，F），s，t Q。若对任何*，（s，）F当且仅当（s，）F，则称状态s和t是等价的。如果s和t不等价，则称s和t是可区别的。化简方法DFA M最小化的方法是把M的状态集Q分划成一些不相交的子集，使得每个子集中任何两个状态是等价的，而任何两个属于不同子集的状态都是可区别的；然后在每个子集中任取一个状态作为“代表”，而删去子集中其余状态，并把射向其余状态的箭弧都改为射向作为“代表”的状态中。下面给出化简算法的具体执行步骤。输入：一个DFA M。输出：接受与M相同语言的DFA M，且其状态数最少。方法：（1）将DFA M 的状态集K分成两个子集：终态集F和非终态集F，形成初始分划。（2）对建立新的分划new。对的每个状态子集G，进行如下变换：1）把G分划成新的子集，使得G的两个状态s和t属于同一子集，当且仅当对任何输入符号a，状态s和t转换到的状态都属于的同一子集。2）用G分划出的所有新自己替换G，形成新的分划new。（3）如果new =，则执行第（4）步；否则令=new，重复第（2）步。（4）分划结束后，对分划中的每个状态子集，选出一个状态作为代表，而删去其他一切等价的状态，并把射向其他状态的箭弧改为射向这个作为代表的状态。这样得到的DFA M是与DFA M等价的一切DFA中状态数最少的DFA。2.4. 自下而上的语法分析2.4.1. FIRST集合和FOLLOW集合在介绍自下而上的分析方法之前，我们先介绍一下两个重要的概念 FIRST集合和FOLLOW集合以及他们的求法。FIRST集合即一个符号串所有可能的第一个终结符的集合。但要确定一个FIRST集合并非简单到一目了然，为此我们需要了解FIRST集合的确切定义。定义2.2.4 令X为一个文法符号（包括终结符、非终结符和），集合FIRST（X）由终结符组成（含），其定义如下：（1）若X是终结符或，则FIRST（X）=X；（2）若X是非终结符，则对每一个产生式XX1X2Xn 。FIRST（X）包含了FIRST（X1）-。若存在FIRST（X1）FIRST（Xi）（in），都包含，则FIRST（X）也包含FIRST（Xi+1）-。若所有集合FIRST（X1）FIRST（Xn）都包含，则FIRST（X）也包含。FOLLOW集合直观的概念是指一个非终结符直接后继的终结符所组成的集合。定义2.2.5 给出一个非终结符A，那么FOLLOW（A）则是由终结符构成的，此外还有输入字符串结尾标识符号#。集合FOLLOW（A）的元素有如下性质。1）若A是开始符号，则FOLLOW（A）中必含#。2）若存在产生式BA，则FIRST（）-在FOLLOW（A）中。3）若存在产生式BA，且 FIRST（），则FOLLOW（A）包括FOLLOW（B）。自下而上语法分析的目的仍是构造语法树，它的构造过程是先以被分析句子之词为叶，生成子树。再根据文法规则，以非终结符为父结点，逐步向上构造子树，最后得到以文法开始符号为根的语法树。2.4.2. 自下而上的语法分析方法自下而上的语法分析分析时将输入串中的符号逐一地移进符号栈，同时由检查栈顶，一旦发现栈顶有若干相邻的符号与文法中某产生式的候选式相同，就可以生成以该产生式左部非终结符为父结点，该产生式右部符号串为子结点的子树，同时用产生式左部非终结符替换栈顶所构成的候选式符号串。这就是“归约”的概念。然后再检查符号栈顶是否还有构造子树的可能。若有，则再次构造子树，若无，则继续将输入串中的符号移进符号栈。当输入串的全部符号都移进符号栈后，弱国经过若干次归约，符号栈里只剩下一个文法开始符号，则意味着一棵以文法开始符号为根的语法树已构造完成。语法分析到此成功结束。这种利用符号栈的自下而上分析方法被称为“移进归约”法。 LR分析法LR分析法是一种十分强大有效的分析方法，适用于一大类上下文无关文法的语法分析。“LR”的是指从左向右扫描输入字符串，R是指构造最右推导的逆过程。一个LR语法分析器实质上是一个带栈的确定有限状态自动机。它的功能是根据文法来识别形成句子的字符串。一个LR分析器的结构示意图如图所示，它由分析栈、分析表和总控程序3个部分组成。分析栈用来存放分析过程中的历史和展望信息。LR分析法将历史和展望信息抽象成状态，并放在分析栈中，这就是说分析栈中的每个状态概括了从分析开始到某一归约阶段的整个分析历史和对未来进行的展望。LR分析表是LR分析器的核心部分。一张LR分析表由分析动作（ACTION）表和状态转换（GOTO）表两部分组成，它们都是二维数组。状态转换表元素GOTOSi，X规定了当状态Si面临文法符号X时，应该转移到的下一个状态。分析动作表元素ACTIONSi，a规定了当状态Si面临输入符号a时应该执行的动作。有如下4种可能的动作。（1）移进：把状态Sj=GOTOSi，a和输入符号a移入分析栈。（2）归约：当栈顶符号串 形成句柄，且文法中有A 的规则，其中|=，则归约动作是从分析栈顶去掉个文法符号和个状态，并把归约符A和GOTOSi-，A=Sj移入分析栈中。（3）接受（acc）：表示分析成功。此时，分析栈中只剩文法开始符号S和当前读到的输入符号“$”。即输入符号串已经结束。（4）报错：表示输入串含有错误，此时出现栈顶的某一状态遇到了不该遇到的输入符号。总控程序也称为驱动程序，对所有的LR分析器其总控程序是相同的。总控程序从左至右扫描输入符号串，并根据当前分析栈中栈顶状态以及当前读到的输入符号按照LR分析表元素所指示的动作完成每一步的分析工作。总控程序的算法如下：输入：输入串W和LR分析表。输出：若W是句子，得到W的自下而上分析成功的信息，否则输出错误信息。算法：初始化时，初始化状态S0在分析栈栈顶，输入串W$的第一个符号读入a中。while（ACTIONS，a!=acc）if （ACTIONS，a=Si） 将状态i和输入符号a进栈； 将下一个输入符号读入a中；else if（ACTIONS，a=rj） 用第j条规则A归约； 将|个状态和|个输入符号退栈； 当前栈顶状态为S，将A和GOTOS，A=S”进栈；else if（ACTIONS，a=ERROR） error（）； LR（0）分析法LR（0）分析就是在分析的每一步，只需根据当前栈顶状态而不必向前查看输入符号就能确定应采用的分析动作。LR分析器的关键部分是分析表的构造。构造LR分析表的基本思想是从给定的上下文无关文法直接构造识别文法所有规范句型活前缀的DFA，然后再将DFA转换成一张LR分析表。为了给出构造LR分析表的算法，需要定义一些重要的概念和术语。文法规范句型的活前缀（1）字符串的前缀是指字符串的任意首部。（2）规范句型活前缀是指规范句型的前缀，这种前缀不包含句柄右边的任何符号。LR（0）项目由活前缀定义可知，在一个规范句型的活前缀中，绝不含有句柄右边的任何符号。因此，活前缀与句柄之间的关系由下述3种情况：（1）活前缀中已含有句柄的全部符号，表明此时某一规则A 的右部符号串 已经出现在栈顶，其相应的分析动作是用此规则进行归约。（2）活前缀中只含有句柄的一部分符号，此时意味着形如A12 规则的右部子串1已出现在栈顶，正期待着从剩余的输入串中进行归约得到2。（3）活前缀中全然不含有句柄的任何符号，此时意味着期望从剩余输入串中能看到由某规则A的右部所推出的符号串。为了刻画在分析过程中，文法的一个规则右部符号串已有多大一部分被识别，我们在文法中每个规则右部适当位置上加一个圆点来表示。针对上述三种情况，标有圆点的规则分别为AA12A我们把文法G中右部标有圆点的规则称为G的一个LR（0）项目。对空规则A仅有LR（0）项目A。直观上说，一个LR（0）项目指明了对文法规范句型活前缀的不同识别状态，文法G的全部LR（0）项目是构造识别文法所有规范句型活前缀的DFA的基础。由于不同的LR（0）项目反映了在分析过程中栈顶的不同情况，因此，可以根据圆点位置和圆点后是终结符还是非终结符，将一个文法的全部LR（0）项目进行分类：1）归约项目，形如A ，其中 （VN VT）*，即圆点在最右端的项目，它表示一个规则的右部已分析完，句柄已形成，应该按此规则进行归约。2）移进项目，形如Aa，其中，（VN VT）*，aVT即圆点后面为终结符的项目，它表示期待从输入串中移进一个符号，以待形成句柄。3）待约项目，形如AB，其中其中，（VN VT）*，BVN即圆点后面为非终结符的项目，它表示期待从剩余的输入串中进行归约而得到B，然后才能继续分析A的右部。4）接受项目，形如SS ，其中S为文法的开始符号，即文法开始符号的归约项目。S为左部的规则仅有一个，它是归约项目的特殊情况，它表示整个句子已经分析完毕，可以接受。构造识别文法所有规范句型活前缀DFA的方法构成识别文法规范句型活前缀DFA的每一个状态是由若干个LR（0）项目所组成的集合，称为LR（0）项目集。在这个项目集中，所有的LR（0）项目识别的活前缀是相同的，可以用闭包函数（CLOSURE）来求DFA的一个状态的项目集。为了使“接受”项目惟一，我们对文法G进行拓广。假定文法G的开始符号为S，在文法G中引入一个新的开始符号S，并加进一个新的规则SS，从而得到文法G的拓广文法G。（1）定义闭包函数设I是拓广文法G的一个LR（0）项目集，定义和构造I的闭包CLOSURE（I）如下：1）I中的任何一个项目都属于CLOSURE（I）。2）若AB属于CLOSURE（I），则每一形如Br的项目也属于CLOSURE（I）。3）重复2）直到CLOSURE（I）不再增大为止。（2）定义状态转移函数GO设I是拓广文法G 的任一个项目集，X为一文法符号，定义状态转移函数GO）（I，X）如下：GO（I，X）=CLOSURE（J）J=AX|AXI 通过闭包函数（CLOSURE）和状态转移函数（GO）很容易构造出文法G的识别文法规范句型活前缀的DFA。（3）构造识别文法规范句型活前缀DFA的方法1）求CLOSURE（SS），得到初状态项目集。2）对初态项目集或其他已构造的项目集，应用状态转移函数GO（I，X）求出新的项目集（后继状态）。3）重复2）直到不出现新的项目集（新状态）为止。4）转移函数GO建立状态之间的连接关系。构成识别一个文法活前缀的DFA的状态（项目集）的全体称为这个文法的LR（0）项目集规范族。（4）LR（0）分析表的构造若对于一个文法G的拓广文法G的LR（0）项目集规范族中的每个项目集，不存在移进项目和归约项目同时并存或多个归约项目同时并存，则称G为LR（0）文法。对LR（0）文法，构造LR（0）分析表的算法如下：输入：识别LR（0）文法G规范句型活前缀的DFA输出：文法G的LR（0）分析表。方法：用整数0，1，2，n分别表示状态I0，I1，I2，In，令包含SS项目的集合Ik的下标为分析器的初始状态。1）若项目Ax属于Ik，且转换函数GO（Ik，x）= Ij，当x为终结符时，则置ACTION（k，x）= Sj。2）若项目A属于Ik，则对任何终结符和结束符$（统一记为a）置ACTIONk， a= rj（假定A 为文法的第j条规则）。3）若GO（Ik，A）= Ij，A为非终结符，则置GOTOk，A = j。4）若项目SS属于Ik，则置ACTIONk，$= acc。5）分析表中凡不能用规则1）至4）填入信息的元素均置为“出错标志”。根据这种方法构造的LR（0）分析表不含多重定义时，称这样的分析表为LR（0）分析表。能构造LR（0）分析表的文法称为LR（0）文法。 SLR（1）分析法由于LR（0）文法要求文法的每一个LR（0）项目集中都不含有冲突的项目，这个条件比较苛刻，对于大多数语言来说，一般都不能满足LR（0）文法的条件。为了对语言句子进行确定性的分析，需要解决“移进归约”或“归约归约”冲突。我们采用对含有冲突的项目集向前查看一个输入符号的办法来解决冲突，这种分析发称为简单的LR分析法，即SLR（1）分析法。一般而言，若一个LR（0）项目集I中有m个移进项目和n个归约项目时：I：A11a11，A22a22，Ammamm，B1r1 ，B2r2 ，Bnrn 对所有移进项目向前看一符号集合a1，a2，am和FOLLOW（B1），FOLLOW（B2），FOLLOW（Bn）两两相交为空集时，对当前输入符a：（1）若aa1，a2，am，则移进。（2）若aFOLLOW（Bi），i=1，2，n，则用Biri进行归约。（3）此外报错。这种用来解决分析动作冲突的方法称为SLR（1）方法。如果对于一个文法的某些LR（0）项目集或者LR（0）分析表中所含有的动作冲突都能用SLR（1）方法解决，则称为这个文法是SLR（1）文法。 LR（1）分析法由于用SLR（1）方法解决动作冲突时，它仅孤立地考查对于归约项目A ，只要当前面临输入符号aFOLLOW（A）时，就确定使用规则A进行归约，而没有考查符号串所在规范句型的环境。因为如果栈里的符号串为$，归约后变为$A，当前读到的输入符号是a，若文法中不存在以Aa为前缀的规范句型，那么，这种归约无效。LR（1）分析法的思想是在分析过程中，当试图用某一规则A归约栈顶的符号串时，不仅应该查看栈中符号串，还应向前扫视一个输入符号a，只有当Aa的确构成文法某一规范句型的前缀时，才能用此规则进行归约。为此，可以考虑在原来LR（0）项目集中增加更多的展望信息，这些展望信息有助于克服动作冲突和排除无效归约。也就是需要重新定义称之为LR（1）的项目。一个LR（1）项目是一个二元组A，a，其中A是一个LR（0）项目，每个a是终结符，称它为展望符或搜索符。当时，搜索符是无意义的；当=时，搜索符a明确指出当A ，a是栈顶状态的一个LR（1）项目时，仅在输入符号是a是才能用A归约，而不是对FOLLOW（A）中的所有符号都用A归约。构造LR（1）项目集族的方法和构造LR（0）项目集规范族的方法基本相同。具体构造方法如下：