张宇 哈尔滨工业大学计算机科学与技术学院 zhangyu@ir.hit.edu.cn

内容提要 什么是句法分析 与形式语言句法分析的比较 上下文无关语法的分析策略 自顶向下分析法 自底向上分析法 左角分析法 2019年1月17日3时40分 中文信息处理--句法分析

内容提要（续） 上下文无关语法的分析算法 概率上下文无关语法 组块分析与部分分析 移进－归约算法 Marcus确定性分析算法 CYK算法 Earley算法 Tomita算法 Chart算法 概率上下文无关语法 组块分析与部分分析 2019年1月17日3时40分 中文信息处理--句法分析

什么是句法分析 句法分析（Parsing）和句法分析器（Parser) 句法分析是从单词串得到句法结构的过程； 不同的语法形式，对应的句法分析算法也不尽相同； 由于短语结构语法（特别是上下文无关语法）应用得最为广泛，因此以短语结构树为目标的句法分析器研究得最为彻底； 很多其他形式语法对应的句法分析器都可以通过对短语结构语法的句法分析器进行简单的改造得到。 本讲义将主要介绍上下文无关语法的句法分析器。 2019年1月17日3时40分 中文信息处理--句法分析

与形式语言句法分析的比较 形式语言一般是人工构造的语言，是一种确定性的语言，即对于语言中的任何一个句子，只有唯一的一种句法结构是合理的，即使语法本身存在歧义，也往往通过人为的方式规定一种合理的解释。 如程序语言中的if…thenif…then…else…结构，往往都人为规定else 子句与最接近的if 子句配对； 而在自然语言中，歧义现象是天然地大量存在着的，而且这些歧义的解释往往都有可能是合理的，因此，对歧义现象的处理是自然语言句法分析器最本质的要求。 由于要处理大量的歧义现象，导致自然语言句法分析器的复杂程度远高于形式语言的句法分析器。 2019年1月17日3时40分 中文信息处理--句法分析

句法结构歧义的消解 人们正常交流中所使用的语言，放在特定的环境下看，一般是没有歧义的，否则人们将无法交流（某些特殊情况如幽默或双关语除外） 如果不考虑语言所处的环境和语言单位的上下文，将会发现语言的歧义现象无所不在； 结论：一般来说，语言单位的歧义现象在引入更大的上下文范围或者语言环境时总是可以被被消解的。句法分析的核心任务就是消解一个句子在句法结构上的歧义。 2019年1月17日3时40分 中文信息处理--句法分析

句法结构的歧义消解（续） 我是县长。 我是县长派来的。 咬死了猎人的狗跑了。 就是这条狼咬死了猎人的狗。 小王和小李的妹妹结婚了。 小王和小李的妹妹都结婚了。 2019年1月17日3时40分 中文信息处理--句法分析

例子－语法 小王和小李的妹妹结婚了 2019年1月17日3时40分 中文信息处理--句法分析

例子－分析结果之一 2019年1月17日3时40分 中文信息处理--句法分析

例子－分析结果之二 2019年1月17日3时40分 中文信息处理--句法分析

另一个例子 我是县长派来的 2019年1月17日3时40分 中文信息处理--句法分析

另一个例子－分析结果 2019年1月17日3时40分 中文信息处理--句法分析

句法分析的基本策略 句法分析通常采用的策略有： 自顶向下分析法； 自底向上分析法； 左角分析法； 其他策略。 2019年1月17日3时40分 中文信息处理--句法分析

上下文无关语法的分析算法 常见的上下文无关语法的句法分析算法： CYK算法； 移进－归约算法； Marcus确定性分析算法； Earley算法； Tomita算法（GLR算法、富田算法）； Chart算法（图分析算法、线图分析算法）； 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下和自低向上分析法1 句法分析的过程也可以理解为句法树的构造过程 所谓自顶向下分析法也就是先构造句法树的根结点，再逐步向下扩展，直到叶结点； 所谓自底向上分析法也就是先构造句法树的叶结点，再逐步向上合并，直到根结点。 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下和自低向上分析法2 自顶向下的方法又称为基于预测的方法，也就是说，这种方法是先产生对后面将要出现的成分的预期，然后再通过逐步吃进待分析的字符串来验证预期。如果预期得到了证明，就说明待分析的字符串可以被分析为所预期的句法结构。如果某一个环节上预期出了差错，那就要用另外的预期来替换（即回溯）。如果所有环节上所有可能的预期都被吃进的待分析字符串所“反驳”，那就说明待分析的字符串不可能是一个合法的句子，分析失败。 自底向上的方法也叫基于归约的方法。就是说，这种方法是先逐步吃进待分析字符串，把它们从局部到整体层层归约为可能的成分。如果整个待分析字符串被归约为开始符号S，那么分析成功。如果在某个局部证明不可能有任何从这里把整个待分析字符串归约为句子的方案，那么就需要回溯。 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例1 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例2 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例3 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例4 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例5 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例6 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例7 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例8 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例9 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例10 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例11 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例12 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例13 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例14 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例15 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例16 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例17 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例18 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例19 2019年1月17日3时40分 中文信息处理--句法分析

自顶向下分析法－示例20 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例1 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例2 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例3 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例4 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例5 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例6 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例7 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例8 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例9 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例10 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例11 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例12 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例13 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例14 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例15 2019年1月17日3时40分 中文信息处理--句法分析

自底向上分析法－示例16 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－概述 左角分析法是一种自顶向下和自底向上相结合的方法 所谓“左角(Left Corner)”是指任何一个句法子树中左下角的那个符号 比较： 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例1 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例2 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例3 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例4 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例5 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例6 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例7 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例8 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例9 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例10 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例11 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例12 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例13 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例14 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例15 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例16 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例17 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例18 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例19 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例20 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例21 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例22 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例23 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例24 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例25 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例26 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例27 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例28 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例29 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例30 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例31 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例32 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例33 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例34 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例35 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例36 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例37 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例38 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例39 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例40 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例41 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例42 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例43 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例44 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例45 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例46 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例47 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例48 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例49 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例50 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例51 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例52 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例53 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例54 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例55 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例56 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例57 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例58 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例59 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例60 2019年1月17日3时40分 中文信息处理--句法分析

左角分析法－示例61 2019年1月17日3时40分 中文信息处理--句法分析

移进－归约算法：概述 移进－归约算法：Shift-Reduce Algorithm 移进－归约算法类似于下推自动机的LR分析算法 移进－归约算法的基本数据结构是堆栈 移进－归约算法的四种操作： 移进：从句子左端将一个终结符移到栈顶 归约：根据规则，将栈顶的若干个符号替换成一个符号 接受：句子中所有词语都已移进到栈中，且栈中只剩下一个符号S，分析成功，结束 拒绝：句子中所有词语都已移进栈中，栈中并非只有一个符号S，也无法进行任何归约操作，分析失败，结束 2019年1月17日3时40分 中文信息处理--句法分析

移进－归约算法：举例 2019年1月17日3时40分 中文信息处理--句法分析

移进－归约算法：冲突 移进－归约算法中有两种形式的冲突： 冲突解决方法：回溯 回溯导致的问题： 移进－归约冲突：既可以移进，又可以归约 归约－归约冲突：可以使用不同的规则归约 冲突解决方法：回溯 回溯导致的问题： 回溯策略：对于互相冲突的各项操作，给出一个选择顺序 断点信息：除了在堆栈中除了保存非终结符外，还需要保存断点信息，使得回溯到该断点时，能够恢复堆栈的原貌，并知道还可以有哪些可选的操作 2019年1月17日3时40分 中文信息处理--句法分析

移进－归约算法：示例1 回溯策略： 断点信息： 移进－归约冲突：先归约，后移进 归约－归约冲突：规则事先排序，先执行排在前面的规则 当前规则：标记当前归约操作所使用的规则序号 候选规则：记录在当前位置还有哪些规则没有使用（由于这里规则是排序的，所以这一条可以省略） 被替换结点：归约时被替换的结点，以便回溯时恢复 2019年1月17日3时40分 中文信息处理--句法分析

移进－归约算法：示例2 给规则排序并加上编号： 2019年1月17日3时40分 中文信息处理--句法分析

移进－归约算法：示例3 2019年1月17日3时40分 中文信息处理--句法分析

移进－归约算法：示例4 2019年1月17日3时40分 中文信息处理--句法分析

移进－归约算法：示例5 2019年1月17日3时40分 中文信息处理--句法分析

移进－归约算法：示例6 2019年1月17日3时40分 中文信息处理--句法分析

移进－归约算法：示例7 2019年1月17日3时40分 中文信息处理--句法分析

移进－归约算法：特点 移进－归约算法是一种自底向上的分析算法 为了得到所有可能的分析结果，可以在每次分析成功时都强制性回溯，直到分析失败 可以看到，采用回溯算法将导致大量的冗余操作，效率非常低 2019年1月17日3时40分 中文信息处理--句法分析

移进－归约算法的改进 如果在出现冲突（移进－归约冲突和归约－归约冲突）时能够减少错误的判断，将大大提高分析的效率 引入规则：通过规则，给出在特定条件（栈顶若干个符号和待移进的单词）应该采取的动作 引入上下文：考虑更多的栈顶元素和更多的待移进单词来写规则 引入缓冲区（Marcus算法）：是一种确定性的算法，没有回溯，但通过引入缓冲区，可以延迟作出决定的时间 2019年1月17日3时40分 中文信息处理--句法分析

CYK算法－概述 CYK算法：Cocke-Younger-Kasami算法 CYK算法是一种并行算法，不需要回溯； CYK算法建立在Chomsky范式的基础上 Chomsky范式的规则只有两种形式：A→BC A→x这里A,B,C是非终结符，x是终结符 由于后一种形式实际上就是词典信息，在句法分析之前已经进行了替换，所以在分析中我们只考虑形如A→BC形式的规则 由于任何一个上下文无关语法都可以转化成符合Chomsky范式的语法，因此CYK算法可以应用于任何一个上下文无关语法 2019年1月17日3时40分 中文信息处理--句法分析

CYK算法－数据结构1 2019年1月17日3时40分 中文信息处理--句法分析

CYK算法－数据结构2 一个二维矩阵：{ P(i , j) } 每一个元素P(i , j)对应于输入句子中某一个跨度（Span）上所有可能形成的短语的非终结符的集合 横坐标i：该跨度左侧第一个词的位置 纵坐标j：该跨度包含的词数 上图中P(3,1)={NP,N}表示“县长”可以归约成N和NP，P(3,3)={Sφ}表示“县长派来”可以规约成Sφ 2019年1月17日3时40分 中文信息处理--句法分析

CYK算法：算法描述 2019年1月17日3时40分 中文信息处理--句法分析

CYK算法：特点 本质上是一种自底向上分析法； 采用广度优先的搜索策略； 采用并行算法，不需要回溯，没有冗余的操作； 时间复杂度O(n3)； 由于采用广度优先搜索，在歧义较多时，必须分析到最后才知道结果，无法采用启发式策略进行改进。 2019年1月17日3时40分 中文信息处理--句法分析

Earley算法－概述 Earley算法也是一种并行算法，不需要回溯； 类似于CYK算法，Earley算法中也通过一个二维矩阵来存放已经分析过的结果； Earley算法的一个重要贡献是引入了点规则，进一步减少了规则匹配中的冗余操作； Earley算法是一种自顶向下的分析算法 2019年1月17日3时40分 中文信息处理--句法分析

Earley算法：点规则 所谓点规则，是在规则的右部的终结符或非终结符之间的某一个位置上加上一个圆点，表示规则右部被匹配的程度 例子： – VP → · V NP 表示这条规则还没有被匹配 – VP → V · NP 表示这条规则右部的V已经匹配成功，而NP还没有被匹配 – VP → V NP · 表示这条已被完全匹配，并形成了一个短语VP 2019年1月17日3时40分 中文信息处理--句法分析

Earley算法：数据结构 数据结构：二维矩阵{E(i,j)}，其中每个元素是一个点规则的集合，用来存放句子中单词i到单词j这个跨度上所分析得到的所有点规则 还是以“我是县长派来的”为例： Earley算法就是从左到右逐步填充这个二维矩阵的过程 2019年1月17日3时40分 中文信息处理--句法分析

Earley算法：算法描述 初始化： 循环执行以下步骤，直到分析成功或失败： 对于规则集中，所有左端为初始符S的规则S→α ，把S→·α加入到E(0,0)中 如果B→· A β在E(0,0)中，那么对于所有左端为符号A的规则A→α ，把A→·α加入到E(0,0)中 循环执行以下步骤，直到分析成功或失败： 如果A→α·xjβ在E(i,j-1)中，那么把A→αxj·β加入到E(i,j)中 如果A→α·Bβ在E(i,j)中，那么对所有左端为符号B的规则B→γ，把B→·γ加入到E(j,j)中 如果B→γ在E(i,j)中，且在E(k,i-1)存在A→α·Bβ，那么把A→αB·β加入到E(k,j)中 2019年1月17日3时40分 中文信息处理--句法分析

复习思考题 “小王和小李的妹妹结婚了”，从语义上说，有哪些种可能的解释？ 在以上介绍的分析算法中，对于句法歧义我们采用了两种消解策略：回溯和并行。请解释那种算法采用了回溯策略，那种算法采用了并行策略，并比较回溯和并行这两种策略的优缺点。 移进－归约算法是一种采用堆栈作为数据结构的自底向上分析算法。试构造一种采用堆栈作为数据结构的自顶向下分析算法。 试比较移进－归约算法和编译原理中LR(k)算法的异同。 2019年1月17日3时40分 中文信息处理--句法分析