句法分析I 张宇 哈尔滨工业大学计算机科学与技术学院 Zhangyu@irhit.edu.cn
句法分析I 张宇 哈尔滨工业大学计算机科学与技术学院 zhangyu@ir.hit.edu.cn
内容提要 ■什么是句法分析 ■与形式语言句法分析的比较 ■上下文无关语法的分析策略 自顶向下分析法 ■自底向上分析法 左角分析法 2021年2月9日9时14分 中文信息处理-句法分析
2021年2月9日9时14分 中文信息处理--句法分析 2 内容提要 ◼ 什么是句法分析 ◼ 与形式语言句法分析的比较 ◼ 上下文无关语法的分析策略 ◼ 自顶向下分析法 ◼ 自底向上分析法 ◼ 左角分析法
内容提要(续) ■上下文无关语法的分析算法 ■移进一归约算法 ■ Marcus确定性分析算法 ■CYK算法 Earley算法 Tomita算法 Chart算法 ■概率上下文无关语法 组块分析与部分分析 2021年2月9日9时14分 中文信息处理-句法分析
2021年2月9日9时14分 中文信息处理--句法分析 3 内容提要（续） ◼ 上下文无关语法的分析算法 ◼ 移进－归约算法 ◼ Marcus确定性分析算法 ◼ CYK算法 ◼ Earley算法 ◼ Tomita算法 ◼ Chart算法 ◼ 概率上下文无关语法 ◼ 组块分析与部分分析
什么是句法分析 句法分析( Parsing)和句法分析器( Parser) 句法分析是从单词串得到句法结构的过程 不同的语法形式,对应的句法分析算法也不尽相同 由于短语结构语法(特别是上下文无关语法)应用得 最为广泛,因此以短语结构树为目标的句法分析器研 究得最为彻底; ■很多其他形式语法对应的句法分析器都可以通过对短 语结构语法的句法分析器进行简单的改造得到。 ■本讲义将主要介绍上下文无关语法的句法分析器。 2021年2月9日9时14分 中文信息处理-句法分析
2021年2月9日9时14分 中文信息处理--句法分析 4 什么是句法分析 ◼ 句法分析（Parsing）和句法分析器（Parser) ◼ 句法分析是从单词串得到句法结构的过程； ◼ 不同的语法形式，对应的句法分析算法也不尽相同； ◼ 由于短语结构语法（特别是上下文无关语法）应用得 最为广泛，因此以短语结构树为目标的句法分析器研 究得最为彻底； ◼ 很多其他形式语法对应的句法分析器都可以通过对短 语结构语法的句法分析器进行简单的改造得到。 ◼ 本讲义将主要介绍上下文无关语法的句法分析器
与形式语言句法分析的比较 形式语言一般是人工构造的语言,是一种确定性的语 言,即对于语言中的任何一个句子,只有唯一的一种 句法结构是合理的,即使语法本身存在歧义,也往往 通过人为的方式规定一种合理的解释 如程序语言中的if. theif.then.else.结构,往往都人为规 定else子句与最接近的i子句配对: 而在自然语言中,歧义现象是天然地大量存在着的, 而且这些歧义的解释往往都有可能是合理的,因此, 对歧义现象的处理是自然语言句法分析器最本质的要 求 由于要处理大量的歧义现象,导致自然语言句法分析 器的复杂程度远高于形式语言的句法分析器。 2021年2月9日9时14分 中文信息处理-句法分析 5
2021年2月9日9时14分 中文信息处理--句法分析 5 与形式语言句法分析的比较 ◼ 形式语言一般是人工构造的语言，是一种确定性的语 言，即对于语言中的任何一个句子，只有唯一的一种 句法结构是合理的，即使语法本身存在歧义，也往往 通过人为的方式规定一种合理的解释。 ◼ 如程序语言中的if…thenif…then…else…结构，往往都人为规 定else 子句与最接近的if 子句配对； ◼ 而在自然语言中，歧义现象是天然地大量存在着的， 而且这些歧义的解释往往都有可能是合理的，因此， 对歧义现象的处理是自然语言句法分析器最本质的要 求。 ◼ 由于要处理大量的歧义现象，导致自然语言句法分析 器的复杂程度远高于形式语言的句法分析器
句法结构歧义的消解 人们正常交流中所使用的语言,放在特定的环 境下看,一般是没有歧义的,否则人们将无法 交流(某些特殊情况如幽默或双关语除外) 如果不考虑语言所处的环境和语言单位的上下 文,将会发现语言的歧义现象无所不在 结论:一般来说,语言单位的歧义现象在引入 更大的上下文范围或者语言环境时总是可以被 被消解的。句法分析的核心任务就是消解一个 句子在句法结构上的歧义 2021年2月9日9时14分 中文信息处理-句法分析 6
2021年2月9日9时14分 中文信息处理--句法分析 6 句法结构歧义的消解 ◼ 人们正常交流中所使用的语言，放在特定的环 境下看，一般是没有歧义的，否则人们将无法 交流（某些特殊情况如幽默或双关语除外） ◼ 如果不考虑语言所处的环境和语言单位的上下 文，将会发现语言的歧义现象无所不在； ◼ 结论：一般来说，语言单位的歧义现象在引入 更大的上下文范围或者语言环境时总是可以被 被消解的。句法分析的核心任务就是消解一个 句子在句法结构上的歧义
句法结构的歧义消解(续) ■我是县长。 我是县长派来的 ■咬死了猎人的狗跑了。 就是这条狼咬死了猎人的狗 小王和小李的妹妹结婚了 小王和小李的妹妹都结婚了。 2021年2月9日9时14分 中文信息处理-句法分析
2021年2月9日9时14分 中文信息处理--句法分析 7 句法结构的歧义消解（续） ◼ 我是县长。 我是县长派来的。 ◼ 咬死了猎人的狗跑了。 就是这条狼咬死了猎人的狗。 ◼ 小王和小李的妹妹结婚了。 小王和小李的妹妹都结婚了
例子一语法 ■小王和小李的妹妹结婚了 规则: 词典: S→NPVP 小王:N NP→ NPCNP 小李:N 和:C NP→N 妹妹:N NP→ np de n 结婚:V 了:1e VP→Vle 的:de 2021年2月9日9时14分 中文信息处理-句法分析
2021年2月9日9时14分 中文信息处理--句法分析 8 例子－语法 ◼ 小王和小李的妹妹结婚了
例子一分析结果之 小王和小李的妹妹结婚了 2021年2月9日9时14分 中文信息处理-句法分析
2021年2月9日9时14分 中文信息处理--句法分析 9 例子－分析结果之一
例子一分析结果之二 NP N de 小王和小李的妹妹结婚了 2021年2月9日9时14分 中文信息处理-句法分析 10
2021年2月9日9时14分 中文信息处理--句法分析 10 例子－分析结果之二
