PDF《第八章 句法分析》

第八章 句法分析

第八章 句法分析 詹卫东 http://ccl.

pku.edu.cn/doubtfire 提纲 ?

1 句法分析概说 ?

1 句法分析概说 ?

2 自顶向下分析法 ?

3 自底向上分析法 ?

4 小结 小结

2 1 句法分析概说 ? 文法 G ―― 语言 L 文法 语言 ? 分析算法 ? (1)给定一个字符串S,判定S是否属于L ? (2)给定一个字符串S,如果S属于L,给出S对应的树结构 S 他从美国来 * 他从来美国 VP PP * 他从来美国 PP N P N V 他从美国 来3他从美国 来[S [N 他] [VP [PP [P 从] [N 美国 ]] [V 来]]] 句法分析的不同类型 自顶向下(Top-down)句法分析 predicative parser 自底向上(Bottom-up)句法分析 shift-reduce parser 确定性句法分析 d t i i ti 确定性句法分析 deterministic parser 非确定性句法分析 non-deterministic parser 传统的非概率分析方法 概率方法(PCFG) 概率方法(PCFG) 完全句法分析

4 部分句法分析(partial parsing / shallow parsing) 自然语言 ―― 歧义无处不在 ? 我是县长 box ? 我是县长 我是县长派来的 ? Put the frog on the napkin in the box garden-path sentence/ 花园路径句 ? 麻子无头发黑脸大脚不大好看 frog napkin ? 麻子无头发黑脸大脚不大好看 麻子无 头发黑 脸大脚不大 好看 麻子 无头发 黑脸 大脚 不大好看

5 麻子 无头发 黑脸 大脚 不大好看 自然语言 ―― 歧义无处不在(续) 小王和小李结婚了 小王和小李都结婚了 S S NP NP VP NP NP VP NP NP VP PP 小王 和 小李 结婚 了NCNVle 小王 和 小李 结婚 了NPNVle

6 小王 和 小李 结婚 了 小王 和 小李 结婚 了 自然语言 ―― 歧义无处不在(续) 小王和小李结婚了 小王和小李都结婚了 S NP VP l NP NP VP VP 小王 和 小李 都 结婚 了NCNVle D

7 自然语言文法 ―― over generalization 大 眼睛 姑娘 大 钢铁 公司 实例 打伤 了 猎人 的 眼睛 打伤 了 眼睛 的 猎人 实例 大 钢铁 公司 A N N 模式 打伤 了 眼睛 的 猎人 V 了N的N模式 董永 和 七仙女 的 母亲 实例 董永 和 七仙女 的 母亲 董永 和 七仙女 的 孩子 和的实例 模式

8 N 和N的N模式 如何进行句法结构分析 ? 句法结构分析: 从 线性串 到 树结构 的映射. 如何在 对多中求解最优的映射? 如何在一对多中求解最优的映射? ? 需要做两件事: 1. 语言模型 语法体系形式化描述的任务 ? 语言成分有多少类(范畴)?

2 搜索算法 计算技术的任务 语言成分有多少类(范畴) ? 成分间组合模式有多少种? ? 成分组合的约束条件是什么? 2. 搜索算法 计算技术的任务 ? 如何快速找到正确的结构树

9 2 自顶向下分析法 ? 自顶向下的方法又称为基于预测的方法. 这种方法是先产生对后面将要出现的成分的预期,然后再通 过逐步吃进待分析的字符串来验证预期. 过逐步吃进待分析的字符串来验证预期. - 如果预期得到了证明,就说明待分析的字符串可以被分析 为所预期的句法结构 为所预期的句法结构. - 如果某一个环节上预期出了差错,那就要用另外的预期来 替换(即回溯). - 如果所有环节上所有可能的预期都被吃进的待分析字符串 所 反驳 ,那就说明待分析的字符串不可能是一个合法 的10 的 句子,分析失败. 分析示例 规则 词典 张三是县长派来的 规则: (1) S ? NP VP (2) NP ? N 词典: 张三:N 县长 N 张三是县长派来的 苍蝇是瞎子打死的 主意是董永想出来的 (2) NP ? N (3) NP ? CS 的(4) CS ? NP V '