自然語(yǔ)言理解句法分析算法課件

1、句法分析算法上海交通大學(xué)陳玉泉第1頁(yè)，共49頁(yè)。內(nèi)容提要概述帶回溯的LR 分析法CYKEarley Chart Parsing第2頁(yè)，共49頁(yè)。概述第3頁(yè)，共49頁(yè)。程序設(shè)計(jì)語(yǔ)言分析算法遞歸下降LLLR第4頁(yè)，共49頁(yè)。特點(diǎn)高效排歧策略簡(jiǎn)單First集Follow集算符優(yōu)先級(jí)第5頁(yè)，共49頁(yè)。自然語(yǔ)言文法的特點(diǎn)歧義歧義最大數(shù)量：真歧義和偽歧義咬死獵人的狗（v n 的 n）建設(shè)公路的需要 （v n 的 n）他和我的爸爸（r 和 r 的 n）他和他的爸爸（r 和 r 的 n）第6頁(yè)，共49頁(yè)。算法應(yīng)該容納歧義允許二義文法任何可能結(jié)果都應(yīng)計(jì)算到高效在多項(xiàng)式時(shí)間內(nèi)得到結(jié)果具備排序機(jī)制，啟發(fā)式搜索策略第

2、7頁(yè)，共49頁(yè)。一些算法自頂向下自底向上帶回溯的LR 分析法CYKEarley Chart Parsing第8頁(yè)，共49頁(yè)。使用的例子輸入：一/m 張/q 火車/n 票/n文法：NP NP NP(1)NP MP NP(2)NP n(3)MP m q(4)第9頁(yè)，共49頁(yè)。期望分析結(jié)果第10頁(yè)，共49頁(yè)。Top-down自頂向下的方法又稱為基于預(yù)測(cè)的方法。這種方法是先產(chǎn)生對(duì)后面將要出現(xiàn)的成分的預(yù)期，然后再通過(guò)逐步吃進(jìn)待分析的字符串來(lái)驗(yàn)證預(yù)期。如果預(yù)期得到了證明，就說(shuō)明待分析的字符串可以被分析為所預(yù)期的句法結(jié)構(gòu)。如果某一個(gè)環(huán)節(jié)上預(yù)期出了差錯(cuò)，那就要用另外的預(yù)期來(lái)替換（即回溯）。如果所有環(huán)節(jié)上所有可

3、能的預(yù)期都被吃進(jìn)的待分析字符串所“反駁”，那就說(shuō)明待分析的字符串不可能是一個(gè)合法的句子，分析失敗。第11頁(yè)，共49頁(yè)。Top-downNP MPNPNP MP NP(2)第12頁(yè)，共49頁(yè)。Top-downNPNPNPNP MP NP(s)MP m q(4)mq一張第13頁(yè)，共49頁(yè)。Top-downNPNPNPNP MP NP(s)MP m q(4)mq一張NPNPNP NP NP(1)第14頁(yè)，共49頁(yè)。Top-downNPNPNPNP MP NP(s)MP m q(4)mq一張NPNPNP NP NP(1)nn火車票第15頁(yè)，共49頁(yè)。Bottom-up自底向上的方法也叫基于歸約的方法。

4、這種方法是先逐步吃進(jìn)待分析字符串，把它們從局部到整體層層歸約為可能的成分。如果整個(gè)待分析字符串被歸約為開(kāi)始符號(hào)S，那么分析成功。如果在某個(gè)局部證明不可能有任何從這里把整個(gè)待分析字符串歸約為句子的方案，那么就需要回溯。如果經(jīng)過(guò)回溯始終無(wú)法將待分析字符串歸約為S，那么分析失敗。第16頁(yè)，共49頁(yè)。Bottom-up一張火車票mqnn第17頁(yè)，共49頁(yè)。Bottom-up一張火車票mqnnMP第18頁(yè)，共49頁(yè)。Bottom-up一張火車票mqnnMPNP第19頁(yè)，共49頁(yè)。Bottom-up一張火車票mqnnMPNPNP第20頁(yè)，共49頁(yè)。Bottom-up一張火車票mqnnMPNPNPNP第21

5、頁(yè)，共49頁(yè)。Bottom-up一張火車票mqnnMPNPNPNPNP第22頁(yè)，共49頁(yè)。帶回溯的LR第23頁(yè)，共49頁(yè)。組成部分Shift-Reduce-Goto 表分析棧輸入隊(duì)列引入備份狀態(tài)，解決移進(jìn)規(guī)約沖突第24頁(yè)，共49頁(yè)。LR 分析表的構(gòu)造0S .NPNP .NP NPNP .nNP .MP NPMP .m q4S NP.NP NP. NPNP .NP NPNP .nNP .MP NPMP .m q3NP MP. NPNP .NP NPNP .nNP .MP NPMP .m q5NP MP NP.NP NP. NPNP .NP NPNP .nNP .MP NPMP .m q6NP N

6、P NP.NP NP. NPNP .NP NPNP .nNP .MP NPMP .m q1MP m. q2MP m q.7NP n.第25頁(yè)，共49頁(yè)。過(guò)程The Shift-reduce Table and the parsing processstatusmqn$NPMP0s1s7431s22r4r4r4r43s1s7534s1s7acc635s1 r2r2s7 r2r2636s1 r1r1s7 r1r1637r3r3r3r3StackInput QueueBackup Status$ 0 m q n n $ 0 m 1q n n $ 0 m 1 q 2n n $ 0 MP 3n n $

7、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) NP n(4) MP m q第26頁(yè)

8、，共49頁(yè)。過(guò)程（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 5n $ 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頁(yè)，共49頁(yè)。算法分析類似深度優(yōu)先搜索如果改變備份棧順序，可以實(shí)現(xiàn)其它搜索策略。（agenda）自底向上復(fù)雜度為指數(shù)思考：有沒(méi)有辦法變成多項(xiàng)式？（GLR）第28頁(yè)，共49頁(yè)。

9、CYK第29頁(yè)，共49頁(yè)。組成部分一張二維表，存儲(chǔ)中間結(jié)果從小的成分，逐漸計(jì)算到大的成分第30頁(yè)，共49頁(yè)。前提條件文法符合chomsky范式文法只有兩種形式：A B C 其中，A,B,C都為非終結(jié)符A a 其中，a為終結(jié)符第31頁(yè)，共49頁(yè)。算法數(shù)據(jù)結(jié)構(gòu)一個(gè)二維矩陣： M(i , j) 每一個(gè)元素M(i , j)對(duì)應(yīng)于輸入句子中某一個(gè)跨度（Span）上所有可能形成的短語(yǔ)的非終結(jié)符的集合橫坐標(biāo)i：該跨度左側(cè)第一個(gè)詞的位置縱坐標(biāo)j：該跨度包含的詞數(shù)第32頁(yè)，共49頁(yè)。算法描述初始化For int i = 0 to n-1if W(i,i+1) = a & exit AaAdd A to M(i,

10、i+1)計(jì)算For 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)結(jié)果M(0, n) is the set of all results;第33頁(yè)，共49頁(yè)。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頁(yè)，共49頁(yè)。算法分析文法必須二元化廣度優(yōu)先

11、搜索自底向上O(n3)，動(dòng)態(tài)規(guī)劃思想第35頁(yè)，共49頁(yè)。Earley 算法第36頁(yè)，共49頁(yè)。描述規(guī)則中加入“.”表示當(dāng)前分析程度一張二維表引入預(yù)測(cè)機(jī)制這個(gè)算法可以認(rèn)為是三個(gè)步驟的不斷循環(huán)：預(yù)測(cè)（predict）掃描（scan）完成（complete）第37頁(yè)，共49頁(yè)。基本概念一個(gè)狀態(tài)由四部分組成：上下文無(wú)關(guān)文法規(guī)則圓點(diǎn) （圓點(diǎn)左邊的部分是已分析的，右邊是待分析的）整數(shù)i : 狀態(tài)起點(diǎn)（已分析子串的起點(diǎn)）整數(shù)j : 狀態(tài)終點(diǎn)（已分析子串的終點(diǎn)） i j比如： 第38頁(yè)，共49頁(yè)?；静僮黝A(yù)測(cè)（Predicator）：如果圓點(diǎn)右方是一個(gè)非終結(jié)符，那么以該非終結(jié)符為左部的規(guī)則都有匹配的希望，也就

12、是說(shuō)分析器可以預(yù)測(cè)這些規(guī)則都可以建立相應(yīng)的項(xiàng)目。掃描（Scanner）：如果圓點(diǎn)右方是一個(gè)終結(jié)符，就將圓點(diǎn)向右方掃描一個(gè)字符間隔，把匹配完的字符“讓”到左方。歸約（Completer）：如果圓點(diǎn)右方?jīng)]有符號(hào)（即圓點(diǎn)已經(jīng)在狀態(tài)的結(jié)束位置），那么表示當(dāng)前狀態(tài)所做的預(yù)測(cè)已經(jīng)實(shí)現(xiàn)，因而可以將當(dāng)前狀態(tài)（Si）與已有的包含當(dāng)前狀態(tài)的狀態(tài)(Sj)進(jìn)行歸約（合并），從而擴(kuò)大Sj覆蓋的子串范圍第39頁(yè)，共49頁(yè)。Earley Example 一 張 火車 票5) m7) q14) n23) n1) NP 。NP NP2) NP 。MP NP3) NP 。n4) MP 。m q6) =4+5 MP m。q8)=6

13、+7 MP 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頁(yè)，共49頁(yè)

14、。分析自頂向下和自底向上的結(jié)合，以自頂向下為主引入了預(yù)測(cè)機(jī)制，在一般情況下改進(jìn)了效率最壞情況下復(fù)雜度為O(n3)第41頁(yè)，共49頁(yè)。圖算法第42頁(yè)，共49頁(yè)。基本數(shù)據(jù)結(jié)構(gòu)圖（二維表）節(jié)點(diǎn)：詞與詞之間的間隙?。寒a(chǎn)生式在兩個(gè)節(jié)點(diǎn)間的應(yīng)用，分為活動(dòng)弧和完成弧mqMP .m q.MP .m.q012第43頁(yè)，共49頁(yè)?；緮?shù)據(jù)結(jié)構(gòu)（cont.）Agenda: 可以按某種順序排列的隊(duì)列（stack, queue,），存放還沒(méi)有處理過(guò)的弧。弧的處理（舊弧產(chǎn)生新?。簲U(kuò)展：活動(dòng)弧+完成弧觸發(fā)：完成弧mqMP .m q.MP .m.q第44頁(yè)，共49頁(yè)。算法描述1。將所有單詞作為完成弧放入agenda，按某種

15、排序策略排序，把結(jié)果表清空。2。如果agenda為空，轉(zhuǎn)入63。從agenda中取出一條弧，如果是覆蓋整個(gè)句子完成弧且規(guī)則右部是可接受文法符號(hào)，那么將弧放入結(jié)果表4。如果不是，則進(jìn)行弧的擴(kuò)展與觸發(fā)，將產(chǎn)生的新弧放入agenda，放入時(shí)滿足agenda的排序規(guī)則5。轉(zhuǎn)入26。如果結(jié)果表空，則分析失敗，否則返回結(jié)果表中的內(nèi)容第45頁(yè)，共49頁(yè)。最左觸發(fā)，向右擴(kuò)展，后進(jìn)先出的圖算法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.01423Gramma

16、r: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(