第3章 語法與語法剖析

第三章語法與語法剖析廈門大學(xué)計算機(jī)科學(xué)系

李堂秋第一節(jié)語法與句子結(jié)構(gòu)表示句子結(jié)構(gòu)的最常用的表示法是語法樹：Joneatethecat.表結(jié)構(gòu)表示：

(S(NP(NAMEJone))

(VP(Vate)

(NP(ARTthe)

(Ncat))))簡單的上下文無關(guān)規(guī)則： SNPVPNAMEVNPJohnateARINthecat相關(guān)術(shù)語：樹結(jié)點(diǎn)鏈接根葉子

父親子女祖先后代

1S-->NPVP5NAME-->John2VP-->VNP6V-->ate3NP-->NAME7ART-->the4NP-->ARTN8N-->cat相關(guān)術(shù)語：上下文無關(guān)文法重寫規(guī)則非終結(jié)符起始符詞類符號終結(jié)符可以用語法推導(dǎo)出合法的句子（所以又叫做生成語法）：有兩個過程是基于推導(dǎo)的：生成與剖析S

==>NPVP （重寫S）

==>NAMEVP （重寫NP)

==>JohnVP （重寫NAME）

==>JohnVNP （重寫VP）

==>JohnateNP （重寫V）

==>JohnateARTN （重寫NP）

==>JohnatetheN （重寫ART）

==>Johnatethecat （重寫N）==>NAMEatethecat （重寫John）==>NAMEVthecat （重寫ate）

==>NAMEVARTcat （重寫the）

==>NAMEVARTN （重寫cat）

==>NPVARTN （重寫NAME）

==>NPVNP （重寫ARTN）==>NPVP （重寫VNP)

==>S （重寫NPVP）

相關(guān)概念：

自頂向下的語法剖析自底向上的語法剖析

語法樹：可以通過把語法剖析

過程記錄起來形成第二節(jié)什么是好的語法好語法應(yīng)具有如下的性質(zhì)：普遍性選擇性易理解性判斷文法的正確性，有幾種方法：如果決定有一類詞可以形成句子的某一成分，試試看這類成分的并列詞組是否可以做同樣的成分，如果不行可能就有問題。NP-NP Iateahamburgerandahotdog.VP-VP Iwilleatthehamburgerandthrowawaythehotdog.S-S IateahambergerandJohnateahotdog.ADJP-ADJP Iateacoldandwellburnedhotdog.ADVP-ADVP Iatethehotdogslowlyandverycarefully.N-N IateahamburgerandhotdogV-V Iwillcookandburnahamburger.AUX-AUX Icanandwilleatthehotdog.ADJ-ADJ Iatetheverycoldandburnedhotdog.如果認(rèn)為某一類詞可以做句子的某一類成分，看一看是否可以出現(xiàn)在句子需要同一類成分的其它地方：當(dāng)提出一條規(guī)則的時候，要考慮它對其它規(guī)則的相互影響。John’shitingofMaryalarmedSue.

IcannotexplainJohn’shittingofMary.

SuewasalarmedbyJohn’shittingofMary.確實可以當(dāng)NPIlookupJohn’sphonenumber.Up..是否是PP？

IlookupJohn’schimney.

*IlookupJohn’sphonenumberandinhiscupboards.可見不都是

IlookupJohn’schimneyandinhiscupboards.第三節(jié)自上而下的語法剖析語法分析是一種AI中搜索過程，下面判斷句子是否被語法所接受為例下面是使用一個簡單的自頂向下的語法剖析算法分析結(jié)果：算法：從初始狀態(tài)((s)1)開始，重復(fù)以下過程：1。選擇當(dāng)前狀態(tài)：從可能狀態(tài)表中取出第一個狀態(tài)，叫它為C。如果可能表為空，算法失?。ú豢赡艿玫秸_的剖析）2。如果C包含一個空符號，且詞的位置是處于句子的結(jié)尾，算法成功3。否則，生成下一個狀態(tài)：

3。1如果C符號表中的第一個符號是詞類符，而當(dāng)前位置上的詞可以作為這種詞類，則形成一個新的狀態(tài)，辦法是：去掉符號表中的第一個符號，并把詞的位置加一。把新狀態(tài)放入可能狀態(tài)表

3。2否則，如果當(dāng)前狀態(tài)符號表中的第一個符號是一個非終結(jié)狀態(tài)，把語法規(guī)則表中所有可以重寫這個符號的規(guī)則重寫這個符號，形成新的狀態(tài)。把形成的所有可能的狀態(tài)加入到可能狀態(tài)表中。語法：

1. S-->NPVP 4.VP-->V

2. NP-->ARTN 5.VP-->VNP

3. NP-->ARTADJN詞匯：

cried:V

dogs:NV

the:ART步數(shù)當(dāng)前狀態(tài) 回朔狀態(tài) 注解

1. ((s)1) 初始位置

2. ((NPVP)1) 用規(guī)則1重寫S

3. ((ARTNVP)1) 用規(guī)則2、3重寫NP

((ARTADJNVP)1)

4. ((NVP)2) ART與the匹配

((ARTADJNVP)1)

5. ((VP)3) N與dog匹配

((ARTADJNVP)1)

6. ((V)3) 用規(guī)則4、5重寫VP

((VNP)3)

((ARTADJNVP)1)

7. V與cried匹配，成功如果把這個例子擴(kuò)大一點(diǎn)：

句子：Theoldmancried.

詞典：the:ARTold:ADJN

man:NV

cried:V語法：

1. S-->NPVP 4.VP-->V

2. NP-->ARTN 5.VP-->VNP

3. NP-->ARTADJN詞匯：

cried:V

dogs:NV

the:ART步數(shù) 當(dāng)前狀態(tài) 回朔狀態(tài) 注解

1. ((s)1) 初始位置

2. ((NPVP)1) 用規(guī)則1重寫S成NPVP

3. ((ARTNVP)1) 用規(guī)則2、3重寫NP

((ARTADJNVP)1)

4. ((NVP)2) ART與the匹配

((ARTADJNVP)1)

5. ((VP)3) ((ARTADJNVP)1)

6. ((V)3) 用規(guī)則4、5重寫VP

((VNP)3)((ARTADJNVP)1)

7. (()4) V與man匹配，不成功

((VNP)3)((ARTADJNVP)1)

8. ((VNP)3) 第一次回朔

((ARTADJNVP)1)

9. ((NP)4)

((ARTADJNVP)1)

10. ((ARTN)4) 找ART失敗回朔

((ARTADJN)4)((ARTADJNVP)1) 11. ((ARTADJN)4)

((ARTADJNVP)1) 再一次失敗，回朔

12. ((ARTADJNVP)1)

13. ((ADJNVP)2) 14. ((NVP)3) 15. ((VP)4)

16. ((V)4)

((VNP)4)

17. (()5)句子：1The2old3man4cried5.詞典：the:ARTold:ADJN

man:NV

cried:V語法：

1.S-->NPVP2.NP-->ARTN3.NP-->ARTADJN4.VP-->V5.VP-->VNP對比一下語法分析和Ai的搜索過程：重復(fù)如下過程直到成果或失?。簭目赡軤顟B(tài)表中取出第一個狀態(tài)從這個選擇的狀態(tài)生成所有可能的后續(xù)狀態(tài)（可能一個也沒有）把生成的狀態(tài)加入到可能狀態(tài)表中如果把生成的后續(xù)狀態(tài)放在可能狀態(tài)表的前面，執(zhí)行的是深度優(yōu)先搜索。如果把生成的后續(xù)狀態(tài)放在可能狀態(tài)表的后面，執(zhí)行的是廣度優(yōu)先搜索?？梢钥闯稣Z法分析的過程就是搜索的過程。注意：對于深度優(yōu)先搜索，遇到左遞歸的規(guī)則可能引起無限循環(huán)：

NP-->NP’sN對于廣度優(yōu)先搜索，在有左遞歸規(guī)則的語法，如果句子是合法的，不會陷入無限循環(huán)，但是如果句子是不合文法時，也會引起無限循環(huán)。上述過程實際上是一個深度優(yōu)先搜索的過程：((s)1)成功！((NPVP)1)((ARTNVP)1)((ARTADJNVP)1)((NVP)2)((VP)3)((V)3)((VNP)3)(()4)((NP)4)((ARTN)4)((ARTADJN)4)((ADJNVP)2)((NVP)3)((VP)4)((V)4)((VNP)4)(()4)廣度優(yōu)先搜索的過程：((s)1)((ARTADJNVP)1)((ARTNVP)1)((NVP)2)((VP)3)((VNP)3)((V)3)(()4)((NP)4)((ARTN)4)((ARTADJN)4)((ADJNVP)2)((NVP)3)((VP)4)(()4)((V)4)((VNP)4)成功！((NPVP)1)第四節(jié)自底向上的圖剖析器自頂向下和自底向上語法分析不同的地方在于：前這使用規(guī)則在句子中找規(guī)則描述的成分后者是使用規(guī)則把句子中已經(jīng)歸結(jié)出來的成分歸結(jié)成更大的成分最簡單的自底向上的語法分析可用下述簡單步驟：把單詞重寫成它可能的詞類把與任何一條規(guī)則右部相匹配的符號序列重寫成匹配規(guī)則的坐部但是這樣的過程太低效，實際上無法使用。主要原因是在分析的過程中會對同一個成分進(jìn)行多次重復(fù)的分析，現(xiàn)在研究使用一種稱為圖的數(shù)據(jù)結(jié)構(gòu)以避免重復(fù)的工作圖剖析器的工作的原理為：有一個記事表記錄遇到的詞的類符或已經(jīng)分析完成的成分，稱它們?yōu)殛P(guān)鍵成分，取出一個關(guān)鍵成分在語法中找出右部以這個關(guān)鍵成分打頭的語法規(guī)則，將之激活或找出已經(jīng)由別的關(guān)鍵成分開始并剛好需要這個關(guān)鍵成分接續(xù)下去，以便擴(kuò)展規(guī)則的匹配。這樣一直進(jìn)行下去或一個完整的句子剖析已得到，或記事表空（失?。┫旅媸鞘褂靡粋€簡單的自上而下的語法剖析算法分析結(jié)果：算法：從((s)1)，重復(fù)以下過程：1。選擇當(dāng)前狀態(tài)：從可能狀態(tài)表中取出第一個狀態(tài)，叫它為C。如果可能表為空，算法失敗（不可能得到正確的剖析）2。如果C包含一個空符號，且詞的位置是處于句子的結(jié)尾，算法成功3。否則，生成下一個狀態(tài)：

3。1如果C符號表中的第一個符號是詞類符，而當(dāng)前位置上的詞可以作為這種詞類，則形成一個新的狀態(tài)，辦法是：去掉符號表中的第一個符號，并把詞的位置加一。把新狀態(tài)放入可能狀態(tài)表

3。2否則，如果當(dāng)前狀態(tài)符號表中的第一個符號是一個非終結(jié)狀態(tài)，把語法規(guī)則表中所有可以重寫這個符號的規(guī)則重寫這個符號，形成新的狀態(tài)。把形成的所有可能的狀態(tài)加入到可能狀態(tài)表中。例如：有如右的語法規(guī)則，并且正在分析

句子（第一個詞是ART第二個詞是ADJ…）用ART在規(guī)則集合中找出規(guī)則2、3，并將結(jié)構(gòu)記成：

NP->ART。ADJN

NP->ART。Ｎ這兩個弧成活動弧用ADJ在規(guī)則集合中找出規(guī)則４并寫成

NP->ADJ。N以激活的弧也得到擴(kuò)展：

NP->ARTADJ。N1.S->NPVP

2.NP->ARTADJN

3.NP->ARTN

4.NP->ADJN

5.VP->AUXVP6.VP->VNPARTADJNP->ART。ADJNNP->ART。ＮNP->ADJ。NNP->ARTADJ。N核心的算法有兩個，即：弧擴(kuò)展算法：為了添加一個從位置p1到p2的弧C：把這段弧C添加到圖中從p1到p2的位置對于所有有如下公式:X->X1…。Ｃ…Xn從p0到p1的弧，在p0到p2之間加上一段新的活動弧，它有公式X->X1…Ｃ?！璛n對于所有有如下公式:X->X1…。Ｃ從p0到p1的弧，把一個新的成分X(從p0到p2）加到記事表中自底向上的圖語法剖析算法：一直進(jìn)行如下過程直到?jīng)]有余下的輸入詞：如果記事表為空，看輸入中下一個詞的解釋，并把之加如記事表從記事表中選出一個成分（稱為從p1到p2的成分C）對于每一條形如X->CX1X2…Xn的規(guī)則，把一段活動弧加到圖中的p1到p2的位置，它的公式是X->C。X1X2…Xn根據(jù)弧擴(kuò)展算法把Ｃ加到圖中去。輸入句子圖記錄活動弧和分析完成的成分記事表語法規(guī)則表算法S(18)AUX(34)AUX(45）V(34)V(45)V(56)V(78)NP(14)VP(58)S(28)NP(24)VP(48)VP(38)N(45)4can5ART(12)1the2ADJ(23)2large3N(34)3can4N(56)5hold6N(78)7water8ART(67)6the7NP->ART。

ADJNNP->ART。NNP->ADJ。NNP->ARTADJ。NS->NP。VPS->NP。VPVP->AUX。VPVP->AUX。VPVP->V。NPVP->V。NPVP->V。NPNP->ART。

ADJNNP->ART。NNP(68)S->NP。VPVP->V。NP1.S->NPVP

2.NP->ARTADJN

3.NP->ARTN

4.NP->ADJN

5.VP->AUXVP6.VP->VNP

the:ART

large:ADJ

can:N,AUX,V

hold:N,V

water:N,V第五節(jié)轉(zhuǎn)移網(wǎng)絡(luò)語法轉(zhuǎn)移網(wǎng)絡(luò)是另一種表示語法的方法，它有以下兩個元素主成的：帶標(biāo)號的結(jié)點(diǎn)，其中有一個結(jié)點(diǎn)稱為起始初始或結(jié)點(diǎn)帶標(biāo)號的弧最簡單的是有限狀態(tài)機(jī)，但表達(dá)能力也有限，無法表達(dá)自然語言的語法。也一種稱為遞歸轉(zhuǎn)移網(wǎng)絡(luò)的（RTN），與上下文無關(guān)文法等價，下面是簡單的自然語言語法的網(wǎng)絡(luò)表示法：上面小寫字母串表示詞類，大寫字母串表示短語的類型，而且在實際應(yīng)用中還有不少擴(kuò)充，為了分別，加上前綴：類型 標(biāo)識 應(yīng)用CAT noun 如果當(dāng)前的詞的類型與標(biāo)識符相同，成功通過當(dāng)前弧

NPNP1NP2SS1S2S3artpopnounNPNPverbNPpopWRD of 如果當(dāng)前的詞與標(biāo)識符相同，成功通過當(dāng)前弧PUSH NP 如果從當(dāng)前的詞開始能通過標(biāo)識符指定的子網(wǎng)絡(luò) 相同，則成功通過當(dāng)前弧JUMP 不管當(dāng)前詞是什么，總能通過當(dāng)前弧POP 子網(wǎng)絡(luò)通過成功，跳回上一層網(wǎng)絡(luò)下面看如何用RTN分析句子的：

Thepurplecowatethegrass.NPNP1NP2artpopnounNPSS1S2S3NPverbNPpopSS1S2S3NPNP1NP2NPNP1NP2遞歸轉(zhuǎn)移網(wǎng)絡(luò)自頂向下的語法剖析：名稱解釋：當(dāng)前位置：指句子中當(dāng)前要分析的詞當(dāng)前結(jié)點(diǎn)：當(dāng)前在網(wǎng)絡(luò)中所處的結(jié)點(diǎn)位置返回點(diǎn)：如果從一個子網(wǎng)絡(luò)中跳出，返回到哪個子網(wǎng)絡(luò)的什么地方下一個狀態(tài)：通過弧算法：如果是CAT符，并且當(dāng)前位置的詞類與標(biāo)識符相同

則把當(dāng)前位置加一，把當(dāng)前結(jié)點(diǎn)換成弧所指的結(jié)點(diǎn)如果是PUSHＮ弧，把當(dāng)前弧所指的結(jié)點(diǎn)設(shè)定加入到返回點(diǎn)表，把當(dāng)前結(jié)點(diǎn)設(shè)為子網(wǎng)絡(luò)Ｎ的首結(jié)點(diǎn)如果是POP弧，并且返回表非空，則彈出返回表中的第一個點(diǎn)，做為當(dāng)前結(jié)點(diǎn)如果是POP弧，返回表為空且所有的詞都分析完畢，則語法剖析成功下面是另一個語法的網(wǎng)絡(luò)：分析：Theoldmancried.NPNP1NP2SS1S2PUSHNPCARverbPUSHNPPOPCATpronounCATartCATnumberCATadjPOPCATnoun3121211112步驟 當(dāng)前結(jié)點(diǎn)當(dāng)前位置返回點(diǎn) 要走的弧 注釋1. S 1 NIL S/1 初始位置2. NP 1 (S1) NP/1 轉(zhuǎn)到NP3. NP1 2 (S1) NP1/1 the4. NP1 3 (S1) NP1/2 old5. NP2 4 (S1) NP2/2 man6. S1 4 NIL S1/1 返回S17. S2 5 NIL S2/1 cried8. 成功

分析：Onesawtheman.NPNP1NP2SS1S2PUSHNPCARverbPUSHNPPOPCATpronounCATartCATnumberCATadjPOPCATnoun3121211112步驟 當(dāng)前狀態(tài) 要走的弧 回朔狀態(tài)1. (S1NIL) S/1 2. (NP1(S1)) NP/2(NP3回朔用）

3. (NP12(S1)) NP1/2 (NP22(S1))4. (NP13(S1) NP2/1 (NP22(S1))5. (S13NIL) NO (NP22(S1)) 6. (NP22(S1)) NP2/1 7. (S12NIL) S1/1 8. (S23NIL) S2/2 9. (NP3(S2)) NP/110. (NP14(S2)) NP1/211. (NP25(S2)) NP2/112. (S25NIL) S2/113. 成功

RTN可以用圖一樣的數(shù)據(jù)結(jié)構(gòu)提高

分析的效率--合法子結(jié)構(gòu)表，其分

析效率與圖語法剖析一樣：K*N3第六節(jié)自頂向下圖剖析自頂向下和自底向上語法分析各有優(yōu)缺點(diǎn)：自頂向下的語法分析有高度的預(yù)見性，這有助于排除一些歧義，使得沒有得到預(yù)見的結(jié)構(gòu)不會生成。如：Thecanholdsthewater.中can有三種可能AUX、V、N。但是自頂向下語法分析中：S->NPVP,->ARTADJNVP,或ARTNVP,ADJNVP.先用第一個，the是ART，看can是否可以是ADJ時，失敗用第二時，再次檢查ART，然后看can是否可能是N時成功，此后AUX、V不再考慮而自底向上語法分析中三種可能全會考慮。從這種意義上說自頂向下分析法更高效相反，自頂向下的語法分析對the是否是ART要多次判斷，對與復(fù)雜的語法，反復(fù)生成復(fù)雜的中間結(jié)構(gòu)會造成低效的嚴(yán)重效果。而在自底向上語法分析中同一個機(jī)構(gòu)可保證只生成一次。這樣自底向上的看來效率更高。通過把兩種方法結(jié)合起來，可以綜合兩者的優(yōu)點(diǎn)--形成自上而下制導(dǎo)的自底向上的分析方法。這種方法與純自底向上的比較如下：弧擴(kuò)展算法一樣不同的是這種方法引入自上而下的弧引入算法。不是引入所有以生成的成分為第一個元素的所有產(chǎn)生式。算法：自上而下的弧引入算法：要加入一條在位置j結(jié)尾的弧S->C1C2..。Ci…Cn，執(zhí)行：對于語法中的每一條形如Ci->X1X2…Xk，遞歸地在從j到j(luò)的位置上加入形如

Ci->。X1X2…Xk的弧。自上而下的圖剖析算法：初始化：對于語法中所有形如S->X1X2…Xk，應(yīng)用弧引如算法往圖中加入標(biāo)

為S->。X1X2…Xn.分析算法：如果記事表為空，看輸入中下一個詞的解釋，并把之加入記事表從記事表中選出一個成分（稱為從p1到p2的成分C）根據(jù)弧擴(kuò)展算法把Ｃ加到圖中去，并與可能擴(kuò)展的活動弧相結(jié)合。生成的

所有新成分要加到記事表中去。對于在步驟３中生成的每一條形活動弧，使用上述弧引入算法把它們加到

圖中去。S(18)AUX(45）V(45)NP(14)VP(58)VP(48)ART(12)1the2ADJ(23)2large3N