句法分析前部分优秀课件.ppt
句法分析前部分第1页，本讲稿共33页提纲：提纲：概述短语结构分析线图分析法第2页，本讲稿共33页 句法分析：是指对输入的单词序列（一般为句子）判断其构成是否合乎给定的语法，分析合乎语法的句子的句法结构句法分析的任务：1）判断输入的字符串是否属于某种语言 2）消除输入句子中词法和结构等方面的歧义 3）分析输入句子的内部结构，如成分构成、上下文关系等类型：短语结构分析(Phrase parsing)完全句法分析(Full parsing)局部句法分析(Partial parsing)依存句法分析(Dependency parsing)8.1 8.1 概概 述述第3页，本讲稿共33页句法形式化（grammar formalism）属于句法理论研究的范畴常见的机遇约束的语法：功能合一语法（functional unification grammar,FUG）树连接语法(tree-adjoining grammar，TAG)词汇功能语法（lexical-functional grammar，LFG）广义的短语结构语法（genneralized phrase structure grammar,GPSG）中心语驱动的短语结构语法（head-driven phase structure grammar，HPSG）8.1.2 8.1.2 语法形式化语法形式化第4页，本讲稿共33页句法分析方法分为：基于规则的分析方法和基于统计的分析方法基于规则的分析方法的基本思路：由人工组织语法规则，建立语法知识库，通过条件约束和检查来实现句法结构的歧义的消除。基于规则的分析方法的主要优点：分析算法可以利用手工编写的语法规则分析输入的句子所有可能的句法结构；对于特定的领域和目的，利用手工编写的有针对性的规则能较好地处理句子中的部分歧义和一些超语法现象。基于规则的分析方法的缺陷：对于一个中等长度的输入句子来说，要利用大覆盖度的语法规则分析出所有可能的句子结构是非常困难的，分析过程的复杂性往往是程序无法实现；即使能够分析出句子所有可能的结构，也难以在巨大的句法分析结果集合中实现有效的消歧义，并选择出最有可能的结果。手工编写的规则一般带有一定的主观性，对于实际应用系统来说，往往难以覆盖大领域的所有复杂语言 手工编写的规则本身是一件大工作量的复杂劳动，而且编写的规则对特定的领域有密切的相关性，不利于句法分析系统向其他领域移植。8.1.3 8.1.3 基本方法基本方法第5页，本讲稿共33页 句法分析的例子（参见前面第4章）他还提出一系列具体措施的政策要点。他/PN 还/AD 提出/VV 一/CD 系列/M 具体/JJ措施/NN 和/CC 政策/NN 要点/NN 。/PU8.2 8.2 短语结构分析第6页，本讲稿共33页(IP(NP-SBJ(PN 他)(VP(ADVP(AD 还)(VP(VV 提出 )(NP-OBJ(QP(CD 一)(CLP(M 系列)(NP(NP(ADJP(JJ 具体)(NP(NN 措施)(CC 和)(NP(NN 政策)NN 要点)(PU。)8 8.2.2 短语结构分析第7页，本讲稿共33页树状表示：IPNPVPPUPNADVPVP。他ADVVNP还提出 QPNPCD CLPNPCCNP一 M ADJP NP 和 NN NN系列 JJNN政策 要点具体 措施8 8.2.2 短语结构分析第8页，本讲稿共33页短语结构分析:目标：实现高正确率、高鲁棒性(robustness)(robustness)、高速度的自动句法分析过程。困难：自然语言中存在大量的复杂的结构歧义 (structural(structural ambiguity)ambiguity)。8 8.2.2 短语结构分析第9页，本讲稿共33页结构歧义例如：(1)I saw a boy in the park.I saw a boy in the park.I saw a boy in the park.(2)I saw a boy in the park with a telescope.(3)I saw a boy swimming on the bridge.(4)关于鲁迅的文章。(5)把重要的书籍和手稿带走了。8.2 8.2 短语结构分析第10页，本讲稿共33页 英语中的结构歧义随介词短语组合个数的增加而不断加深的，这个组合个数我们称之为开塔兰数(Catalan number，记作CN)。如果句子中存在这样 n(n为自然数)个介词短语，CN可由下式获得 Samuelsson,2000：8 8.2.2 短语结构分析第11页，本讲稿共33页 基本方法和开源的句法分析器：基于CFG规则的分析方法：线图分析法(chart parsing)CYK 算法 Earley(厄尔利)算法 LR 算法/Tomita 算法 Top-down:Depth-first/Breadth-first Bottom-up8 8.2.2 短语结构分析第12页，本讲稿共33页 基于 PCFGPCFG 的分析方法PCFG:PCFG:ProbabilisticProbabilistic Context-FreeContext-Free GrammarGrammar(有时也写作 StochasticStochastic CFG,CFG,SCFG)SCFG)其他统计模型 部分开源的句法分析器8 8.2.2 短语结构分析第13页，本讲稿共33页线图分析法 三种策略 自底向上(Bottom-up)(Bottom-up)从上到下(Top-down)(Top-down)从上到下和从下到上结合8 8.3 3 线图分析法第14页，本讲稿共33页8 8.3 3 线图分析法第15页，本讲稿共33页执行操作：查看任意相邻几条边上的词性串是否与某条重写规则的右部相同，如果相同，则增加一条新的边跨越原来相应的边，新增加边上的标记为这条重写规则的头(左部)。重复这个过程，直到没有新的边产生。8 8.3 3 线图分析法第16页，本讲稿共33页点规则：用于表示规则右部被归约(reduce)的程度。设有规则：NP Det A N NP Det N NP A N句子:The good book8 8.3 3 线图分析法第17页，本讲稿共33页点规则：用于表示规则右部被归约(reduce)的程度。设有规则：NP Det A N NP Det N NP A N 句子:The good book8 8.3 3 线图分析法第18页，本讲稿共33页 数据结构 线图(Chart)(Chart)：保存分析过程中已经建立的成分(包括终结符和非 终结符)、位置(包括起点和终点)。通常以 n nn n 的数组表示(n n 为句子包含的词数)。代理表(待处理表)(Agenda)(Agenda)：记录刚刚得到的一些重写规则所代 表的成分，这些重写规则的右端符号串与输入词性 串(或短语标志串)中的一 段完全匹配，通常以栈 或线性队列表示。活动边集(ActiveArc)(ActiveArc)：记录那些右端符号串与输入串的某一段相 匹配，但还未完全匹配的重写规则，通常以数组或 列表存储。8 8.3 3 线图分析法第19页，本讲稿共33页算法描述：从输入串的起始位置到最后位置，循环执行如下步骤：(1)如果待处理表(Agenda)为空，则找到下一个位置上的词，将该词对应的(所有)词类X 附以(i,j)作为元素放到待处 理表中，即X(i,j)。其中，i,j 分别是该词的起始位置和 终止位置，j i，j-i 为该词的长度。(2)从Agenda 中取出一个元素X(i,j)。(3)对于每条规则 A X，将 AX (i,j)加入活动边集ActiveArc 中，然后调用 扩展弧子程序。8 8.3 3 线图分析法第20页，本讲稿共33页 扩展弧子程序：(a)将 X 插入图表(Chart)的(i,j)位置中。(b)对于活动边集(ActiveArc)中每个位置为(k,i)(i k 1)的点 规则，如果该规则具有如下形式：A X,如果A=S,则 把 S(1,n+1)加入到 Chart 中，并给出一个完整的分析结 果；否则，则将 A(k,j)加入到Agenda表中。(c)对于每个位置为(k,i)的点规则：AX，则将 AX (k,j)加入到活动边集中。8 8.3 3 线图分析法8 8.3 3 线图分析法第21页，本讲稿共33页8 8.3 3 线图分析法第22页，本讲稿共33页8 8.3 3 线图分析法第23页，本讲稿共33页8 8.3 3 线图分析法 句子分析句子分析:第24页，本讲稿共33页8 8.3 3 线图分析法 句子分析句子分析:第25页，本讲稿共33页8 8.3 3 线图分析法最后分析结果：第26页，本讲稿共33页8 8.3 3 线图分析法第27页，本讲稿共33页算法的时间复杂度分析 设 n为输入句子的长度，C 为上下文无关文法中的非终结符的数目，S 为点规则的状态数目(大于 CFG 规则的数目)，显然 S C。因为 Agenda 表中的元素形式为X(i,j)，因此,Agenda 表中最大的元素个数为：Cn2。8 8.3 3 线图分析法第28页，本讲稿共33页 由于ActiveArc 中的元素形式为：A Xi,j，所以ActiveArc 表中最大的元素数目为：Sn2.Chart 表中的边的形式为：Ai,j，因此，Chart 表中最大的元素数目为：Cn2。我们来考察算法中每一步执行的最大次数：8 8.3 3 线图分析法第29页，本讲稿共33页算法描述：从输入串的起始位置到最后位置，循环执行如下步骤：(1)如果待处理表(Agenda)为空，则找到下一个位置上的词，将该词对应的(所有)词类X 附以(i,j)作为元素放到待处理表中，即X(i,j)。其中，i,j 分别是该词的起始位置和终止位置，j i，j-i 为该词的长度。最多执行的次数为：最多执行的次数为：C(2)从 Agenda 中取出一个元素X(i,j)加入活动边集ActiveArc 中，最多执行的次数为：最多执行的次数为：1(3)对于每条规则 A X，将 AX (i,j)加入活动边集ActiveArc 中，然后调用 扩展弧子程序。最多执行的次数为：最多执行的次数为：Sn28 8.3 3 线图分析法第30页，本讲稿共33页 扩展弧子程序：(a)将 X 插入图表(Chart)的(i,j)位置最多执行的次数为：1(b)对于活动边集(ActiveArc)中每个位置为(k,i)(i k 1)的点 规则，如果该规则具有如下形式：A X,如果A=S,则 把 S(1,n+1)加入到 Chart 中，并给出一个完整的分析结果；否则，则将 A(k,j)加入到Agenda表中。最多执行的次数为：Sn2(c)对于每个位置为(k,i)的点规则：AX，则将AX (k,j)加入到活动边集中。最多执行的次数为：Sn28 8.3 3 线图分析法第31页，本讲稿共33页每处理一个单词需要最多执行的最多操作次数为：C1Sn21Sn2Sn22C3Sn2由于算法对于长度为 n 的输入句子要执行 n 次循环，因此，Chart 算法最大执行的操作次数为：n(2C3Sn2)所以，Chart算法的时间复杂度为：8 8.3 3 线图分析法第32页，本讲稿共33页 Chart parsing 算法评价 优点：算法简单，容易实现，开发周期短。弱点：算法效率低，时间复杂度为 Kn3;需要高质量的规则，分析结果与规则质量 密切相关;难以区分歧义结构。8 8.3 3 线图分析法第33页，本讲稿共33页
