自然语言理解句法分析算法..课件.ppt

1、句法分析算法上海交通大学陈玉泉第1页，共49页。内容提要n概述n带回溯的LR 分析法nCYKnEarley nChart Parsing第2页，共49页。概述第3页，共49页。程序设计语言分析算法n递归下降nLLnLR第4页，共49页。特点n高效n排歧策略简单nFirst集nFollow集n算符优先级第5页，共49页。自然语言文法的特点n歧义n歧义最大数量：n真歧义和伪歧义n咬死猎人的狗（v n 的 n）n建设公路的需要（v n 的 n）n他和我的爸爸（r 和 r 的 n）n他和他的爸爸（r 和 r 的 n）第6页，共49页。算法应该n容纳歧义n允许二义文法n任何可能结果都应计算到n高效n在多

2、项式时间内得到结果n具备排序机制，启发式搜索策略第7页，共49页。一些算法n自顶向下n自底向上n带回溯的LR 分析法nCYKnEarley nChart Parsing第8页，共49页。使用的例子n输入：n一/m 张/q 火车/n 票/nn文法：nNP NP NP(1)nNP MP NP(2)nNP n(3)nMP m q(4)第9页，共49页。期望分析结果第10页，共49页。Top-down自顶向下的方法又称为基于预测的方法。这种方法是先产生对后面将要出现的成分的预期，然后再通过逐步吃进待分析的字符串来验证预期。n如果预期得到了证明，就说明待分析的字符串可以被分析为所预期的句法结构。n如果某

3、一个环节上预期出了差错，那就要用另外的预期来替换（即回溯）。n如果所有环节上所有可能的预期都被吃进的待分析字符串所“反驳”，那就说明待分析的字符串不可能是一个合法的句子，分析失败。第11页，共49页。Top-downNP MPNPNP MP NP(2)第12页，共49页。Top-downNPNPNPNP MP NP(s)MP m q(4)mq一张第13页，共49页。Top-downNPNPNPNP MP NP(s)MP m q(4)mq一张NPNPnNP NP NP(1)第14页，共49页。Top-downNPNPNPNP MP NP(s)MP m q(4)mq一张NPNPnNP NP NP(

4、1)nn火车票第15页，共49页。Bottom-up自底向上的方法也叫基于归约的方法。这种方法是先逐步吃进待分析字符串，把它们从局部到整体层层归约为可能的成分。n如果整个待分析字符串被归约为开始符号S，那么分析成功。n如果在某个局部证明不可能有任何从这里把整个待分析字符串归约为句子的方案，那么就需要回溯。n如果经过回溯始终无法将待分析字符串归约为S，那么分析失败。第16页，共49页。Bottom-up一张火车票mqnn第17页，共49页。Bottom-up一张火车票mqnnMP第18页，共49页。Bottom-up一张火车票mqnnMPNP第19页，共49页。Bottom-up一张火车票mqn

5、nMPNPNP第20页，共49页。Bottom-up一张火车票mqnnMPNPNPNP第21页，共49页。Bottom-up一张火车票mqnnMPNPNPNPNP第22页，共49页。带回溯的LR第23页，共49页。组成部分nShift-Reduce-Goto 表n分析栈n输入队列n引入备份状态，解决移进规约冲突第24页，共49页。LR 分析表的构造n0nS .NPnNP .NP NPnNP .nnNP .MP NPnMP .m qn4nS NP.nNP NP.NPnNP .NP NPnNP .nnNP .MP NPnMP .m qn3nNP MP.NPnNP .NP NPnNP .nnNP .

6、MP NPnMP .m qn5nNP MP NP.nNP NP.NPnNP .NP NPnNP .nnNP .MP NPnMP .m qn6nNP NP NP.nNP NP.NPnNP .NP NPnNP .nnNP .MP NPnMP .m qn1nMP m.qn2nMP m q.n7nNP n.第25页，共49页。过程nThe Shift-reduce Table and the parsing processstatusmqn$NPMP0s1s7431s22r4r4r4r43s1s7534s1s7acc635s1 r2r2s7 r2r2636s1 r1r1s7 r1r1637r3r3r3

7、r3StackInput QueueBackup Status$0 m q n n$0 m 1q n n$0 m 1 q 2n n$0 MP 3n n$0 MP 3 n 7n$0 MP 3 NP 5n$0 MP 3 NP 5 n 7$($0 NP 4)(n$)$0 MP 3 NP 5 NP 6$($0 NP 4)(n$)$0 MP 3 NP 5$($0 NP 4)(n$)$0 NP 4$($0 NP 4)(n$)$0 acc$($0 NP 4)(n$)$0 NP 4 n$0 NP 4 n 7$0 NP 4 NP 6$0 NP 4$0 acc$(1)NP NP NP(2)NP MP NP(3)N

8、P n(4)MP m q第26页，共49页。过程（cont.）$0 m q n n$0 m 1q n n$0 m 1 q 2n n$0 MP 3n n$0 MP 3 n 7n$0 MP 3 NP 5 n$0 MP 3 NP 5 n 7$0 MP 3 NP 5 NP 6$0 MP 3 NP 5$0 NP 4$0 acc$0 NP 4n$0 NP 4 n 7$0 NP 4 NP 6$0 NP 4$0 acc$第27页，共49页。算法分析n类似深度优先搜索n如果改变备份栈顺序，可以实现其它搜索策略。（agenda）n自底向上n复杂度为指数n思考：有没有办法变成多项式？（GLR）第28页，共49页。C

9、YK第29页，共49页。组成部分n一张二维表，存储中间结果n从小的成分，逐渐计算到大的成分第30页，共49页。前提条件n文法符合chomsky范式n文法只有两种形式：A B C 其中，A,B,C都为非终结符A a 其中，a为终结符第31页，共49页。算法数据结构n一个二维矩阵：M(i,j)n每一个元素M(i,j)对应于输入句子中某一个跨度（Span）上所有可能形成的短语的非终结符的集合n横坐标i：该跨度左侧第一个词的位置n纵坐标j：该跨度包含的词数第32页，共49页。算法描述n初始化nFor int i=0 to n-1if W(i,i+1)=a&exit AaAdd A to M(i,i+1

10、)n计算nFor int l=2 to nfor int k=0 to n-lfor int j=1 to l-1for each A B Cif(B in M(k,k+j)and C in M(k+j,k+l)add A to M(k,k+l)n结果M(0,n)is the set of all results;第33页，共49页。CYK Examplem(1)q(2)N(5),NP(6)n(3),NP(4)一张火车票MP(7=1+2)NP(8=4+6)NP(9=7+4)NP(10=9+6),NP(11=7+8)第34页，共49页。算法分析n文法必须二元化n广度优先搜索n自底向上nO(n3)

11、，动态规划思想第35页，共49页。Earley 算法第36页，共49页。描述n规则中加入“.”表示当前分析程度n一张二维表n引入预测机制n这个算法可以认为是三个步骤的不断循环：n预测（predict）n扫描（scan）n完成（complete）第37页，共49页。基本概念n一个状态由四部分组成：n上下文无关文法规则n圆点（圆点左边的部分是已分析的，右边是待分析的）n整数i:状态起点（已分析子串的起点）n整数j:状态终点（已分析子串的终点）i jn比如：第38页，共49页。基本操作n预测（Predicator）：如果圆点右方是一个非终结符，那么以该非终结符为左部的规则都有匹配的希望，也就是说分析

12、器可以预测这些规则都可以建立相应的项目。n扫描（Scanner）：如果圆点右方是一个终结符，就将圆点向右方扫描一个字符间隔，把匹配完的字符“让”到左方。n归约（Completer）：如果圆点右方没有符号（即圆点已经在状态的结束位置），那么表示当前状态所做的预测已经实现，因而可以将当前状态（Si）与已有的包含当前状态的状态(Sj)进行归约（合并），从而扩大Sj覆盖的子串范围第39页，共49页。Earley Example 一一 张张 火车火车 票票5)m7)q14)n23)n1)NP 。NP NP2)NP 。MP NP3)NP 。n4)MP 。m q6)=4+5 MP m。q8)=6+7 MP

13、m q。9)=2+8 NP MP。NP10)NP 。NP NP11)NP 。MP NP12)NP 。n13)MP 。m q15)=12+14 NP n。16)=9+15 NP MP NP。17)=1+16 NP NP。NP18)=10+15 NP NP。NP19)NP 。NP NP20)NP 。MP NP21)NP 。n22)MP 。m q24)=21+23 NP n。25)=17+24 NP NP NP。26)=18+24 NP NP NP。27)=9+26 NP MP NP。PredictionScanningCompletionResults第40页，共49页。分析n自顶向下和自底向上的

14、结合，以自顶向下为主n引入了预测机制，在一般情况下改进了效率n最坏情况下复杂度为O(n3)第41页，共49页。图算法第42页，共49页。基本数据结构n图（二维表）n节点：词与词之间的间隙n弧：产生式在两个节点间的应用，分为活动弧和完成弧mqMP .m q.MP .m.q012第43页，共49页。基本数据结构（cont.）nAgenda:可以按某种顺序排列的队列（stack,queue,），存放还没有处理过的弧。n弧的处理（旧弧产生新弧）：n扩展：活动弧+完成弧n触发：完成弧mqMP .m q.MP .m.q第44页，共49页。算法描述n1。将所有单词作为完成弧放入agenda，按某种排序策略排

15、序，把结果表清空。n2。如果agenda为空，转入6n3。从agenda中取出一条弧，如果是覆盖整个句子完成弧且规则右部是可接受文法符号，那么将弧放入结果表n4。如果不是，则进行弧的扩展与触发，将产生的新弧放入agenda，放入时满足agenda的排序规则n5。转入2n6。如果结果表空，则分析失败，否则返回结果表中的内容第45页，共49页。最左触发，向右扩展，后进先出的图算法mqnn 一 张 火车 票MP.m.qMP .m q.NP .MP.NPNP.n.NP.NP.NPNP .MP NP.NP.NP.NPNP.n.NP.NP NP.NP.MP NP.NP.NP NP.01423Grammar

16、:NP NP NPNP nNP MP NPMP m q (0,1)m(1,2)q(2,3)n(3,4)nagenda:Extended arcsTriggered arcs (1,2)q(2,3)n(3,4)n (0,1)MP.m.q(1,2)q(2,3)n(3,4)n (1,2)q(2,3)n(3,4)n (2,3)n(3,4)n (0,2)MP.m q.(2,3)n(3,4)n (2,3)n(3,4)n (0,2)NP.MP.NP(2,3)n(3,4)n (2,3)n(3,4)n (3,4)n (2,3)NP.n.(3,4)n (3,4)n (0,3)NP.MP NP.(2,3)NP.NP.NP(3,4)n (2,3)NP.NP.NP(3,4)n (0,3)NP.NP.NP(2,3)NP.NP.NP(3,4)n (2,3)NP.NP.NP(3,4)n (3,4)n (3,4)NP.n.(2,4)NP.NP NP.(0,4)NP.NP NP.(0,4)NP.NP NP.(0,4)NP.MP NP.(0,4)NP.NP NP.(0,4)NP.NP NP.第46页，共49页。Agenda的作用n实现多种搜索策略：n后进先出，深度优先n先进先出，广度优先n启发式搜索第47页，共49页。算法分析n灵活n自底向上nO(n3)第48页，共49页。Thank you!第49页，共49页。