句法分析(gao)精选.ppt

不同分析策略的比较 不同的分析策略在面对不同的语法规则和句子的时候，各有优势 对于某一种具体的自然语言，可能总体上会存在一种比较好的分析策略 移进-归约算法：概述 移进－归约算法：举例 移进－归约算法：冲突 移进－归约算法：示例 (1) 移进－归约算法：示例 (2) 移进－归约算法：示例 (3) 移进－归约算法：示例 (4) 移进－归约算法：示例 (5) 移进－归约算法：示例 (6) 移进－归约算法：示例 (7) 移进－归约算法：特点 移进－归约算法的改进 G=（Vt,Vn,S,P） Vt：终结符集合； Vn：非终结符集合； S：起始符号； P：规则集合（规则用产生式表示 * * * 左角分析法－示例 (3) 左角分析法－示例 (4) 左角分析法－示例 (5) 左角分析法－示例 (6) 左角分析法－示例 (7) 左角分析法－示例 (8) 左角分析法－示例 (9) 左角分析法－示例 (10) 左角分析法－示例 (11) 左角分析法－示例 (12) 左角分析法－示例 (13) 左角分析法－示例 (14) 左角分析法－示例 (15) 左角分析法－示例 (16) 左角分析法－示例 (17) 左角分析法－示例 (18) 左角分析法－示例 (19) 左角分析法－示例 (20) 左角分析法－示例 (21) 左角分析法－示例 (28) 左角分析法－示例 (29) 左角分析法－示例 (30) 左角分析法－示例 (31) 左角分析法－示例 (32) 左角分析法－示例 (33) 左角分析法－示例 (34) 左角分析法－示例 (35) 自顶向下分析法－示例 (8) 自顶向下分析法－示例 (9) 自顶向下分析法－示例 (10) 自顶向下分析法－示例 (11) 自顶向下分析法－示例 (12) 自顶向下分析法－示例 (13) 自顶向下分析法－示例 (14) 自顶向下分析法－示例 (15) 自顶向下分析法－示例 (16) 自顶向下分析法－示例 (17) 自顶向下分析法－示例 (18) 自顶向下分析法－示例 (19) 自顶向下分析法－示例 (20) 自底向上分析法－示例 (1) 自底向上分析法－示例 (2) 自底向上分析法－示例 (3) 自底向上分析法－示例 (4) 自底向上分析法－示例 (5) 自底向上分析法－示例 (6) 自底向上分析法－示例 (7) 自底向上分析法－示例 (8) 自底向上分析法－示例 (9) 自底向上分析法－示例 (10) 自底向上分析法－示例 (11) 自底向上分析法－示例 (12) 自底向上分析法－示例 (13) 自底向上分析法－示例 (14) 自底向上分析法－示例 (15) 自底向上分析法－示例 (16) 左角分析法－概述 左角分析法－示例 (1) 左角分析法－示例 (2) 句法分析 内容提要 语言结构 句法分析算法 内容提要 词语到句子的组合关系 词语之间的依赖关系 短语结构树 G=Vn,Vt,S,P Vn={S,NP VP……} Vt={小李，远远，地，小王，在草地 上 看书} P：S-N VP VP-DP VP DP-D U …… 依存结构树 内容提要 什么是句法分析 句法分析（Parsing）和句法分析器（Parser) 句法分析是从单词串得到句法结构的过程； 不同的语法形式，对应的句法分析算法也不尽相同； 由于短语结构语法（特别是上下文无关语法）应用 得最为广泛，因此以短语结构树为目标的句法分析 器研究得最为彻底； 很多其他形式语法对应的句法分析器都可以通过对 短语结构语法的句法分析器进行简单的改造得到。 0型语法：是一种无约束的短语结构语法 1型语法：又称上下文有关文法，规则形式为aXb→aYb 2型语法：又称上下文无关文法，规则形式为A→x，A必须是一个单独的非终结符，x∈（Vn∪Vt）* 3型语法：又称正则文法， 规则形式为A→Bt或A→t，A、B必须是一个单独的非终结符，t∈Vt，此时称为左线性文法；推导的过程能被自动机识别。 规则形式为A→tB或A→t，A、B必须是一个单独的非终结符，t∈Vt，此时称为右线性文法； 本讲义将主要介绍上下文无关语法的句法分析器。 与形式语言句法分析的比较 句法结构歧义的消解 (1) 句法结构的歧义消解 (2) 我是县长。 我是县长派来的。 咬死了猎人的狗跑了。 就是这条狼咬死了猎人的狗。 小王和小李的妹妹结婚了。 小王和小李的妹妹都结婚了。 例子－语法 例子－分析结果之一 例子－分析结果之二 另一个例子 另一个例子－分析结果 内容提要 句法分析的基本策略 上下文无关语法的分析算法 自顶向下和自底向上分析法 (1) 句法分析的过程也可以理解为句法树的 构造过程 所谓自顶向下分析法也就是先