1、句法分析I,张宇哈尔滨工业大学计算机科学与技术学院,2018年10月8日3时48分,中文信息处理-句法分析,2,内容提要,什么是句法分析与形式语言句法分析的比较上下文无关语法的分析策略自顶向下分析法自底向上分析法左角分析法,2018年10月8日3时48分,中文信息处理-句法分析,3,内容提要（续）,上下文无关语法的分析算法移进归约算法Marcus确定性分析算法CYK算法Earley算法Tomita算法Chart算法概率上下文无关语法组块分析与部分分析,2018年10月8日3时48分,中文信息处理-句法分析,4,什么是句法分析,句法分析（Parsing）和句法分析器（Parser)句法分析是从单
2、词串得到句法结构的过程；不同的语法形式，对应的句法分析算法也不尽相同；由于短语结构语法（特别是上下文无关语法）应用得最为广泛，因此以短语结构树为目标的句法分析器研究得最为彻底；很多其他形式语法对应的句法分析器都可以通过对短语结构语法的句法分析器进行简单的改造得到。本讲义将主要介绍上下文无关语法的句法分析器。,2018年10月8日3时48分,中文信息处理-句法分析,5,与形式语言句法分析的比较,形式语言一般是人工构造的语言，是一种确定性的语言，即对于语言中的任何一个句子，只有唯一的一种句法结构是合理的，即使语法本身存在歧义，也往往通过人为的方式规定一种合理的解释。如程序语言中的ifthenift
3、henelse结构，往往都人为规定else 子句与最接近的if 子句配对；而在自然语言中，歧义现象是天然地大量存在着的，而且这些歧义的解释往往都有可能是合理的，因此，对歧义现象的处理是自然语言句法分析器最本质的要求。由于要处理大量的歧义现象，导致自然语言句法分析器的复杂程度远高于形式语言的句法分析器。,2018年10月8日3时48分,中文信息处理-句法分析,6,句法结构歧义的消解,人们正常交流中所使用的语言，放在特定的环境下看，一般是没有歧义的，否则人们将无法交流（某些特殊情况如幽默或双关语除外）如果不考虑语言所处的环境和语言单位的上下文，将会发现语言的歧义现象无所不在；结论：一般来说，语言单
4、位的歧义现象在引入更大的上下文范围或者语言环境时总是可以被被消解的。句法分析的核心任务就是消解一个句子在句法结构上的歧义。,2018年10月8日3时48分,中文信息处理-句法分析,7,句法结构的歧义消解（续）,我是县长。 我是县长派来的。咬死了猎人的狗跑了。 就是这条狼咬死了猎人的狗。小王和小李的妹妹结婚了。 小王和小李的妹妹都结婚了。,2018年10月8日3时48分,中文信息处理-句法分析,8,例子语法,小王和小李的妹妹结婚了,2018年10月8日3时48分,中文信息处理-句法分析,9,例子分析结果之一,2018年10月8日3时48分,中文信息处理-句法分析,10,例子分析结果之二,2018
5、年10月8日3时48分,中文信息处理-句法分析,11,另一个例子,我是县长派来的,2018年10月8日3时48分,中文信息处理-句法分析,12,另一个例子分析结果,2018年10月8日3时48分,中文信息处理-句法分析,13,句法分析的基本策略,句法分析通常采用的策略有：自顶向下分析法；自底向上分析法；左角分析法；其他策略。,2018年10月8日3时48分,中文信息处理-句法分析,14,上下文无关语法的分析算法,常见的上下文无关语法的句法分析算法：CYK算法；移进归约算法；Marcus确定性分析算法；Earley算法；Tomita算法（GLR算法、富田算法）；Chart算法（图分析算法、线图分
6、析算法）；,2018年10月8日3时48分,中文信息处理-句法分析,15,自顶向下和自低向上分析法1,句法分析的过程也可以理解为句法树的构造过程所谓自顶向下分析法也就是先构造句法树的根结点，再逐步向下扩展，直到叶结点；所谓自底向上分析法也就是先构造句法树的叶结点，再逐步向上合并，直到根结点。,2018年10月8日3时48分,中文信息处理-句法分析,16,自顶向下和自低向上分析法2,自顶向下的方法又称为基于预测的方法，也就是说，这种方法是先产生对后面将要出现的成分的预期，然后再通过逐步吃进待分析的字符串来验证预期。如果预期得到了证明，就说明待分析的字符串可以被分析为所预期的句法结构。如果某一个环
7、节上预期出了差错，那就要用另外的预期来替换（即回溯）。如果所有环节上所有可能的预期都被吃进的待分析字符串所“反驳”，那就说明待分析的字符串不可能是一个合法的句子，分析失败。自底向上的方法也叫基于归约的方法。就是说，这种方法是先逐步吃进待分析字符串，把它们从局部到整体层层归约为可能的成分。如果整个待分析字符串被归约为开始符号S，那么分析成功。如果在某个局部证明不可能有任何从这里把整个待分析字符串归约为句子的方案，那么就需要回溯。,2018年10月8日3时48分,中文信息处理-句法分析,17,自顶向下分析法示例1,2018年10月8日3时48分,中文信息处理-句法分析,18,自顶向下分析法示例2,
8、2018年10月8日3时48分,中文信息处理-句法分析,19,自顶向下分析法示例3,2018年10月8日3时48分,中文信息处理-句法分析,20,自顶向下分析法示例4,2018年10月8日3时48分,中文信息处理-句法分析,21,自顶向下分析法示例5,2018年10月8日3时48分,中文信息处理-句法分析,22,自顶向下分析法示例6,2018年10月8日3时48分,中文信息处理-句法分析,23,自顶向下分析法示例7,2018年10月8日3时48分,中文信息处理-句法分析,24,自顶向下分析法示例8,2018年10月8日3时48分,中文信息处理-句法分析,25,自顶向下分析法示例9,2018年1
9、0月8日3时48分,中文信息处理-句法分析,26,自顶向下分析法示例10,2018年10月8日3时48分,中文信息处理-句法分析,27,自顶向下分析法示例11,2018年10月8日3时48分,中文信息处理-句法分析,28,自顶向下分析法示例12,2018年10月8日3时48分,中文信息处理-句法分析,29,自顶向下分析法示例13,2018年10月8日3时48分,中文信息处理-句法分析,30,自顶向下分析法示例14,2018年10月8日3时48分,中文信息处理-句法分析,31,自顶向下分析法示例15,2018年10月8日3时48分,中文信息处理-句法分析,32,自顶向下分析法示例16,2018年
10、10月8日3时48分,中文信息处理-句法分析,33,自顶向下分析法示例17,2018年10月8日3时48分,中文信息处理-句法分析,34,自顶向下分析法示例18,2018年10月8日3时48分,中文信息处理-句法分析,35,自顶向下分析法示例19,2018年10月8日3时48分,中文信息处理-句法分析,36,自顶向下分析法示例20,2018年10月8日3时48分,中文信息处理-句法分析,37,自底向上分析法示例1,2018年10月8日3时48分,中文信息处理-句法分析,38,自底向上分析法示例2,2018年10月8日3时48分,中文信息处理-句法分析,39,自底向上分析法示例3,2018年10
11、月8日3时48分,中文信息处理-句法分析,40,自底向上分析法示例4,2018年10月8日3时48分,中文信息处理-句法分析,41,自底向上分析法示例5,2018年10月8日3时48分,中文信息处理-句法分析,42,自底向上分析法示例6,2018年10月8日3时48分,中文信息处理-句法分析,43,自底向上分析法示例7,2018年10月8日3时48分,中文信息处理-句法分析,44,自底向上分析法示例8,2018年10月8日3时48分,中文信息处理-句法分析,45,自底向上分析法示例9,2018年10月8日3时48分,中文信息处理-句法分析,46,自底向上分析法示例10,2018年10月8日3时
12、48分,中文信息处理-句法分析,47,自底向上分析法示例11,2018年10月8日3时48分,中文信息处理-句法分析,48,自底向上分析法示例12,2018年10月8日3时48分,中文信息处理-句法分析,49,自底向上分析法示例13,2018年10月8日3时48分,中文信息处理-句法分析,50,自底向上分析法示例14,2018年10月8日3时48分,中文信息处理-句法分析,51,自底向上分析法示例15,2018年10月8日3时48分,中文信息处理-句法分析,52,自底向上分析法示例16,2018年10月8日3时48分,中文信息处理-句法分析,53,左角分析法概述,左角分析法是一种自顶向下和自底
13、向上相结合的方法所谓“左角(Left Corner)”是指任何一个句法子树中左下角的那个符号比较：,2018年10月8日3时48分,中文信息处理-句法分析,54,左角分析法示例1,2018年10月8日3时48分,中文信息处理-句法分析,55,左角分析法示例2,2018年10月8日3时48分,中文信息处理-句法分析,56,左角分析法示例3,2018年10月8日3时48分,中文信息处理-句法分析,57,左角分析法示例4,2018年10月8日3时48分,中文信息处理-句法分析,58,左角分析法示例5,2018年10月8日3时48分,中文信息处理-句法分析,59,左角分析法示例6,2018年10月8日
14、3时48分,中文信息处理-句法分析,60,左角分析法示例7,2018年10月8日3时48分,中文信息处理-句法分析,61,左角分析法示例8,2018年10月8日3时48分,中文信息处理-句法分析,62,左角分析法示例9,2018年10月8日3时48分,中文信息处理-句法分析,63,左角分析法示例10,2018年10月8日3时48分,中文信息处理-句法分析,64,左角分析法示例11,2018年10月8日3时48分,中文信息处理-句法分析,65,左角分析法示例12,2018年10月8日3时48分,中文信息处理-句法分析,66,左角分析法示例13,2018年10月8日3时48分,中文信息处理-句法分
15、析,67,左角分析法示例14,2018年10月8日3时48分,中文信息处理-句法分析,68,左角分析法示例15,2018年10月8日3时48分,中文信息处理-句法分析,69,左角分析法示例16,2018年10月8日3时48分,中文信息处理-句法分析,70,左角分析法示例17,2018年10月8日3时48分,中文信息处理-句法分析,71,左角分析法示例18,2018年10月8日3时48分,中文信息处理-句法分析,72,左角分析法示例19,2018年10月8日3时48分,中文信息处理-句法分析,73,左角分析法示例20,2018年10月8日3时48分,中文信息处理-句法分析,74,左角分析法示例2
16、1,2018年10月8日3时48分,中文信息处理-句法分析,75,左角分析法示例22,2018年10月8日3时48分,中文信息处理-句法分析,76,左角分析法示例23,2018年10月8日3时48分,中文信息处理-句法分析,77,左角分析法示例24,2018年10月8日3时48分,中文信息处理-句法分析,78,左角分析法示例25,2018年10月8日3时48分,中文信息处理-句法分析,79,左角分析法示例26,2018年10月8日3时48分,中文信息处理-句法分析,80,左角分析法示例27,2018年10月8日3时48分,中文信息处理-句法分析,81,左角分析法示例28,2018年10月8日3
17、时48分,中文信息处理-句法分析,82,左角分析法示例29,2018年10月8日3时48分,中文信息处理-句法分析,83,左角分析法示例30,2018年10月8日3时48分,中文信息处理-句法分析,84,左角分析法示例31,2018年10月8日3时48分,中文信息处理-句法分析,85,左角分析法示例32,2018年10月8日3时48分,中文信息处理-句法分析,86,左角分析法示例33,2018年10月8日3时48分,中文信息处理-句法分析,87,左角分析法示例34,2018年10月8日3时48分,中文信息处理-句法分析,88,左角分析法示例35,2018年10月8日3时48分,中文信息处理-句
18、法分析,89,左角分析法示例36,2018年10月8日3时48分,中文信息处理-句法分析,90,左角分析法示例37,2018年10月8日3时48分,中文信息处理-句法分析,91,左角分析法示例38,2018年10月8日3时48分,中文信息处理-句法分析,92,左角分析法示例39,2018年10月8日3时48分,中文信息处理-句法分析,93,左角分析法示例40,2018年10月8日3时48分,中文信息处理-句法分析,94,左角分析法示例41,2018年10月8日3时48分,中文信息处理-句法分析,95,左角分析法示例42,2018年10月8日3时48分,中文信息处理-句法分析,96,左角分析法示
19、例43,2018年10月8日3时48分,中文信息处理-句法分析,97,左角分析法示例44,2018年10月8日3时48分,中文信息处理-句法分析,98,左角分析法示例45,2018年10月8日3时48分,中文信息处理-句法分析,99,左角分析法示例46,2018年10月8日3时48分,中文信息处理-句法分析,100,左角分析法示例47,2018年10月8日3时48分,中文信息处理-句法分析,101,左角分析法示例48,2018年10月8日3时48分,中文信息处理-句法分析,102,左角分析法示例49,2018年10月8日3时48分,中文信息处理-句法分析,103,左角分析法示例50,2018年
20、10月8日3时48分,中文信息处理-句法分析,104,左角分析法示例51,2018年10月8日3时48分,中文信息处理-句法分析,105,左角分析法示例52,2018年10月8日3时48分,中文信息处理-句法分析,106,左角分析法示例53,2018年10月8日3时48分,中文信息处理-句法分析,107,左角分析法示例54,2018年10月8日3时48分,中文信息处理-句法分析,108,左角分析法示例55,2018年10月8日3时48分,中文信息处理-句法分析,109,左角分析法示例56,2018年10月8日3时48分,中文信息处理-句法分析,110,左角分析法示例57,2018年10月8日3
21、时48分,中文信息处理-句法分析,111,左角分析法示例58,2018年10月8日3时48分,中文信息处理-句法分析,112,左角分析法示例59,2018年10月8日3时48分,中文信息处理-句法分析,113,左角分析法示例60,2018年10月8日3时48分,中文信息处理-句法分析,114,左角分析法示例61,2018年10月8日3时48分,中文信息处理-句法分析,115,移进归约算法：概述,移进归约算法：Shift-Reduce Algorithm移进归约算法类似于下推自动机的LR分析算法移进归约算法的基本数据结构是堆栈移进归约算法的四种操作：移进：从句子左端将一个终结符移到栈顶归约：根据
22、规则，将栈顶的若干个符号替换成一个符号接受：句子中所有词语都已移进到栈中，且栈中只剩下一个符号S，分析成功，结束拒绝：句子中所有词语都已移进栈中，栈中并非只有一个符号S，也无法进行任何归约操作，分析失败，结束,2018年10月8日3时48分,中文信息处理-句法分析,116,移进归约算法：举例,2018年10月8日3时48分,中文信息处理-句法分析,117,移进归约算法：冲突,移进归约算法中有两种形式的冲突：移进归约冲突：既可以移进，又可以归约归约归约冲突：可以使用不同的规则归约冲突解决方法：回溯回溯导致的问题：回溯策略：对于互相冲突的各项操作，给出一个选择顺序断点信息：除了在堆栈中除了保存非终
23、结符外，还需要保存断点信息，使得回溯到该断点时，能够恢复堆栈的原貌，并知道还可以有哪些可选的操作,2018年10月8日3时48分,中文信息处理-句法分析,118,移进归约算法：示例1,回溯策略：移进归约冲突：先归约，后移进归约归约冲突：规则事先排序，先执行排在前面的规则断点信息：当前规则：标记当前归约操作所使用的规则序号候选规则：记录在当前位置还有哪些规则没有使用（由于这里规则是排序的，所以这一条可以省略）被替换结点：归约时被替换的结点，以便回溯时恢复,2018年10月8日3时48分,中文信息处理-句法分析,119,移进归约算法：示例2,给规则排序并加上编号：,2018年10月8日3时48分,
24、中文信息处理-句法分析,120,移进归约算法：示例3,2018年10月8日3时48分,中文信息处理-句法分析,121,移进归约算法：示例4,2018年10月8日3时48分,中文信息处理-句法分析,122,移进归约算法：示例5,2018年10月8日3时48分,中文信息处理-句法分析,123,移进归约算法：示例6,2018年10月8日3时48分,中文信息处理-句法分析,124,移进归约算法：示例7,2018年10月8日3时48分,中文信息处理-句法分析,125,移进归约算法：特点,移进归约算法是一种自底向上的分析算法为了得到所有可能的分析结果，可以在每次分析成功时都强制性回溯，直到分析失败可以看到
25、，采用回溯算法将导致大量的冗余操作，效率非常低,2018年10月8日3时48分,中文信息处理-句法分析,126,移进归约算法的改进,如果在出现冲突（移进归约冲突和归约归约冲突）时能够减少错误的判断，将大大提高分析的效率引入规则：通过规则，给出在特定条件（栈顶若干个符号和待移进的单词）应该采取的动作引入上下文：考虑更多的栈顶元素和更多的待移进单词来写规则引入缓冲区（Marcus算法）：是一种确定性的算法，没有回溯，但通过引入缓冲区，可以延迟作出决定的时间,2018年10月8日3时48分,中文信息处理-句法分析,127,CYK算法概述,CYK算法：Cocke-Younger-Kasami算法CYK
26、算法是一种并行算法，不需要回溯；CYK算法建立在Chomsky范式的基础上Chomsky范式的规则只有两种形式：ABC Ax这里A,B,C是非终结符，x是终结符由于后一种形式实际上就是词典信息，在句法分析之前已经进行了替换，所以在分析中我们只考虑形如ABC形式的规则由于任何一个上下文无关语法都可以转化成符合Chomsky范式的语法，因此CYK算法可以应用于任何一个上下文无关语法,2018年10月8日3时48分,中文信息处理-句法分析,128,CYK算法数据结构1,2018年10月8日3时48分,中文信息处理-句法分析,129,CYK算法数据结构2,一个二维矩阵： P(i , j) 每一个元素P
27、(i , j)对应于输入句子中某一个跨度（Span）上所有可能形成的短语的非终结符的集合横坐标i：该跨度左侧第一个词的位置纵坐标j：该跨度包含的词数上图中P(3,1)=NP,N表示“县长”可以归约成N和NP，P(3,3)=S表示“县长派来”可以规约成S,2018年10月8日3时48分,中文信息处理-句法分析,130,CYK算法：算法描述,2018年10月8日3时48分,中文信息处理-句法分析,131,CYK算法：特点,本质上是一种自底向上分析法；采用广度优先的搜索策略；采用并行算法，不需要回溯，没有冗余的操作；时间复杂度O(n3)；由于采用广度优先搜索，在歧义较多时，必须分析到最后才知道结果，
28、无法采用启发式策略进行改进。,2018年10月8日3时48分,中文信息处理-句法分析,132,Earley算法概述,Earley算法也是一种并行算法，不需要回溯；类似于CYK算法，Earley算法中也通过一个二维矩阵来存放已经分析过的结果；Earley算法的一个重要贡献是引入了点规则，进一步减少了规则匹配中的冗余操作；Earley算法是一种自顶向下的分析算法,2018年10月8日3时48分,中文信息处理-句法分析,133,Earley算法：点规则,所谓点规则，是在规则的右部的终结符或非终结符之间的某一个位置上加上一个圆点，表示规则右部被匹配的程度例子： VP V NP 表示这条规则还没有被匹配
29、 VP V NP 表示这条规则右部的V已经匹配成功，而NP还没有被匹配 VP V NP 表示这条已被完全匹配，并形成了一个短语VP,2018年10月8日3时48分,中文信息处理-句法分析,134,Earley算法：数据结构,数据结构：二维矩阵E(i,j)，其中每个元素是一个点规则的集合，用来存放句子中单词i到单词j这个跨度上所分析得到的所有点规则还是以“我是县长派来的”为例：Earley算法就是从左到右逐步填充这个二维矩阵的过程,2018年10月8日3时48分,中文信息处理-句法分析,135,Earley算法：算法描述,初始化：对于规则集中，所有左端为初始符S的规则S ，把S加入到E(0,0)
30、中如果B A 在E(0,0)中，那么对于所有左端为符号A的规则A ，把A加入到E(0,0)中循环执行以下步骤，直到分析成功或失败：如果Axj在E(i,j-1)中，那么把Axj加入到E(i,j)中如果AB在E(i,j)中，那么对所有左端为符号B的规则B，把B加入到E(j,j)中如果B在E(i,j)中，且在E(k,i-1)存在AB，那么把AB加入到E(k,j)中,2018年10月8日3时48分,中文信息处理-句法分析,136,复习思考题,“小王和小李的妹妹结婚了”，从语义上说，有哪些种可能的解释？在以上介绍的分析算法中，对于句法歧义我们采用了两种消解策略：回溯和并行。请解释那种算法采用了回溯策略，那种算法采用了并行策略，并比较回溯和并行这两种策略的优缺点。移进归约算法是一种采用堆栈作为数据结构的自底向上分析算法。试构造一种采用堆栈作为数据结构的自顶向下分析算法。试比较移进归约算法和编译原理中LR(k)算法的异同。,
