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

《自然语言理解-句法分析算法(1)讲课讲稿.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、自然语言理解-句法分析算法(1)概述程序设计语言分析算法递归下降LLLR特点高效排歧策略简单First集Follow集算符优先级自然语言文法的特点歧义歧义最大数量：真歧义和伪歧义咬死猎人的狗（vn的n）建设公路的需要（vn的n）他和我的爸爸（r和r的n）他和他的爸爸（r和r的n）算法应该……容纳歧义允许二义文法任何可能结果都应计算到高效在多项式时间内得到结果具备排序机制，启发式搜索策略一些算法自顶向下自底向上带回溯的LR分析法CYKEarleyChartParsing使用的例子输入：一/m张/q火车/n票/n文

2、法：NPNPNP(1)NPMPNP(2)NPn(3)MPmq(4)期望分析结果Top-down自顶向下的方法又称为基于预测的方法。这种方法是先产生对后面将要出现的成分的预期，然后再通过逐步吃进待分析的字符串来验证预期。如果预期得到了证明，就说明待分析的字符串可以被分析为所预期的句法结构。如果某一个环节上预期出了差错，那就要用另外的预期来替换（即回溯）。如果所有环节上所有可能的预期都被吃进的待分析字符串所“反驳”，那就说明待分析的字符串不可能是一个合法的句子，分析失败。Top-downNPMPNPNPM

3、PNP(2)Top-downNPNPNPNPMPNP(s)MPmq(4)mq一张Top-downNPNPNPNPMPNP(s)MPmq(4)mq一张NPNPNPNPNP(1)Top-downNPNPNPNPMPNP(s)MPmq(4)mq一张NPNPNPNPNP(1)nn火车票Bottom-up自底向上的方法也叫基于归约的方法。这种方法是先逐步吃进待分析字符串，把它们从局部到整体层层归约为可能的成分。如果整个待分析字符串被归约为开始符号S，那么分析成功。如果在某个局部证明不可能有任何从这里把整个

4、待分析字符串归约为句子的方案，那么就需要回溯。如果经过回溯始终无法将待分析字符串归约为S，那么分析失败。Bottom-up一张火车票mqnnBottom-up一张火车票mqnnMPBottom-up一张火车票mqnnMPNPBottom-up一张火车票mqnnMPNPNPBottom-up一张火车票mqnnMPNPNPNPBottom-up一张火车票mqnnMPNPNPNPNP带回溯的LR组成部分Shift-Reduce-Goto表分析栈输入队列引入备份状态，解决移进规约冲突LR分析表的构造0S’.NPNP

5、.NPNPNP.nNP.MPNPMP.mq4S’NP.NPNP.NPNP.NPNPNP.nNP.MPNPMP.mq3NPMP.NPNP.NPNPNP.nNP.MPNPMP.mq5NPMPNP.NPNP.NPNP.NPNPNP.nNP.MPNPMP.mq6NPNPNP.NPNP.NPNP.NPNPNP.nNP.MPNPMP.mq1MPm.q2MPmq.7NPn.过程TheShift-reduceTableandtheparsingprocessstatus

6、mqn$NPMP0s1s7431s22r4r4r4r43s1s7534s1s7acc635s1r2r2s7r2r2636s1r1r1s7r1r1637r3r3r3r3StackInputQueueBackupStatus$0mqnn$$0m1qnn$$0m1q2nn$$0MP3nn$$0MP3n7n$$0MP3NP5n$$0MP3NP5n7$($0NP4)(n$)$0MP3NP5NP6$($0NP4)(n$)$0MP3NP5$($0NP4)(n$)$0NP4$($0NP4)(n$)$0acc$($0NP4)(n

7、$)$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）自底向上

8、复杂度为指数思考：有没有办法变成多项式？（GLR）CYK组成部分一张二维表，存储中间结果从小的成分，逐渐计算到大的成分前提条件文法符合chomsky范式文法只有两种形式：ABC其中，A,B,C都为非终结符Aa其中，a为终结符算法数据结构一个二维矩阵：{M(i,j)}每一个元素M(i,j)对应于输入句子中某一个跨度（Span）上所有可能形成的短语的非终结符的集合横坐标i：该跨度左侧第