NLP-句法分析之线图分析算法
句法分析之线图分析算法
移进规约算法评价：
上节课我们学习了移进规约算法，该算法为了得到正确的分析结果，需要在每次分析失败时都强制性回
溯，直到分析成功。可以看到，采用回溯算法将导致大量的冗余操作，效率非常低。
本节我们介绍另外一种自底向上算法--线图分析算法（从字符串逐步鬼月初初始符号S的方法）。
线图相关基本概念：
(1). 线图：一组节点和边的集合，本质上也是图的一种。
(2). 结点：对应着输出字符串中的字符间隔，也就是说，如果我们有一个文本串: 我(N)是(V)上级(N)派(V)来(V)的(de)，对应的词性标注为: | N | V | N | V | V | de |，'|'表示一个分割；可见，结点数 = 字符间隔数 =输入符号串字符数 + 1
(3). 边：连接两个结点，边上有权值，称作标记，为非终结符或是终结符。
(4). 简单举个例子：
(5). 在自左至右分析输入字符串时，需要引入点规则表明当前分析的状态
点规则：上下文无关文法与圆点 ：用来表示当前文法已经规约出的部分(圆点左部)以及期望得到的部分(圆点右部)；整数i与整数j : 当前点规则作用的字串范围。
比如：S -> NP·VP <0,4>表示的是：在寻找S时的文法S ->NP VP，在输入字符串的0~4之间已经得到了一个NP，期望后面的会给出一个VP。
(6). 算法运行需要三个部分：线图；议程表（待处理表）；活动弧；他们的作用如下图所示
(7). 算法描述：
step1：将待分析字符串w植入输入缓冲区中，清空议程表。
step2：循环执行下列步骤，知道输入缓冲区和agenda为空：
1）若议程表栈为空，从输入缓冲区中取出一个字符，把该字符及其起止位置(P1, P2)压入议程表栈中
2）若议程表栈不空，弹出栈顶元素：i,j,L，表示的是边ij之间是一个L，所以我们在图表的i，j两节点之间连一条边，上标标记L。
3）这时候由于我们新增了一个文法符号，我们需要检查一下，根据我们新加入的边和我们的文法规则，会不会出现新的点规则：检查规则中的规则，对所有形如A -> L\(\beta\)的规则，我们就可以在活动弧中新增一条起止节点为i,j的弧，弧上标注A -> L · \(\beta\) 这样的点规则。
4）同时我们还需要检查一下，根据我们新加入的边和已有的活动弧中，是否可以将活动弧的文法规约到更进一步：检查所有的活动弧，如果存在起止位置为k,i且弧上规则为B -> \(\alpha\)·L\(\theta\)，那么久邢增一条活动弧，起止位置是k,j，弧上规则为B -> \(\alpha\)L·\(\theta\)
5）更新活动弧之后，我们需要检查一下，是否在更新活动弧的过程中完整规约出了一个非终结符，如果是那么我们就需要把新更新出来的非终结符作为标记同该弧的起止位置一起加入到议程表中：如果，一条互动弧起止位置是m,n，点规则是C -> \(\gamma\)X·，九江起止位置为(m,n)标记C压入议程表栈中。
(8). 优缺点分析:
优点：简单，易于实现，易于理解
缺点：效率较低，复杂度为O(\(n^3\))；严重依赖语法规则的质量；难区分歧义