句法分析前部分.ppt

第八章：句法分析;提纲：;★ 句法分析：是指对输入的单词序列（一般为句子）判断其构成是否合乎给定的语法，分析合乎语法的句子的句法结构 ★句法分析的任务： 1）判断输入的字符串是否属于某种语言 2）消除输入句子中词法和结构等方面的歧义 3）分析输入句子的内部结构，如成分构成、上下文关系等 ★类型： ? 短语结构分析 (Phrase parsing) ? 完全句法分析 (Full parsing) ? 局部句法分析 (Partial parsing) ? 依存句法分析 (Dependency parsing);;;;;;短语结构分析: ? 目标：实现高正确率、高鲁棒性 (robustness)、 高速度的自动句法分析过程。 ? 困难：自然语言中存在大量的复杂的结构 歧义 (structural ambiguity)。;?结构歧义 例如：(1) I saw a boy in the park. [ I saw a boy ] in the park. I saw a [ boy in the park]. (2) I saw a boy in the park with a telescope. (3) I saw a boy swimming on the bridge. (4) 关于鲁迅的文章。 (5) 把重要的书籍和手稿带走了。; 英语中的结构歧义随介词短语组合个数的增加而不断加深的， 这个组合个数我们称之为开塔兰数(Catalan number，记作CN)。 如果句子中存在这样 n (n为自然数)个介词短语，CN可由下式 获得 [Samuelsson, 2000]：;? 基本方法和开源的句法分析器： ? 基于CFG规则的分析方法： ? 线图分析法 (chart parsing) ? CYK 算法 ? Earley (厄尔利)算法 ? LR 算法 / Tomita 算法 … … － Top-down: Depth-first/ Breadth-first － Bottom-up;? 基于 PCFG 的分析方法 PCFG: Probabilistic Context-Free Grammar (有时也写作 Stochastic CFG, SCFG) ? 其他统计模型 ? 部分开源的句法分析器;线图分析法 ? 三种策略 ? 自底向上 (Bottom-up) ? 从上到下 (Top-down) ? 从上到下和从下到上结合;;执行操作： 查看任意相邻几条边上的词性串是否与某条重 写规则的右部相同，如果相同，则增加一条新的边 跨越原来相应的边，新增加边上的标记为这条重写 规则的头(左部)。重复这个过程，直到没有新的边 产生。;点规则：用于表示规则右部???归约(reduce)的程度。 设有规则：NP ? Det A N NP ? Det N NP ?A N 句子: The good book; 点规则：用于表示规则右部被归约(reduce)的程度。 设有规则：NP ? Det A N NP ? Det N NP ? A N 句子: The good book;? 数据结构 ? 线图(Chart)：保存分析过程中已经建立的成分(包括终结符和非 终结符)、位置(包括起点和终点)。通常以 n×n 的数组表示(n 为句子包含的词数)。 ? 代理表(待处理表)(Agenda)：记录刚刚得到的一些重写规则所代 表的成分，这些重写规则的右端符号串与输入词性 串(或短语标志串)中的一 段完全匹配，通常以栈 或线性队列表示。 ?活动边集(ActiveArc)：记录那些右端符号串与输入串的某一段相 匹配，但还未完全匹配的重写规则，通常以数组或 列表存储。;?算法描述： 从输入串的起始位置到最后位置，循环执行如下步骤： (1)