自然语言理解-句法分析算法(1)..

句法分析算法上海交通大学陈玉泉内容提要概述带回溯的LR分析法CYKEarleyChartParsing概述程序设计语言分析算法递归下降LLLR特点高效排歧策略简单First集Follow集算符优先级自然语言文法的特点歧义歧义最大数量：真歧义和伪歧义咬死猎人的狗（vn的n）建设公路的需要（vn的n）他和我的爸爸（r和r的n）他和他的爸爸（r和r的n）算法应该……容纳歧义允许二义文法任何可能结果都应计算到高效在多项式时间内得到结果具备排序机制，启发式搜索策略一些算法自顶向下自底向上带回溯的LR分析法CYKEarleyChartParsing使用的例子输入：一/m张/q火车/n票/n文法：NPNPNP(1)NPMPNP(2)NPn(3)MPmq(4)期望分析结果Top-down自顶向下的方法又称为基于预测的方法。这种方法是先产生对后面将要出现的成分的预期，然后再通过逐步吃进待分析的字符串来验证预期。如果预期得到了证明，就说明待分析的字符串可以被分析为所预期的句法结构。如果某一个环节上预期出了差错，那就要用另外的预期来替换（即回溯）。如果所有环节上所有可能的预期都被吃进的待分析字符串所“反驳”，那就说明待分析的字符串不可能是一个合法的句子，分析失败。Top-downNPMPNPNPMPNP(2)Top-downNPNPNPNPMPNP(s)MPmq(4)mq一张Top-downNPNPNPNPMPNP(s)MPmq(4)mq一张NPNPNPNPNP(1)Top-downNPNPNPNPMPNP(s)MPmq(4)mq一张NPNPNPNPNP(1)nn火车票Bottom-up自底向上的方法也叫基于归约的方法。这种方法是先逐步吃进待分析字符串，把它们从局部到整体层层归约为可能的成分。如果整个待分析字符串被归约为开始符号S，那么分析成功。如果在某个局部证明不可能有任何从这里把整个待分析字符串归约为句子的方案，那么就需要回溯。如果经过回溯始终无法将待分析字符串归约为S，那么分析失败。Bottom-up一张火车票mqnnBottom-up一张火车票mqnnMPBottom-up一张火车票mqnnMPNPBottom-up一张火车票mqnnMPNPNPBottom-up一张火车票mqnnMPNPNPNPBottom-up一张火车票mqnnMPNPNPNPNP带回溯的LR组成部分Shift-Reduce-Goto表分析栈输入队列引入备份状态，解决移进规约冲突LR分析表的构造0S’.NPNP.NPNPNP.nNP.MPNPMP.mq4S’NP.NPNP.NPNP.NPNPNP.nNP.MPNPMP.mq3NPMP.NPNP.NPNPNP.nNP.MPNPMP.mq5NPMPNP.NPNP.NPNP.NPNPNP.nNP.MPNPMP.mq6NPNPNP.NPNP.NPNP.NPNPNP.nNP.MPNPMP.mq1MPm.q2MPmq.7NPn.过程TheShift-reduceTableandtheparsingprocessstatusmqn$NPMP0s1s7431s22r4r4r4r43s1s7534s1s7acc635s1r2r2s7r2r2636s1r1r1s7r1r1637r3r3r3r3StackInputQueueBackupStatus$0mqnn$$0m1qnn$$0m1q2nn$$0MP3nn$$0MP3n7n$$0MP3NP5n$$0MP3NP5n7$($0NP4)(n$)$0MP3NP5NP6$($0NP4)(n$)$0MP3NP5$($0NP4)(n$)$0NP4$($0NP4)(n$)$0acc$($0NP4)(n$)$0NP4n$$0NP4n7$$0NP4NP6$$0NP4$$0acc$(1)NPNPNP(2)NPMPNP(3)NPn(4)MPmq过程（cont.）$0mqnn$$0m1qnn$$0m1q2nn$$0MP3nn$$0MP3n7n$$0MP3NP5n$$0MP3NP5n7$$0MP3NP5NP6$$0MP3NP5$$0NP4$$0acc$$0NP4n$$0NP4n7$$0NP4NP6$$0NP4$$0acc$算法分析类似深度优先搜索如果改变备份栈顺序，可以实现其它搜索策略。（agenda）自底向上复杂度为指数思考：有没有办法变成多项式？（GLR）CYK组成部分一张二维表，存储中间结果从小的成分，逐渐计算到大的成分前提条件文法符合chomsky范式文法只有两种形式：ABC其中，A,B,C都为非终结符Aa其中，a为终结符算法数据结构一个二维矩阵：{M(i,j)}每一个元素M(i,j)对应于输入句子中某一个跨度（Span）上所有可能形成的短语的非终结符的集合横坐标i：该跨度左侧第一个词的位置纵坐标j：该跨度包含的词数算法描述初始化Forinti=0ton-1ifW(i,i+1)==a&&exitAaAddAtoM(i,i+1)计算Forintl=2tonforintk=0ton-lforintj=1tol-1foreachABCif(BinM(k,k+j)andCinM(k+j,k+l))addAtoM(k,k+l)结果M(0,n)isthesetofallresults;CYKExamplem(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)算法分析文法必须二元化广度优先搜索自底向上O(n3)，动态规划思想Earley算法描述规则中加入“.”表示当前分析程度一张二维表引入预测机制这个算法可以认为是三个步骤的不断循环：预测（predict）扫描（scan）完成（complete）基本概念一个状态由四部分组成：1.上下文无关文法规则2.圆点·（圆点左边的部分是已分析的，右边是待分析的）3.整数i:状态起点（已分析子串的起点）4.整数j:状态终点（已分析子串的终点）i≤j比如：SNP·VP0,4基本操作预测（Predicator）：如果圆点右方是一个非终结符，那么以该非终结符为左部的规则都有匹配的希望，也就是说分析器可以预测这些规则都可以建立相应的项目。扫描（Scanner）：如果圆点右方是一个终结符，就将圆点向右方扫描一个字符间隔，把匹配完的字符“让”到左方。归约（Completer）：如果圆点右方没有符号（即圆点已经在状态的结束位置），那么表示当前状态所做的预测已经实现，因而可以将当前状态（Si）与已有的包含当前状态的状态(Sj)进行归约（合并），从而扩大Sj覆盖的子串范围EarleyExample一张火车票5)m7)q14)n23)n1)NP。NPNP2)NP。MPNP3)NP。n4)MP。mq6)=4+5MPm。q8)=6+7MPmq。9)=2+8NPMP。NP10)NP。NPNP11)NP。MPNP12)NP。n13)MP。mq15)=12+14NPn。16)=9+15NPMPNP。17)=1+16NPNP。NP18)=10+15NPNP。NP19)NP。NPNP20)NP。MPNP21)NP。n22)MP。mq24)=21+23NPn。25)=17+24NPNPNP。26)=18+24NPNPNP。27)=9+26NPMPNP。PredictionScanningCompletionResults分析自顶向下和自底向上的结合，以自顶向下为主引入了预测机制，在一般情况下改进了效率最坏情况下复杂度为O(n3)图算法基本数据结构图（二维表）节点：词与词之间的间隙弧：产生式在两个节点间的应用，分为活动弧和完成弧mqMP.mq.MP.m.q012基本数据结构（cont.）Agenda:可以按某种顺序排列的队列（stack,queue,…），存放还没有处理过的弧。弧的处理（旧弧产生新弧）：扩展：活动弧+完成弧触发：完成弧mqMP.mq.MP.m.q算法描述1。将所有单词作为完成弧放入agenda，按某种排序策略排序，把结果表清空。2。如果agenda为空，转入63。从agenda中取出一条弧，如果是覆盖整个句子完成弧且规则右部是可接受文法符号，那么将弧放入结果表4。如果不是，则进行弧的扩展与触发，将产生的新弧放入agenda，放入时满足agenda的排序规则5。转入26。如果结果表空，则分析失败，否则返回结果表中的内容最左触发，向右扩展，后进先出的图算法mqnn一张火车票MP.m.qMP.mq.NP.MP.NPNP.n.NP.NP.NPNP.MPNP.NP.NP.NPNP.n.NP.NPNP.NP.MPNP.NP.NPNP.01423Grammar:•NPNPNP•NPn•NPMPNP•MPmq•••(0,1)m•(1,2)q•(2,3)n•(3,4)nagenda:ExtendedarcsTriggeredarcs••••(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.mq.•(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.MPNP.•(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.NPNP.•(0,4)NP.NPNP.••••••(0,4)NP.NPNP.•••••(0,4)NP.MPNP.•(0,4)NP.NPNP.••••••(0,4)NP.NPNP.••••••Agenda的作用实现多种搜索策略：后进先出，深度优先先进先出，广度优先启发式搜索算法分析灵活自底向上O(n3)Thankyou!