自然语言处理 第09章 句法分析 软件学院教研室 陈鄞

引言 句法 句法分析（ Syntactic Parsing ） 关于句子结构的两种观点 句子的构成方法。通常以规则的形式表示。 根据句法规则，分析给定句子的结构。 关于句子结构的两种观点 短语结构（ Phrase structure / Constituency ） 依存结构（ Dependency structure ） 2

例：“The boy put the tortoise on the rug” 短语结构 依存结构 “依存”是指词语词之间支配与被支配的关系 处于支配地位的成分称为支配者（head）；处于被支配地位的成分称为从属者（modifier，dependency） 箭头从支配者指向从属者 动词是句子的中心并支配别的成分，它本身不受任何其他成分支配 S NP VP Det n VP PP prep NP the boy V NP Det put Det n on n the rug the tortoise

例：“The boy put the tortoise on the rug” 短语结构 依存结构 S NP VP Det n VP PP prep NP the boy V NP 依存树 Det put n Det n on the rug the tortoise

国内外研究现状 国外 国内 总的来说，目前国内外自然语言的自动句法分析尚未取得根本突破。其实际性能离真正实用化要求还有相当的距离。 有一定基础 已研制出几个著名的句法分析器（主要以英语为对象），如PASIFAL，Fidditch，ESG，Cass等， 在语言模型、语法规则构造和分析算法等方面取得了许多进展 国内 关于汉语的自动句法分析大体上处于实验阶段，理论、算法研究方面正在进行艰苦的探索 总的来说，目前国内外自然语言的自动句法分析尚未取得根本突破。其实际性能离真正实用化要求还有相当的距离。 其主要原因在于（语言学）理论和（实际的自然语言）应用之间存在着巨大的差距 5

句法分析器的主要工作 语法的形式化表示 分析算法的设计 自顶向下的分析方法 树根→树叶 自底向上的分析方法 树叶→树根

本章内容 9.1 文法的描述 9.2 自顶向下的句法分析 9.3 自底向上的句法分析 9.4 基于统计的句法分析 9.5 句法分析系统的评测 9.6 浅层句法分析 9.7 汉语句法分析的困难

9.1 文法的描述 文法 一条“产生式”就是一条句法规则。 不同类型的文法对规则的形式有不同的限制。 句法分析前首先要确定使用什么类型的文法

(一) 无约束短语结构文法 α→β 0型文法，对产生式没有任何限制 0型语言：由0型语法生成的语言 生成能力太强，无法设计一个程序来判别输入的符号串是不是0型语言中的一个句子

(二) 上下文有关文法 α→β ( |α|≤|β| ) 1型文法，规则左部的符号个数少于或等于规则右部的符号个数 α→β ( |α|≤|β| ) 1型文法，规则左部的符号个数少于或等于规则右部的符号个数 1型语言：由1型文法生成的语言 Example：xYz →xyz

A→β （A是非终结符，β是终结符和/或非终结符组合） (三) 上下文无关文法 A→β （A是非终结符，β是终结符和/或非终结符组合） 2型文法，产生式的左部是一个非终结符 2型语言：由2型文法生成的语言 Example： Y→y

(四) 正则文法 右线性文法 左线性文法 右线性文法和左线性文法都是正则文法，并且二者是等价的 A→βB A和B是非终结符，β是终结符组合

四种文法类型的比较 0型文法生成能力太强 上下文有关文法（1型）的分析算法过于复杂 0型语法 α→β 四种文法类型的比较 0型文法生成能力太强 上下文有关文法（1型）的分析算法过于复杂 上下文无关文法（2型）的规则体系便于构造，是研究得最多的一种文法 正则文法（3型）通常用于词法分析 1型语法 α→β(|α|≤|β|) 2型语法 A→β 3型语法 A→βB或A→Bβ

句法规则 在上下文无关语法中，规则左部必定是一个非终结符，右部是终结符、非终结符或二者的结合 桥姆斯基范式 如果规定右部必须是一个终结符，或者是两个非终结符，符合这种限制的产生式叫做“桥姆斯基范式” 桥姆斯基范式不会削弱产生式表达上下文无关语法的能力

规则的分类 捆绑规则 提升规则 将两个或两个以上符号捆绑为一个符号 体现为二叉树或多叉树 将一个符号（终结符或非终结符）提升为一个非终结符 体现为一叉树 捆绑规则 提升规则 15

对于自顶向下的分析来说，左部相同的规则应该放在一起 规则应该放在一个有序表中以便查找 规则的左部和右部应该分开 对于自顶向下的分析来说，左部相同的规则应该放在一起 反映了汉语语法特点， 即句子可以没有主语

提纲 9.1 语法类型 9.2 自顶向下的句法分析 9.3 自底向上的句法分析 9.4 基于统计的句法分析 9.5 句法分析系统的评测 9.6 浅层句法分析 9.7 汉语句法分析的困难

9.2 自顶向下的句法分析 基本思想 最左推导 有多个候选式时，需要逐个尝试 “孩子/n 喜欢/v 狗/n” S NP VP n （孩子） （喜欢） （狗）

句法分析器的系统结构 “孩子/n 喜欢/v 狗/n” 输入缓冲区(符号序列) 栈 控制程序 输出的 产生式序列

Example “孩子/n 喜欢/v 狗/n” 推导 栈 z0=S z1=NP VP (1.1) z2=a n VP (1.1)(2.1) 推导 栈 z0=S z1=NP VP (1.1) z2=a n VP (1.1)(2.1) z2=n VP (1.1)(2.2) z3=n v NP (1.1)(2.2)(3.1) z4=n v a n (1.1)(2.2)(3.1)(2.1) z4=n v n (1.1)(2.2)(3.1)(2.2) 接收 z1=VP (1.2) z2=v NP (1.2)(3.1)

算法描述 自顶向下的分析是从树根开始推导的。它作用于如下形式的推导： 开始时，这个推导只包含起始符S，并且n=0 所用到的规则放在一个先进后出的堆栈里，开始时堆栈为空。这个堆栈的作用是记录最近所用到的规则 假定左部符号为A的规则的排列顺序是

zn的前i-1个终结符跟输入串的前i-1个符号匹配？ 算 法 流 程 n=0 设zn最左边的非终结符为B 用PB.1展开B n++ 规则PB.1入栈 i:=zn中最左边的非终结符的位置 是 用PB.i+1的应用结果取代 推导的上一步 将PB.i弹出堆栈 将PB.i+1入栈 zn中仍含有 非终结符？ zn的前i-1个终结符跟输入串的前i-1个符号匹配？ 是 否 否 把当前推导作为输入串的一个推导记下 zn与输入串匹配？ 是 结束 否 是 否 n==0 设栈顶规则为PB.i 存在规则PB.i+1？ 从推导中删除最后一个元素 n-- 栈顶规则出栈 否 是

性能分析——优点 节约空间，自始至终只需存储一棵树的结构 虽然处理的是上下文无关语法，但是由于随时检查前面所有的终结符是否跟输入串相匹配，因此受到“上文”的有力约束，避免了许多无谓的扩展 z2=a n VP 当发现a不是输入串的第一个终结符，就不再去扩展后面的VP了

性能分析——缺点 难以处理递归结构 左递归 A->AB 由于不检查“下文” ，将无限次地用这条产生式来扩展A，生成出“ABB…B”这样的串 VP->VP NP 把对输入串的自左至右扫描改为自右至左扫描，这样可以随时检查“下文”，解决左递归问题 右递归 B->AB 由于不检查“上文” ，将无限次地用这条产生式来扩展B，生成出“AAAA…AB”这样的串 NP->AP NP 双向递归 NP->NP NP 无论采取何种扫描方式都难以处理 在自顶向下的分析中，解决递归问题需要附加某种测试

提纲 9.1 语法类型 9.2 自顶向下的句法分析 9.3 自底向上的句法分析 9.4 基于统计的句法分析 9.5 句法分析系统的评测 9.6 浅层句法分析 9.7 汉语句法分析的困难

9.3 自底向上的句法分析 基本思想 主要的自底向上的句法分析方法 最左归约（归约是推导的逆过程） 移进－归约算法，1972 CYK分析法，1965 欧雷（Earley）分析法，1970 线图分析法，1980 GLR分析法，1985 …… “孩子/n 喜欢/v 狗/n” S NP VP n （孩子） v （喜欢） （狗）

9.3.1 移进－归约算法 基本数据结构 四种操作 堆栈 移进：从句子左端将一个终结符移到栈顶 归约：根据规则，将栈顶的若干个符号替换成一个符号 接收：句子中所有词语都已移进到栈中，且栈中只剩下一个开始符号S，分析成功，结束 拒绝：句子中所有词语都已移进栈中，栈中并非只有一个开始符号S，也无法进行任何归约操作，分析失败，结束

举例 句法规则 输入句子 (1) NP → r (2) NP → n (3) NP → S’ de (4) VP’→v v (5) VP→v NP (6) S’ →NP VP’ (7) S →NP VP 输入句子 我/r 是/v 县长/n 派/v 来/v 的/de

操作 栈 输入 1 # r v n v v de 2 sh # r v n v v de 3 r1 # NP v n v v de 操作 栈 输入 1 # r v n v v de 2 sh # r v n v v de 3 r1 # NP v n v v de 4 sh # NP v n v v de 5 sh # NP v n v v de 6 r2 # NP v NP v v de 7 r5 # NP VP v v de 8 sh # NP VP v v de 9 sh # NP VP v v de 10 r4 # NP VP V’ de 11 sh # NP VP V’ de 12 回溯 规则 (1) NP → r (2) NP → n (3) NP → S’ de (4) V’→v v (5) VP→v NP (6) S’ →NP V’ (7) S →NP VP S NP VP r （我） v （是） n （县长） （派） （来） de （的） S’ V’

操作 栈 输入 1 # r v n v v de 2 sh # r v n v v de 3 r1 # NP v n v v de 操作 栈 输入 1 # r v n v v de 2 sh # r v n v v de 3 r1 # NP v n v v de 4 sh # NP v n v v de 5 sh # NP v n v v de 6 r2 # NP v NP v v de 7 r5 # NP VP v v de 8 sh # NP VP v v de 9 sh # NP VP v v de 10 sh # NP VP v v de 11 回溯 规则 (1) NP → r (2) NP → n (3) NP → S’ de (4) V’→v v (5) VP→v NP (6) S’ →NP V’ (7) S →NP VP S NP VP r （我） v （是） n （县长） （派） （来） de （的） S’ V’

操作 栈 输入 1 # r v n v v de 2 sh # r v n v v de 3 r1 # NP v n v v de 操作 栈 输入 1 # r v n v v de 2 sh # r v n v v de 3 r1 # NP v n v v de 4 sh # NP v n v v de 5 sh # NP v n v v de 6 r2 # NP v NP v v de 7 sh # NP v NP v v de 8 sh # NP v NP v v de 9 r4 # NP v NP V’ de 10 r6 # NP v S’ de 11 sh # NP v S’ de 12 r3 # NP v NP 13 r5 # NP VP 14 r7 # S 规则 (1) NP → r (2) NP → n (3) NP → S’ de (4) V’→v v (5) VP→v NP (6) S’ →NP V’ (7) S →NP VP S NP VP r （我） v （是） n （县长） （派） （来） de （的） S’ V’ 回溯导致大量的冗余操作，效率非常低

两种冲突 冲突解决方法 移进－归约冲突：既可以移进，又可以归约 归约－归约冲突：可以使用不同的规则归约 回溯 回溯策略：对于互相冲突的各项操作，给出一个选择顺序 移进－归约冲突：先归约，后移进 归约－归约冲突：规则事先排序，先执行排在前面的规则 断点信息 除了在堆栈中除了保存非终结符外，还需要保存断点信息，使得回溯到该断点时，能够恢复堆栈的原貌，并知道还可以有哪些可选的操作

9.3.2 欧雷（Earley）分析法 基本思想 点规则 把每个句法成分的识别过程划分为若干状态 在规则的右部的终结符或非终结符之间的某一个位置上加上一个圆点，表示规则右部被匹配的程度。 例： VP → v NP VP → · v NP 表示这条规则还没有被匹配 VP → v · NP 表示这条规则右部的v已经匹配成功，而NP还没有被匹配 VP → v NP · 表示这条已被完全匹配，并形成了一个短语VP

Earley算法 (1) S →NP VP (2) NP → n (3) NP → CS de (4) CS →NP V’ (5) VP→v NP (6) V’→v v “张三/n 是/v 县长/n 派/v 来/v 的/de” 6 5 4 3 2 1 n v de

横轴上的坐标代表语法成分的起点 纵轴上的坐标代表“点”所在的位置

基本操作 扫描（Scanner） 预测（Predicator） 归约（Completer） 如果圆点右方是一个终结符，就将圆点向右方扫描一个字符间隔，把匹配完的字符“让”到左方。 预测（Predicator） 如果圆点右方是一个非终结符，那么以该非终结符为左部的规则都有匹配的希望，也就是说分析器可以预测这些规则都可以建立相应的项目。 归约（Completer） 如果圆点右方没有符号（即圆点已经在状态的结束位置），那么表示当前状态所做的预测已经实现，因而可以将当前状态（Si）与已有的包含当前状态的状态(Sj)进行归约（合并），从而扩大Sj覆盖的子串范围。

Earley算法通过一个二维矩阵{E(i,j)}来存放已经分析过的结果，其中每个元素是一个点规则的集合，用来存放句子中单词i到单词j这个跨度上所分析得到的所有点规则。

Earley算法 初始化： 循环执行以下步骤，直到分析成功或失败： 对于规则集中，所有左端为初始符S的规则S→α ，把S→·α加入到E(0,0)中。如果B→· A β在E(0,0)中，那么对于所有左端为符号A的规则A→α ，把A→·α加入到E(0,0)中。 循环执行以下步骤，直到分析成功或失败： 扫描：如果A→α·xjβ在E(i,j)中，并且终结符xj与输入字符串中第j+1个字符匹配，那么把A→αxj·β加入到E(i,j+1)中； 归约：如果B→γ·在E(i,j)中，且在E(k,i)存在A→α·Bβ，那么把A→αB·β加入到E(k,j)中 预测：如果A→α·Bβ在E(i,j)中，那么对所有左端为符号B的规则B→γ，把B→·γ加入到E(j,j)中；

9.3.3 线图分析法 线图分析法（Chart parsing） 给定一组CFG 规则 给定一个句子的词性序列： S=w1 , w2 , … , wn 构造一个线图（一组结点和边的集合） 建立一个二维表：记录每一条边的起始位置和终止位置 the boy hits the dog with a rod

基本思想 查看任意相邻几条边上的标记串是否与某条规则的右部相同，如果相同，则增加一条新的边跨越原来相应的边，新增加边上的标记为这条规则的左部。重复这个过程，直到没有新的边产生。

例 句法规则G (S) 输入句子 S → NP VP NP → det n VP → v NP VP → VP PP PP → prep NP 输入句子 the boy hits the dog with a rod det n v det n prep det n VP VP PP NP NP NP det n v det n prep det n 1 2 3 4 5 6 7 8 S

活性边(活动弧)： 规则右部未被完全匹配 括号中 第1个数字代表 语法成分的起点 第2个数字代表 “点”所在的位置 边 点规则 det(0,1) NP→det · n (0, 1) n(1,2) NP→det n · (0, 2) NP(0,2) S→NP · VP (0, 2) v(2,3) VP→v · NP (2, 3) det(3,4) NP→det · n (3, 4) n(4,5) NP→det n · (3, 5) NP(3,5) S→NP · VP (3, 5) VP→v NP · (2, 5) VP(2,5) VP→VP · PP (2, 5) S→NP VP · (0, 5) S(0,5) prep(5,6) PP→prep · NP (5, 6) det(6,7) NP→det · n (6, 7) n(7,8) NP→det n · (6, 8) NP(6,8) S→NP · VP (6, 8) PP→prep NP · (5, 8) PP(5,8) VP→VP PP · (2, 8) VP(2,8) VP→VP · PP (2, 8) S→NP VP · (0, 8) S(0,8) 活性边(活动弧)： 规则右部未被完全匹配 括号中 第1个数字代表 语法成分的起点 第2个数字代表 “点”所在的位置

数据结构 线图(Chart)： 代理表(待处理表)(Agenda)： 活动边集(ActiveArc)： 保存分析过程中已经建立的成分(包括终结符和非终结符)、位置(包括起点和终点)。通常以n×n 的数组表示(n 为句子包含的词数)。 代理表(待处理表)(Agenda)： 记录刚刚得到的一些规则所代表的成分，这些规则的右部符号串与输入词性串(或短语标志串)中的一段完全匹配，通常以栈或线性队列表示。 活动边集(ActiveArc)： 记录那些右端符号串与输入串的某一段相匹配，但还未完全匹配的规则，通常以数组或列表存储。

算法 从输入串的起始位置到最后位置，循环执行如下步骤： 如果待处理表(Agenda)为空，则找到下一个位置上的词，将该词对应的(所有)词类X 附以(i, j) 作为元素放到待处理表中，即X (i, j)。其中，i, j 分别是该词的起始位置和终止位置，j > i，j- i 为该词的长度 从Agenda 中取出一个元素X(i, j)。 对于每条规则A→Xγ，将A→X·γ(i, j) 加入活动边集ActiveArc 中，然后调用扩展弧子程序。

扩展弧子程序： 将X 插入图表(Chart)的(i, j) 位置中。 对于活动边集(ActiveArc)中每个位置为(k, i) (i >k ≥1)的点规则，如果该规则具有如下形式：A→α·X， 如果A=S, 则把S(1, n+1) 加入到Chart 中，并给出一个完整的分析结果；否则，则将A(k, j) 加入到待处理表中。 对于每个位置为(k i) 的点规则：A→α·Xβ ，则将A→αX·β(k, j ) 加入到活动边集中。

将线图中的边改为结点，将结点改为边，得到分析结果的直观图

Chart parsing 算法评价 优点 算法简单，容易实现，开发周期短 弱点 需要高质量的规则，分析结果与规则质量密切相关 难以区分歧义结构

9.3.4 CYK分析法 Cocke-Younger-Kasami算法 是一种并行算法，不需要回溯 建立在Chomsky范式的基础上 由于任何一个上下文无关语法都可以转化成符合Chomsky范式的语法，因此CYK算法可以应用于任何一个上下文无关语法

Parsing Triangle 张三/n 是/v 县长/n 派/v 来/v 的/de S VP NP [2,5][5,6] S CS VP S → NP VP NP → n NP → CS de CS → NP V ' VP → v NP V ' → v v S [0,1][1,6] VP [1,2][2,6] NP [2,5][5,6] S [0,1][1,3] CS [2,3][3,5] VP V’ n v n v v de NP NP 0 1 2 3 4 5 6 n v n v v de

0 n 1 v 2 n 3 v 4 v 5 de 6 1 2 3 4 5 a[0][1] a[0][2] a[0][3] a[0][4]

CYK 算法的评价 优点 弱点 简单易行，执行效率高 必须对文法进行范式化处理 无法区分歧义 采用并行算法，不需要回溯，没有冗余的操作； 时间复杂度O(n3)； 弱点 必须对文法进行范式化处理 无法区分歧义

提纲 9.1 语法类型 9.2 自顶向下的句法分析 9.3 自底向上的句法分析 9.4 基于统计的句法分析 9.5 句法分析系统的评测 9.6 浅层句法分析 9.7 汉语句法分析的困难

9.4 基于统计的方法 自然语言里存在着大量的歧义结构 例：I saw a man in the park with a telescope.

在真实文本中，人们所觉察到的歧义结构很少，因为大多数歧义结构实例受到语义等方面的约束而化解了歧义 在一个纯粹句法的分析器里，我们最多只能期望它给出所有的歧义分析，并且尽可能少“虚报”歧义结构 理论上可以给出输入句子的所有可能的句法结构 对于一个中等长度的输入句子来说，分析过程十分复杂，很难分析出所有可能的句子结构 即使能够分析出句子所有可能的结构，也难以在巨大的句法分析结果集合中实现有效的消歧

歧义消解办法 不能指望仅仅通过某种精心设计的算法来消除所有的句法歧义 要想从根本上解决歧义问题，必须给分析器提供语义知识和词语搭配等方面的知识 另外，通过计算推导过程中所用到每条句法规则的概率，也能在很大程度上减少句法歧义现象 算法分类 基于规则的方法 基于统计的方法

Statistical parsing NLP researchers have produced a range of (often free, open source) statistical parsers, which can parse any sentence and often get most of it correct Collins (C) or Bikel reimplementation (Java) Charniak or Johnson-Charniak parser (C++) Stanford Parser (Java) …

Statistical parsing applications High precision question answering systems (Pasca and Harabagiu SIGIR 2001) Improving biological named entity extraction (Finkel et al. JNLPBA 2004): Syntactically based sentence compression (Lin and Wilbur Inf. Retr. 2007) Extracting people’s opinions about products (Bloom et al. NAACL 2007) Improved interaction in computer games (Gorniak and Roy, AAAI 2005) Helping linguists find data (Resnik et al. BLS 2005) Source sentence analysis for MT (Xu et al. 2009)

概率上下文无关语法 PCFG的优点 PCFG，Probabilistic Context Free Grammars 在一部有歧义的语法中，如果参数（规则的概率）选择适当，正确的分析一般会有较高的概率，因而有利于减少句法歧义 由于在分析过程中可以尽早删除那些概率较低的局部分析，因此能加快分析过程 可以用语料库来定量比较两个语法的性能。如果用语法G2时语料库中句子的平均概率高于用语法G1时句子的平均概率，就可以得到语法G2优于G1的结论

9.4.1 规则的概率 PCFG跟CFG基本相同，区别只在于给每条句法规则附加一个概率值 概率值来自 限制条件 语感 语料统计 左部符号相同的若干条规则，其概率之和等于1

9.4.2 分析树的概率 一棵分析树的概率，等于推导出这棵分析树时所使用的各条规则的概率的乘积，即用来展开各节点n的规则r的概率的乘积

Example S0.1 NP0.3 DJ0.4 NP0.3 VP1.0 de n VC0.5 的 狗 NP0.3 VC0.3 utl n 了 猎人 vt adj 咬 死

S0.2 VP1.0 VC0.5 NP0.3 VC0.3 DJ0.6 utl NP0.3 了 vt adj NP0.3 de n 咬 死 的 狗 n 猎人

9.4.3 PCFG的三个基本问题

PRG与HMM的关系

Extended CKY Parsing 0 fish 1 people 2 fish 3 tanks 4 S → NP VP 0.9 N → fish 0.2 V → fish 0.6 NP → N 0.14 VP → V 0.06 S → VP 0.006 VP → V NP 0.105 NP → NP NP 4.9e-3 S → VP 1.05e-2 N → people 0.5 V → people 0.1 NP → N 0.35 VP → V 0.01 S → VP 0.001 S → NP VP 0.9 S → VP 0.1 VP → V NP 0.5 VP → V 0.1 VP → V PP 0.4 NP → NP NP 0.1 NP → NP PP 0.2 NP → N 0.7 N → people 0.5 N → fish 0.2 N → tanks 0.2 N → rods 0.1 V → people 0.1 V → fish 0.6 V → tanks 0.3 N → fish 0.2 V → fish 0.6 NP → N 0.14 VP → V 0.06 S → VP 0.006 VP → V NP S → NP VP NP → NP NP S → VP 0.5*0.6*0.35=0.105 0.9*0.14*0.01=1.26e-3 0.1*0.14*0.35=4.9e-3 0.1*0.105=1.05e-2 N → tanks 0.2 V → tanks 0.3 NP → N 0.14 VP → V 0.03 S → VP 0.003

Extended CKY Parsing 0 fish 1 people 2 fish 3 tanks 4 S → NP VP 0.9 N → fish 0.2 V → fish 0.6 NP → N 0.14 VP → V 0.06 S → VP 0.006 VP → V NP 0.105 NP → NP NP 4.9e-3 S → VP 1.05e-2 N → people 0.5 V → people 0.1 NP → N 0.35 VP → V 0.01 S → VP 0.001 VP → V NP 0.7e-2 NP → NP NP 4.9e-3 S → NP VP 1.89e-2 S → NP VP 0.9 S → VP 0.1 VP → V NP 0.5 VP → V 0.1 VP → V PP 0.4 NP → NP NP 0.1 NP → NP PP 0.2 NP → N 0.7 N → people 0.5 N → fish 0.2 N → tanks 0.2 N → rods 0.1 V → people 0.1 V → fish 0.6 V → tanks 0.3 N → fish 0.2 V → fish 0.6 NP → N 0.14 VP → V 0.06 S → VP 0.006 VP → V NP S → NP VP NP → NP NP S → VP 0.5*0.1*0.14=0.007 0.9*0.35*0.06=1.89e-2 0.1*0.35*0.14=4.9e-3 0.1*0.007=0.7e-3 N → tanks 0.2 V → tanks 0.3 NP → N 0.14 VP → V 0.03 S → VP 0.003

Extended CKY Parsing 0 fish 1 people 2 fish 3 tanks 4 S → NP VP 0.9 N → fish 0.2 V → fish 0.6 NP → N 0.14 VP → V 0.06 S → VP 0.006 VP → V NP 0.105 NP → NP NP 4.9e-3 S → VP 1.05e-2 N → people 0.5 V → people 0.1 NP → N 0.35 VP → V 0.01 S → VP 0.001 VP → V NP 0.7e-2 NP → NP NP 4.9e-3 S → NP VP 1.89e-2 S → NP VP 0.9 S → VP 0.1 VP → V NP 0.5 VP → V 0.1 VP → V PP 0.4 NP → NP NP 0.1 NP → NP PP 0.2 NP → N 0.7 N → people 0.5 N → fish 0.2 N → tanks 0.2 N → rods 0.1 V → people 0.1 V → fish 0.6 V → tanks 0.3 N → fish 0.2 V → fish 0.6 NP → N 0.14 VP → V 0.06 S → VP 0.006 VP → V NP 0.042 NP → NP NP 1.96e-3 S → VP 4.2e-3 VP → V NP S → NP VP NP → NP NP S → VP 0.5*0.6*0.14=0.042 0.9*0.14*0.03=3.78e-3 0.1*0.14*0.14=1.96e-3 0.1*0.042=4.2e-3 N → tanks 0.2 V → tanks 0.3 NP → N 0.14 VP → V 0.03 S → VP 0.003

Extended CKY Parsing 0 fish 1 people 2 fish 3 tanks 4 S → NP VP 0.9 N → fish 0.2 V → fish 0.6 NP → N 0.14 VP → V 0.06 S → VP 0.006 VP → V NP 0.105 NP → NP NP 4.9e-3 S → VP 1.05e-2 NP → NP NP 6.86e-5 VP → V NP 1.47e-3 S → NP VP 8.82e-3 N → people 0.5 V → people 0.1 NP → N 0.35 VP → V 0.01 S → VP 0.001 VP → V NP 0.7e-2 NP → NP NP 4.9e-3 S → NP VP 1.89e-2 S → NP VP 0.9 S → VP 0.1 VP → V NP 0.5 VP → V 0.1 VP → V PP 0.4 NP → NP NP 0.1 NP → NP PP 0.2 NP → N 0.7 N → people 0.5 N → fish 0.2 N → tanks 0.2 N → rods 0.1 V → people 0.1 V → fish 0.6 V → tanks 0.3 N → fish 0.2 V → fish 0.6 NP → N 0.14 VP → V 0.06 S → VP 0.006 VP → V NP 0.042 NP → NP NP 1.96e-3 S → VP 4.2e-3 S → NP VP NP → NP NP VP → V NP S → VP 0.9*4.9e-3*0.06=2.646e-4 0.1*4.9e-3*0.14=6.86e-5 0.5*0.6*4.9e-3=1.47e-3 0.9*0.14*0.7e-2=8.82e-3 0.1*0.14*4.9e-3=6.86e-5 0.1*1.47e-3=1.47e-4 N → tanks 0.2 V → tanks 0.3 NP → N 0.14 VP → V 0.03 S → VP 0.003

Extended CKY Parsing 0 fish 1 people 2 fish 3 tanks 4 S → NP VP 0.9 N → fish 0.2 V → fish 0.6 NP → N 0.14 VP → V 0.06 S → VP 0.006 VP → V NP 0.105 NP → NP NP 4.9e-3 S → VP 1.05e-2 NP → NP NP 6.86e-5 VP → V NP 1.47e-3 S → NP VP 8.82e-3 N → people 0.5 V → people 0.1 NP → N 0.35 VP → V 0.01 S → VP 0.001 VP → V NP 0.7e-2 NP → NP NP 4.9e-3 S → NP VP 1.89e-2 NP → NP NP 6.86e-5 VP → V NP 9.8e-5 S → NP VP 1.323e-2 S → NP VP 0.9 S → VP 0.1 VP → V NP 0.5 VP → V 0.1 VP → V PP 0.4 NP → NP NP 0.1 NP → NP PP 0.2 NP → N 0.7 N → people 0.5 N → fish 0.2 N → tanks 0.2 N → rods 0.1 V → people 0.1 V → fish 0.6 V → tanks 0.3 N → fish 0.2 V → fish 0.6 NP → N 0.14 VP → V 0.06 S → VP 0.006 VP → V NP 0.042 NP → NP NP 1.96e-3 S → VP 4.2e-3 S → NP VP NP → NP NP VP → V NP S → VP 0.9*4.9e-3*0.03=1.323e-4 0.1*4.9e-3*0.14=6.86e-5 0.5*0.1*1.96e-3=9.8e-5 0.9*0.35*0.042=1.323e-2 0.1*0.35*1.96e-3=6.86e-5 0.1*9.8e-5=9.8e-6 N → tanks 0.2 V → tanks 0.3 NP → N 0.14 VP → V 0.03 S → VP 0.003

Extended CKY Parsing 0 fish 1 people 2 fish 3 tanks 4 S → NP VP 0.9 N → fish 0.2 V → fish 0.6 NP → N 0.14 VP → V 0.06 S → VP 0.006 VP → V NP 0.105 NP → NP NP 4.9e-3 S → VP 1.05e-2 NP → NP NP 6.86e-5 VP → V NP 1.47e-3 S → NP VP 8.82e-3 S → NP VP 1.8522e-4 NP → NP NP 9.604e-7 VP → V NP 2.058e-5 N → people 0.5 V → people 0.1 NP → N 0.35 VP → V 0.01 S → VP 0.001 VP → V NP 0.7e-2 NP → NP NP 4.9e-3 S → NP VP 1.89e-2 NP → NP NP 6.86e-5 VP → V NP 9.8e-5 S → NP VP 1.323e-2 S → NP VP 0.9 S → VP 0.1 VP → V NP 0.5 VP → V 0.1 VP → V PP 0.4 NP → NP NP 0.1 NP → NP PP 0.2 NP → N 0.7 N → people 0.5 N → fish 0.2 N → tanks 0.2 N → rods 0.1 V → people 0.1 V → fish 0.6 V → tanks 0.3 N → fish 0.2 V → fish 0.6 NP → N 0.14 VP → V 0.06 S → VP 0.006 VP → V NP 0.042 NP → NP NP 1.96e-3 S → VP 4.2e-3 S → NP VP NP → NP NP VP → V NP S → VP 0.9*6.86e-5*0.03=1.8522e-6 0.1*6.86e-5*0.14=9.604e-7 0.9*4.9e-3*0.042=1.8522e-4 0.1*4.9e-3*1.96e-3=9.604e-7 0.5*0.6*6.86e-5=2.058e-5 0.9*0.14*9.8e-5=1.2348e-5 0.1*0.14*6.86e-5=9.604e-7 0.1*2.058e-5=2.058e-6 N → tanks 0.2 V → tanks 0.3 NP → N 0.14 VP → V 0.03 S → VP 0.003

PCFG的问题 问题1：独立性假设（independence assumption） S → NP VP NP → DT NN

PCFG的问题 问题1：独立性假设（independence assumption） Example of Non-Independence: the expansion of an NP is highly dependent on the parent of the NP (i.e., subjects vs. objects).

PCFG的问题 问题1：独立性假设（independence assumption） 问题2：缺乏对单词的敏感性 p(VP → V NP NP) = 0.00151 p(VP → V NP NP | said) = 0.00001 p(VP → V NP NP | gave) = 0.01980

PCFG的问题 问题1：独立性假设（independence assumption） 问题2：缺乏对单词的敏感性

词汇化PCFG 每个成分都有一个中心词（head） 词汇化的树

提纲 9.1 语法类型 9.2 自顶向下的句法分析 9.3 自底向上的句法分析 9.4 基于统计的句法分析 9.5 句法分析系统的评测 9.6 浅层句法分析 9.7 汉语句法分析的困难

9.5 句法分析系统的评测 主要任务 评测句法分析系统生成的树结构与手工标注的树结构之间的相似程度 性能指标 满意程度 准确率 召回率 效率

例

提纲 9.1 语法类型 9.2 自顶向下的句法分析 9.3 自底向上的句法分析 9.4 基于统计的句法分析 9.5 句法分析系统的评测 9.6 浅层句法分析 9.7 汉语句法分析的困难

9.6 浅层句法分析(shallow parsing) S.Abney，1991 也叫部分句法分析(partial parsing)或语块分析(chunk parsing)， 不要求得到完全的句法分析树，只要求识别其中的某些结构相对简单的成分，如非递归的名词短语、动词短语等 识别出来的结构通常被称作语块(chunk)，和短语概念通常可以换用 例 When [anyone] opens [a current account] at [a bank], [he] is lending [the bank] [money], [repayment] of [which] [he] demand at [any time], either in [cash] or by drawing [a cheque] in [favour] of [another person].

浅层句法分析的作用 一种预处理手段 有利于句法分析技术在大规模真实文本处理系统中迅速得到利用 减少待处理的节点数 使句子的整个结构更加清晰 有助于句法分析器实现正确的分析 有利于句法分析技术在大规模真实文本处理系统中迅速得到利用 很多NLP应用（如信息检索、文本分类等）并不象机器翻译那样需要对输入的句子作深层次的句法结构分析

基本名词短语识别 基本名词短语（Base Noun Phrase，BNP） 英语中的BNP 简单的，非嵌套的名词短语，即不含其它名词短语的名词短语 （1）由序数词、基数词和限定词（包括冠词、指示形容词、指示代词、名词所有格、wh-限定词、数量限定词）修饰的名词短语。 （2）由形容词和名词修饰的名词短语。 例 When [anyone] opens [a current account] at [a bank], [he] is lending [the bank] [money], [repayment] of [which] [he] demand at [any time], either in [cash] or by drawing [a chenque] in [favour] of [another person].

基本名词短语识别 基本名词短语（Base Noun Phrase，BNP） 英语中的BNP 汉语中的BNP 甲级联赛 产品结构 空中走廊 下岗女工 促销手段 太空旅行 自然语言处理 企业承包合同 第四次中东战争 复杂的特征 这台计算机 对于形势的估计 明朝的古董 11万职工 高速发展的经济 很大成就 研究与发展 老师写的评语

浅层句法分析方法分类 基于规则的方法 基于统计的方法 规则于统计相结合的方法

9.6.1基于规则的方法 9.6.1.1 有限状态层叠法 Finite-state cascades， Abney，1991

有限状态层叠法包括多个层级（Layer），分析逐层进行。 分析过程包括一系列状态转换，用Ti表示。它以Li-1级的输出为输入，并产生Li作为输出。 每一个转换定义为一个模式的集合。 每一个模式包括一个范畴符号和一个正则式。 在模式匹配过程中，如遇到冲突（即两个或两个以上的模式都可以运用），则按最长匹配原则选择合适的模式。 如果输入中的一个元素找不到相应的匹配模式，则把它直接输出，继续下一个元素的匹配。 该技术虽然是面向完全句法分析的，但由于其对完全句法分析的任务进行了分解，所以其技术也可以归入浅层分析的范畴

9.6.1.2基于实例的规则学习方法 Cardie & Pierce(1998) 基本思想 把标注好短语信息的语料库分为两个部分，一部分用于训练，另一部分用于剪枝。 首先从训练的语料中得到一组名词短语的组成模式规则，然后把得到的这些规则应用到剪枝的语料中，对这些规则进行打分。 比如，如果一个规则识别出一个正确的短语得1分，识别出一个错误的短语得-1分， 这样根据每条规则的总的得分情况对规则进行删减，去掉那些得分低的规则。最后得到的一组规则能保证得到较高的正确率。 应用这些规则来识别文本中的名词短语的方法很简单，就是简单的模式匹配方法，在遇到规则冲突时，采用最长匹配原则。

例 从训练语料中归纳出的规则 …… BNP → det n n BNP → det a n BNP → det n BNP → n BNP → n n BNP → a n 限定词（Determiner） 冠词 不定冠词：a 、 an 定冠词：the 零冠词 形容词性的代词 物主限定词 my, your, his, her, our, your, their, one's, its. 名词属格 John's, my friend's. 指示限定词 this, that, these, those, such. 关系限定词 whose, which. 疑问限定词 what, which, whose. 不定限定词 no, some, any, each, every, enough, either, neither, all, both, half, several, many, much, (a) few, (a) little, other, another. 数词 基数词、和序数词、倍数词、分数词 量词 a lot of, lots of, plenty of, a great of, a good deal of, a large of, a small amount of, a quantity of, a great of, a good number of等。

例 从训练语料中归纳出的规则 剪枝语料 …… BNP → det n n BNP → det a n BNP → det n BNP → n BNP → n n BNP → a n 剪枝语料 When [anyone] opens [a current account] at [a adv pron v det a n prep det bank], [he] is lending [the bank] [money], n pron v v-in det n n [repayment] of [which] [he] demand at [any n prep pron pron v prep det time], either in [cash] or by drawing [a chenque] n conj prep n conj prep v-ing det n in [favour] of [another person]. prep n prep det n

例 从训练语料中归纳出的规则 …… BNP → det n n - （-1分） BNP → det a n + （+1分） BNP → n ++ （+2分） BNP → n n （0分） BNP → a n + （+1分）

9.6.2 基于统计的方法 9.6.2.1 基于HMM的方法 任意一对词类标记之间存在5种可能的状态 (1) [ (2) ] (3) ][ (4) I (5) O

9.6.2.2 基于互信息的方法 计算一对词类标记之间的互信息 互信息值越高，X和Y 组成短语的可能性越大

9.6.2.3 2统计法

9.6.3 规则于统计相结合的方法 基于转换的错误驱动学习方法 BNP标注符号 Ramshaw and Marcus（1995） BNP标注符号 O——BNP边界外部的单词； I——处于BNP内部的单词； L——左边界处的单词，对应于“[”； R——右边界处的单词，对应于“]”； S——独立成为一个BNP的单词，对应于“[]” 例：[he] puts [his dirty hand] in [the bag]”

规则举例 ①0:Cate=WP+0:BZ=S+1:Cate=NN→ChangeTo(L) 例：[What/WP] color/NN is/VBZ [it/PRP] ?/. →[What/WP color/NN] is/VBZ [it/PRP] ?/. ②0:Cate=RB+0:BZ=L+1:Cate=NNS→ChangeTo(O) 例：[Those/DT] are/VBP [not/RB desks/NNS] ./. →[Those/DT] are/VBP not/RB [desks/NNS] ./. ③0:Cate=JJ+0:BZ=L+1:Cate=CC+2:Cate=JJ→ChangeTo(O) 例：[They/PRP] are/VBP [black/JJ and/CC white/JJ] ./. →[They/PRP] are/VBP black/JJ and/CC white/JJ ./.

提纲 9.1 语法类型 9.2 自顶向下的句法分析 9.3 自底向上的句法分析 9.4 基于统计的句法分析 9.5 句法分析系统的评测 9.6 浅层句法分析 9.7 汉语句法分析的困难

9.7 汉语句法分析的困难 ①分词错误 分词结果很难达到100%正确率，因此汉语parser的输入存在噪音

②词性标注错误 名词 不使用限定词的名词普遍存在 动词 动词出现的形式不变

限定词 冠词 形容词性的代词 数词 量词 不定冠词：a 、 an 定冠词：the 零冠词 物主限定词 名词属格 指示限定词 关系限定词 my, your, his, her, our, your, their, one's, its. 名词属格 John's, my friend's. 指示限定词 this, that, these, those, such. 关系限定词 whose, which. 疑问限定词 what, which, whose. 不定限定词 no, some, any, each, every, enough, either, neither, all, both, half, several, many, much, (a) few, (a) little, other, another. 数词 基数词、和序数词、倍数词、分数词 量词 a lot of, lots of, plenty of, a great of, a good deal of, a large of, a small amount of, a quantity of, a great of, a good number of等。

③词性与句子成分之间不存在简单的一一对应关系 主语 名词短语 动词短语 学习外语解决了我们的翻译问题 形容词短语 谓语 我今年二十八。 宾语 我决定学习外语。

解决句子结构歧义问题的关键是确定句子的谓语动词 英语句子通过动词的形态变化使得句中通常只存在一个动词(and 和o r 结构除外) I hope that I have said nothing to pain you. 汉语句子允许多个动词存在而无形态变化 学习 外语 解决 了 我们 的 翻译 问题 我 决定 学习 外语 因而在分析汉语句子时必须先确定主动词, 而主动词的确定又是汉语分析的一个老大难问题, 仅通过句法分析是很难确定的。

④语法灵活 虚词并非非用不可，特别是在口语里，虚词更少，因此虚词只能是解决词与词、句与句关系问题的辅助手段； 例：“放桌上吧”

⑤复句 英语 汉语 单句与单句之间需要有显式的连接词或短语 单句与单句之间可以简单通过逗号或分号连接成一个复杂的“句群”式长句（“流水复句”） 例：我现已步入中年，每天挤车，搞得我筋疲力尽，这种情况，直接影响我的工作，家里的孩子也没人照顾

中华人民共和国国家标准标点符号用法 点号 标号 句末点号 句内点号 句号、问号、叹号 句内点号 逗号、顿号、分号、冒号 标号 引号、括号、破折号、省略号、着重号、连接号、间隔号（·）、书名号和专名号。

逗号 句子内部主语与谓语之间 句子内部动词与宾语之间 句子内部状语和其修饰的部分之间 并列短语之间 复句内各分句之间 逗号　　 句子内部主语与谓语之间 例如：我们看得见的星星，绝大多数是恒星。 句子内部动词与宾语之间 例如： 应该看到，科学需要一个人贡献毕生的精力。 句子内部状语和其修饰的部分之间 例如： 对于这个城市，他并不陌生。 并列短语之间 例如：我喜欢在春天去观赏桃花，在夏天去欣赏荷花，在秋天去观赏红叶，但更喜欢在冬天去欣赏雪景。 复句内各分句之间 例如： 据说苏州园林有一百多处，我到过的不过十多处。

本章小结 文法类型 自顶向下的句法分析 自底向上的句法分析 基于统计的句法分析 句法分析系统的评测 浅层句法分析 汉语句法分析的困难 移进－归约算法 欧雷（Earley）分析法 线图分析法 CYK分析法 基于统计的句法分析 句法分析系统的评测 浅层句法分析 基于规则的方法 有限状态层叠法 基于实例的规则学习方法 基于统计的方法 基于HMM的方法 基于互信息的方法 2统计法 基于转换的错误驱动学习方法 汉语句法分析的困难

结束