研究生院第四章_2_

1、1第四章第四章 語(yǔ)法分析語(yǔ)法分析分析器的作用分析器的作用上下文無(wú)關(guān)文法的分析上下文無(wú)關(guān)文法的分析自上而下的分析自上而下的分析自底向上的分析自底向上的分析LR分析器分析器二義文法的應(yīng)用二義文法的應(yīng)用Yacc介紹介紹2自底向上的分析（自底向上的分析（1）什么是自底向上的分析什么是自底向上的分析使用了顯式棧來(lái)完成分析，棧中包括終結(jié)符號(hào)和非終結(jié)符使用了顯式棧來(lái)完成分析，棧中包括終結(jié)符號(hào)和非終結(jié)符號(hào)，以及其他的一些信息等號(hào)，以及其他的一些信息等$InputString$StartSymbol $接受接受分析器根據(jù)當(dāng)前棧中的符號(hào)以及向前看的分析來(lái)決定分析分析器根據(jù)當(dāng)前棧中的符號(hào)以及向前看的分析來(lái)決定分析器

2、的動(dòng)作：器的動(dòng)作：接受接受移進(jìn)移進(jìn)歸約歸約報(bào)錯(cuò)報(bào)錯(cuò)要對(duì)文法進(jìn)行擴(kuò)展要對(duì)文法進(jìn)行擴(kuò)展也稱為移進(jìn)也稱為移進(jìn)-歸約分析，包括算符優(yōu)先分析、歸約分析，包括算符優(yōu)先分析、LR分析分析3自底向上的分析（自底向上的分析（2）自底向上的分析與預(yù)測(cè)分析器的比較自底向上的分析與預(yù)測(cè)分析器的比較一般而言，自底向上的分析功能更強(qiáng)大一般而言，自底向上的分析功能更強(qiáng)大如：預(yù)測(cè)分析器不能處理左遞歸等，而自底向上的分析則不如：預(yù)測(cè)分析器不能處理左遞歸等，而自底向上的分析則不成問(wèn)題成問(wèn)題對(duì)棧和向前看的符號(hào)的使用上：對(duì)棧和向前看的符號(hào)的使用上：可以將輸入符號(hào)移進(jìn)棧，直至它判斷出要執(zhí)行的動(dòng)作為止可以將輸入符號(hào)移進(jìn)棧，直至它判斷出要

3、執(zhí)行的動(dòng)作為止進(jìn)行動(dòng)作判斷時(shí)可以使用棧中所有的符號(hào)進(jìn)行動(dòng)作判斷時(shí)可以使用棧中所有的符號(hào)開(kāi)始時(shí)棧為空，而接受時(shí)棧中為文法的開(kāi)始符號(hào)開(kāi)始時(shí)棧為空，而接受時(shí)棧中為文法的開(kāi)始符號(hào)預(yù)測(cè)分析器描述的是從文法開(kāi)始符號(hào)推導(dǎo)得到句子的過(guò)程預(yù)測(cè)分析器描述的是從文法開(kāi)始符號(hào)推導(dǎo)得到句子的過(guò)程,是一個(gè)匹配的過(guò)程，而自底向上的分析描述的推導(dǎo)過(guò)程的是一個(gè)匹配的過(guò)程，而自底向上的分析描述的推導(dǎo)過(guò)程的逆過(guò)程，是一個(gè)歸約的過(guò)程逆過(guò)程，是一個(gè)歸約的過(guò)程錯(cuò)誤恢復(fù)：自底向上的分析所使用的特定算法的能力會(huì)影錯(cuò)誤恢復(fù)：自底向上的分析所使用的特定算法的能力會(huì)影響到分析程序是否可早些檢測(cè)出錯(cuò)誤的能力，規(guī)范的響到分析程序是否可早些檢測(cè)出錯(cuò)誤的

4、能力，規(guī)范的LR分分析甚至在報(bào)告錯(cuò)誤之前不做任何無(wú)效的歸約析甚至在報(bào)告錯(cuò)誤之前不做任何無(wú)效的歸約自底向上的分析器較為復(fù)雜自底向上的分析器較為復(fù)雜4自底向上的分析（自底向上的分析（3）自底向上分析舉例自底向上分析舉例為輸入串構(gòu)造分析樹(shù)是葉節(jié)點(diǎn)開(kāi)始的，直至逆序?yàn)檩斎氪畼?gòu)造分析樹(shù)是葉節(jié)點(diǎn)開(kāi)始的，直至逆序得到根節(jié)點(diǎn)得到根節(jié)點(diǎn)文法：文法：SaABeAAbc | bBd句子句子abbcde的歸約過(guò)程：的歸約過(guò)程：abbcdeaAbcdeaAdeaABeS對(duì)應(yīng)的最右推導(dǎo)：對(duì)應(yīng)的最右推導(dǎo)：abbcdeaAbcdeaAdeaABeSrmrmrmrm5自底向上的分析（自底向上的分析（4）A Ab ba ab bc

5、 cd de eA AB BS SabbcdeaAbcdeaAdeaABeSrmrmrmrm6自底向上的分析（自底向上的分析（5）句柄句柄定義：定義：右句型右句型(最右推導(dǎo)可得到的句型最右推導(dǎo)可得到的句型)的的句柄句柄是一個(gè)產(chǎn)生式是一個(gè)產(chǎn)生式A以及以及中的一個(gè)位置，在這個(gè)位置可找到串中的一個(gè)位置，在這個(gè)位置可找到串，用用A代代替替得到最右推導(dǎo)的前一個(gè)右句型。即如果有如下的最右得到最右推導(dǎo)的前一個(gè)右句型。即如果有如下的最右推導(dǎo)序列推導(dǎo)序列則在則在后的后的A是是的句柄。的句柄。非形式的說(shuō)法：非形式的說(shuō)法：一個(gè)串的句柄是和一個(gè)產(chǎn)生式右部匹配的子串，并且，把一個(gè)串的句柄是和一個(gè)產(chǎn)生式右部匹配的子串，并

6、且，把它歸約成該產(chǎn)生式左部的非終結(jié)符代表了最右推導(dǎo)逆過(guò)程它歸約成該產(chǎn)生式左部的非終結(jié)符代表了最右推導(dǎo)逆過(guò)程的一步的一步唯一性：唯一性：文法無(wú)二義時(shí)，句柄是唯一的；否則，句柄不一定唯一文法無(wú)二義時(shí)，句柄是唯一的；否則，句柄不一定唯一ASrm*rm7自底向上的分析（自底向上的分析（6）上例中的句柄上例中的句柄Ab是右句型是右句型abbcde的句柄，它的位置？的句柄，它的位置？AAbc是右句型是右句型aAbcde的句柄，它的位置？的句柄，它的位置？簡(jiǎn)稱：簡(jiǎn)稱：如果清楚地知道句柄的位置和應(yīng)用的產(chǎn)生式的話，可以直如果清楚地知道句柄的位置和應(yīng)用的產(chǎn)生式的話，可以直接說(shuō)子串接說(shuō)子串是是的句柄的句柄作用：作用

7、：移進(jìn)移進(jìn)-歸約分析器將終結(jié)符號(hào)從輸入移進(jìn)到棧中，直到歸約分析器將終結(jié)符號(hào)從輸入移進(jìn)到棧中，直到它能執(zhí)行一個(gè)歸約得到下一個(gè)右句型它能執(zhí)行一個(gè)歸約得到下一個(gè)右句型判斷分析中的下一個(gè)句柄是移進(jìn)判斷分析中的下一個(gè)句柄是移進(jìn)-歸約分析器的主要任歸約分析器的主要任務(wù)務(wù)句柄總是為它的產(chǎn)生式構(gòu)成一個(gè)完整的右部，而這個(gè)句柄總是為它的產(chǎn)生式構(gòu)成一個(gè)完整的右部，而這個(gè)產(chǎn)生式是下一步歸約中應(yīng)用的產(chǎn)生式，而且歸約發(fā)生產(chǎn)生式是下一步歸約中應(yīng)用的產(chǎn)生式，而且歸約發(fā)生時(shí)，句柄的最右邊的位置與棧的頂部對(duì)應(yīng)時(shí)，句柄的最右邊的位置與棧的頂部對(duì)應(yīng)8自底向上的分析（自底向上的分析（7）句柄代表了最左邊的由一個(gè)內(nèi)部節(jié)點(diǎn)和它所有的下一代

8、組句柄代表了最左邊的由一個(gè)內(nèi)部節(jié)點(diǎn)和它所有的下一代組成的子樹(shù)成的子樹(shù)句柄的右邊符號(hào)串只含有終結(jié)符號(hào)句柄的右邊符號(hào)串只含有終結(jié)符號(hào)活前綴：一個(gè)規(guī)范句型的一個(gè)前綴，如果不含句柄后的任活前綴：一個(gè)規(guī)范句型的一個(gè)前綴，如果不含句柄后的任何符號(hào)，則稱它為該規(guī)范句型的一個(gè)活前綴何符號(hào)，則稱它為該規(guī)范句型的一個(gè)活前綴活前綴不超過(guò)最右句柄的右端，因此在活前綴的右端加上一活前綴不超過(guò)最右句柄的右端，因此在活前綴的右端加上一些終結(jié)符后可以使它成為右句型些終結(jié)符后可以使它成為右句型只要輸入串的已掃描部分可以歸約成一個(gè)活前綴，意味著所只要輸入串的已掃描部分可以歸約成一個(gè)活前綴，意味著所掃描的部分沒(méi)有錯(cuò)誤掃描的部分沒(méi)有

9、錯(cuò)誤S SA A9自底向上的分析（自底向上的分析（8）例例1：考慮表達(dá)式文法：考慮表達(dá)式文法 EE+E | E*E | （E）| id對(duì)于最右推導(dǎo)：對(duì)于最右推導(dǎo)：但這個(gè)文法是有二義性的，因此存在另一個(gè)最右推導(dǎo)但這個(gè)文法是有二義性的，因此存在另一個(gè)最右推導(dǎo)321*rm32*rm3*rm*rm*rmid*idid id*idE id*EE E*EE EEE10自底向上的分析（自底向上的分析（9）移進(jìn)移進(jìn)-歸約分析的實(shí)現(xiàn)歸約分析的實(shí)現(xiàn)用棧來(lái)保存文法符號(hào)，輸入緩沖區(qū)來(lái)保存待分析用棧來(lái)保存文法符號(hào)，輸入緩沖區(qū)來(lái)保存待分析的串的串句柄的選擇：句柄的選擇：如何決定右句型中要?dú)w約的子串如何決定右句型中要?dú)w約的

10、子串當(dāng)一個(gè)要?dú)w約的子串是多個(gè)產(chǎn)生式的右部時(shí)，如當(dāng)一個(gè)要?dú)w約的子串是多個(gè)產(chǎn)生式的右部時(shí)，如何確定選擇哪個(gè)產(chǎn)生式何確定選擇哪個(gè)產(chǎn)生式動(dòng)作動(dòng)作（1）移進(jìn)：將下一個(gè)輸入符號(hào)移進(jìn)棧頂）移進(jìn)：將下一個(gè)輸入符號(hào)移進(jìn)棧頂（2）歸約：句柄位于棧頂，必須在棧中確定完整的句柄，）歸約：句柄位于棧頂，必須在棧中確定完整的句柄，并決定用哪個(gè)產(chǎn)生式歸約并決定用哪個(gè)產(chǎn)生式歸約（3）接受：分析成功）接受：分析成功（4）出錯(cuò)：報(bào)告錯(cuò)誤，調(diào)用錯(cuò)誤恢復(fù)例程）出錯(cuò)：報(bào)告錯(cuò)誤，調(diào)用錯(cuò)誤恢復(fù)例程11自底向上的分析（自底向上的分析（10）棧棧輸輸 入入動(dòng)動(dòng) 作作 (1) $ id1+id2*id3$ 移進(jìn)移進(jìn) (2) $id1 +id2*

11、id3$ 按按Eid歸約歸約 (3) $E +id2*id3$ 移進(jìn)移進(jìn) (4) $E+ id2*id3$ 移進(jìn)移進(jìn) (5) $E+id2 *id3$ 按按Eid歸約歸約 (6) $E+E *id3$ 移進(jìn)移進(jìn) (7) $E+E* id3$ 移進(jìn)移進(jìn) (8) $E+E*id3 $ 按按Eid歸約歸約 (9) $E+E*E $ 按按EE*E歸約歸約 (10)$E+E $ 按按EE+E歸約歸約 (11)$E $ 接受接受12自底向上的分析（自底向上的分析（11）移進(jìn)移進(jìn)-歸約分析的沖突歸約分析的沖突移進(jìn)移進(jìn)-歸約沖突歸約沖突根據(jù)棧中所有的內(nèi)容和下一個(gè)輸入符號(hào)不能決定是移進(jìn)還是根據(jù)棧中所有的內(nèi)容和下

12、一個(gè)輸入符號(hào)不能決定是移進(jìn)還是歸約歸約歸約歸約-歸約沖突歸約沖突根據(jù)棧中所有的內(nèi)容和下一個(gè)輸入符號(hào)不能決定使用哪一個(gè)根據(jù)棧中所有的內(nèi)容和下一個(gè)輸入符號(hào)不能決定使用哪一個(gè)產(chǎn)生式歸約產(chǎn)生式歸約移進(jìn)移進(jìn)-歸約分析的沖突的解決歸約分析的沖突的解決利用移進(jìn)優(yōu)先的約定可以解決一些二義性文法引起的沖突利用移進(jìn)優(yōu)先的約定可以解決一些二義性文法引起的沖突（如（如if then else ）對(duì)于有些情況要借助其它信息解決，如對(duì)于有些情況要借助其它信息解決，如FORTRAN語(yǔ)言中語(yǔ)言中數(shù)組引用和過(guò)程調(diào)用：數(shù)組引用和過(guò)程調(diào)用：A( i , j , k )，i、j、k是數(shù)組的下標(biāo)表達(dá)式還是參數(shù)？是數(shù)組的下標(biāo)表達(dá)式還是參

13、數(shù)？13LR分析器分析器（1）LR分析算法分析算法LR文法文法LR(0)分析分析SLR(1)分析分析LR(1)規(guī)范分析規(guī)范分析LALR(1)分析分析14LR分析器分析器（2）LR(k)分析分析L指從左到右掃描輸入，指從左到右掃描輸入，R指構(gòu)造最右推導(dǎo)的逆，指構(gòu)造最右推導(dǎo)的逆，k指的是指的是在決定分析動(dòng)作時(shí)向前看的符號(hào)個(gè)數(shù)，在決定分析動(dòng)作時(shí)向前看的符號(hào)個(gè)數(shù)，(k)省略時(shí)，表示省略時(shí)，表示k是是1LR(k)分析能力強(qiáng)大分析能力強(qiáng)大LR分析器能夠構(gòu)造識(shí)別所有上下文無(wú)關(guān)文法寫(xiě)的程序設(shè)計(jì)語(yǔ)分析器能夠構(gòu)造識(shí)別所有上下文無(wú)關(guān)文法寫(xiě)的程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu)言的結(jié)構(gòu)LR分析方法是已知的最一般的無(wú)回溯移進(jìn)分析方法是已

14、知的最一般的無(wú)回溯移進(jìn)-歸約方法，它能歸約方法，它能夠和其他移進(jìn)夠和其他移進(jìn)-歸約方法一樣有效地實(shí)現(xiàn)歸約方法一樣有效地實(shí)現(xiàn)LR方法能分析的文法類是預(yù)測(cè)分析法能分析的文法類的真超方法能分析的文法類是預(yù)測(cè)分析法能分析的文法類的真超集集LR分析器能及時(shí)察覺(jué)語(yǔ)法錯(cuò)誤，快到自左向右掃描輸入的最分析器能及時(shí)察覺(jué)語(yǔ)法錯(cuò)誤，快到自左向右掃描輸入的最大可能大可能手工構(gòu)造手工構(gòu)造LR分析器的工作量太大，但可以利用專門(mén)的工分析器的工作量太大，但可以利用專門(mén)的工具（如具（如Yacc）來(lái)構(gòu)造來(lái)構(gòu)造如果文法二義或有其它難以自左向右分析的結(jié)構(gòu)，分析器的如果文法二義或有其它難以自左向右分析的結(jié)構(gòu)，分析器的生成器能定位這些結(jié)構(gòu)

15、并報(bào)告生成器能定位這些結(jié)構(gòu)并報(bào)告15LR分析器分析器（3）LR分析算法分析算法組成組成驅(qū)動(dòng)程序?qū)λ械尿?qū)動(dòng)程序?qū)λ械腖R分析器是一樣的，只是分析表不同分析器是一樣的，只是分析表不同棧中存儲(chǔ)形如棧中存儲(chǔ)形如s0X1s1X2s2Xmsm的串，其中的串，其中sm在棧頂，在棧頂，Xi是是文法符號(hào)，文法符號(hào)，si是是狀態(tài)狀態(tài)符號(hào)，它概括了棧中它下面部分所包符號(hào)，它概括了棧中它下面部分所包含的信息含的信息輸輸入入棧棧L LR R分分析析程程序序輸輸出出a ac ct ti io on nL LR R分分析析器器模模型型a a1 1. . . .a ai i. . . .a an n$ $s sm mX

16、Xm ms sm m- -1 1X Xm m- -1 1. . . .s s0 0g go ot to o16LR分析器分析器（4）分析表包括動(dòng)作函數(shù)分析表包括動(dòng)作函數(shù)action和轉(zhuǎn)移函數(shù)和轉(zhuǎn)移函數(shù)goto兩部?jī)刹糠纸M成分組成根據(jù)棧頂當(dāng)前的狀態(tài)根據(jù)棧頂當(dāng)前的狀態(tài)sm和當(dāng)前的輸入符號(hào)和當(dāng)前的輸入符號(hào)ai訪問(wèn)訪問(wèn)actionsm , ai，取值包括：取值包括：移進(jìn)移進(jìn)s，其中，其中s是一個(gè)狀態(tài)是一個(gè)狀態(tài)按文法產(chǎn)生式按文法產(chǎn)生式A歸約歸約接受接受出錯(cuò)出錯(cuò)函數(shù)函數(shù)goto取狀態(tài)和文法符號(hào)為變?cè)?，產(chǎn)生一個(gè)狀態(tài)取狀態(tài)和文法符號(hào)為變?cè)?，產(chǎn)生一個(gè)狀態(tài)vLR分析器棧中的文法符號(hào)總是形成活前綴分析器棧中的文法符

17、號(hào)總是形成活前綴v在在LR(0)分析、分析、SLR分析、規(guī)范分析、規(guī)范LR分析和分析和LALR分析中分析中，構(gòu)造一個(gè)識(shí)別文法，構(gòu)造一個(gè)識(shí)別文法G的活前綴的確定有限自動(dòng)機(jī)，的活前綴的確定有限自動(dòng)機(jī)，則則goto函數(shù)是這個(gè)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)，初始狀態(tài)函數(shù)是這個(gè)自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)，初始狀態(tài)是初啟時(shí)置于是初啟時(shí)置于LR分析器棧中的狀態(tài)分析器棧中的狀態(tài)17LR分析器分析器（5）LR分析器的分析器的格局格局是二元組是二元組它的第一個(gè)成分是棧的內(nèi)容，第二個(gè)成分是尚未接收它的第一個(gè)成分是棧的內(nèi)容，第二個(gè)成分是尚未接收的輸入：的輸入：(s0X1s1X2s2Xmsm，aiai+1an$)，這個(gè)格局，這個(gè)格局代

18、表右句型代表右句型X1X2Xmaiai+1an動(dòng)作：動(dòng)作：移進(jìn)：移進(jìn)：如果如果actionsm , ai=移進(jìn)移進(jìn)s，分析器執(zhí)行移進(jìn)動(dòng)作，進(jìn)分析器執(zhí)行移進(jìn)動(dòng)作，進(jìn)入格局入格局(s0X1s1X2s2Xmsmais，ai+1an$) ，其中，其中s=gotosm , ai18LR分析器分析器（6）歸約：歸約：如果如果actionsm , ai=歸約歸約A, 則分析器執(zhí)行歸約則分析器執(zhí)行歸約, 進(jìn)進(jìn)入格局入格局(s0X1s1X2s2Xm-rsm-rAs， aiai+1an$), 其中其中s=gotosm-r , A，r是是的長(zhǎng)度，的長(zhǎng)度，完成這個(gè)動(dòng)作時(shí)，首先從棧中彈出完成這個(gè)動(dòng)作時(shí)，首先從棧中彈出2

19、r個(gè)符號(hào)（包括個(gè)符號(hào)（包括r個(gè)狀態(tài)符號(hào)和個(gè)狀態(tài)符號(hào)和r個(gè)文法符號(hào)，這些文法符號(hào)剛好匹配個(gè)文法符號(hào)，這些文法符號(hào)剛好匹配產(chǎn)生式右部產(chǎn)生式右部 ），然后將產(chǎn)生式左邊的非終結(jié)符），然后將產(chǎn)生式左邊的非終結(jié)符A和和gotosm-r , A的狀態(tài)的狀態(tài)s壓入棧壓入棧在歸約動(dòng)作時(shí)執(zhí)行與歸約產(chǎn)生式相關(guān)的語(yǔ)義動(dòng)作在歸約動(dòng)作時(shí)執(zhí)行與歸約產(chǎn)生式相關(guān)的語(yǔ)義動(dòng)作接受：接受：如果如果actionsm , ai=接受，分析完成接受，分析完成出錯(cuò)：出錯(cuò)：如果如果actionsm , ai=出錯(cuò)，分析器發(fā)現(xiàn)錯(cuò)誤，調(diào)用錯(cuò)出錯(cuò)，分析器發(fā)現(xiàn)錯(cuò)誤，調(diào)用錯(cuò)誤恢復(fù)例程誤恢復(fù)例程19LR分析器分析器（7）LR分析算法分析算法輸入：輸入：L

20、R分析表和輸入串分析表和輸入串輸出：若輸出：若是句子，得到是句子，得到的自下而上分析，否則報(bào)錯(cuò)的自下而上分析，否則報(bào)錯(cuò)方法：方法：將初始狀態(tài)將初始狀態(tài)s0在分析器的棧頂，在分析器的棧頂，$在輸入緩沖區(qū)在輸入緩沖區(qū)讓讓ip指向指向$的第一個(gè)符號(hào)的第一個(gè)符號(hào)repeat forever begin令令s是棧頂?shù)臓顟B(tài)，是棧頂?shù)臓顟B(tài)，a是是ip指向的符號(hào)指向的符號(hào)if actions , a = 移進(jìn)移進(jìn)s then begin把把a(bǔ)和和s依次壓入棧依次壓入棧推進(jìn)推進(jìn)ip指向下一個(gè)輸入符號(hào)指向下一個(gè)輸入符號(hào)endelse if actions , a=歸約歸約A then begin棧頂彈出棧頂彈出2

21、*|個(gè)符號(hào)個(gè)符號(hào)令令s是現(xiàn)在的棧頂狀態(tài)是現(xiàn)在的棧頂狀態(tài)把把A和和gotos , A壓入棧壓入棧輸出產(chǎn)生式輸出產(chǎn)生式A或作相關(guān)的語(yǔ)義動(dòng)作或作相關(guān)的語(yǔ)義動(dòng)作endelse if actions , a=接受接受 then returnelse error()end20LR分析器分析器（8）表達(dá)式文法：對(duì)文法產(chǎn)生式標(biāo)號(hào)表達(dá)式文法：對(duì)文法產(chǎn)生式標(biāo)號(hào)(1) EE+T(2) ET(3) TT*F(4) TF(5) F(E)(6) Fid為了表示的簡(jiǎn)便，對(duì)各類動(dòng)作如下簡(jiǎn)化表示：為了表示的簡(jiǎn)便，對(duì)各類動(dòng)作如下簡(jiǎn)化表示：(1) si表示移進(jìn)，把當(dāng)前輸入符號(hào)和狀態(tài)表示移進(jìn)，把當(dāng)前輸入符號(hào)和狀態(tài)i壓進(jìn)棧壓進(jìn)棧(2)

22、 rj表示按第表示按第j個(gè)產(chǎn)生式進(jìn)行歸約個(gè)產(chǎn)生式進(jìn)行歸約(3) acc表示接受表示接受(4) 空白表示出錯(cuò)空白表示出錯(cuò)21LR分析器分析器（9）狀 態(tài)狀 態(tài)動(dòng) 作動(dòng) 作id + * ( ) $id + * ( ) $0 0s5s51 12 23 34 4s5s55 56 6s5s57 7s5s58 89 910101111s6s6r2r2r4r4accaccs6s6r1r1r3r3r5r5s7s7r4r4r4r4r4r4r2r2r2r2s4s4s4s4r6r6r6r6r6r61 1s4s4s4s4s11s11s7s7r1r1r1r1r3r3r3r3r3r3r5r5r5r5r5r5轉(zhuǎn) 移轉(zhuǎn) 移E

23、 T FE T Fr6r62 23 310102 23 39 93 38 822LR分析器分析器（10）棧棧輸輸 入入動(dòng)動(dòng) 作作 (1) 0 id*id+id$ 移進(jìn)移進(jìn) (2) 0 id 5 *id+id$ 按按Fid歸約歸約 (3) 0 F 3 *id+id$ 按按TF歸約歸約 (4) 0 T 2 *id+id$ 移進(jìn)移進(jìn) (5) 0 T 2 * 7 id+id$ 移進(jìn)移進(jìn) (6) 0 T 2 * 7 id 5 +id$ 按按Fid歸約歸約 (7) 0 T 2 * 7 F 10 +id$ 按按TT*F歸約歸約 (8) 0 T 2 +id$ 按按ET歸約歸約 (9) 0 E 1 +id$ 移

24、進(jìn)移進(jìn) (10)0 E 1 + 6 id$ 移進(jìn)移進(jìn) (11)0 E 1 + 6 id 5 $ 按按Fid歸約歸約 (12)0 E 1 + 6 F 3 $ 按按TF歸約歸約 (13)0 E 1 + 6 T 9 $ 按按EE+T歸約歸約 (14)0 E 1 $ 接受接受23LR分析器分析器（11）LR文法文法定義：一個(gè)文法，如果能夠?yàn)樗鼧?gòu)造出定義：一個(gè)文法，如果能夠?yàn)樗鼧?gòu)造出LR分析表，且表分析表，且表的條目都唯一的條目都唯一性質(zhì)：性質(zhì)：一個(gè)文法如果是一個(gè)文法如果是LR的，只要保證當(dāng)句柄出現(xiàn)在棧頂時(shí)，自左的，只要保證當(dāng)句柄出現(xiàn)在棧頂時(shí)，自左向右掃描的移進(jìn)向右掃描的移進(jìn)-歸約分析器能夠及時(shí)識(shí)別它便

25、足夠了歸約分析器能夠及時(shí)識(shí)別它便足夠了如果句柄出現(xiàn)在棧頂時(shí)，如果句柄出現(xiàn)在棧頂時(shí)，LR分析器不需要掃描整個(gè)棧，棧頂分析器不需要掃描整個(gè)棧，棧頂?shù)臓顟B(tài)符號(hào)包含了所需要的一切信息的狀態(tài)符號(hào)包含了所需要的一切信息LR(k)文法：最多向前看文法：最多向前看k個(gè)符號(hào)就可以決定動(dòng)作的個(gè)符號(hào)就可以決定動(dòng)作的LR分分析器分析的文法稱為析器分析的文法稱為L(zhǎng)R(k)文法文法與與LL文法的區(qū)別：文法的區(qū)別：LR(k)文法：在看見(jiàn)了產(chǎn)生式右部推導(dǎo)出的所有東西和文法：在看見(jiàn)了產(chǎn)生式右部推導(dǎo)出的所有東西和k個(gè)向個(gè)向前看的符號(hào)后，能識(shí)別產(chǎn)生式右部的出現(xiàn)前看的符號(hào)后，能識(shí)別產(chǎn)生式右部的出現(xiàn)LL(k)文法：在看見(jiàn)了右部推出的前

26、文法：在看見(jiàn)了右部推出的前k個(gè)符號(hào)就能識(shí)別所使用個(gè)符號(hào)就能識(shí)別所使用的產(chǎn)生式的產(chǎn)生式24LR分析器分析器（12）LR(0)項(xiàng)目的有限自動(dòng)機(jī)項(xiàng)目的有限自動(dòng)機(jī)LR(0)項(xiàng)目（項(xiàng)目（LR(0) item，簡(jiǎn)稱項(xiàng)目、，簡(jiǎn)稱項(xiàng)目、item）：）：是是在右部帶有區(qū)分位置（一般是用一個(gè)在右部帶有區(qū)分位置（一般是用一個(gè)“.”表示表示這個(gè)區(qū)分的位置）的產(chǎn)生式這個(gè)區(qū)分的位置）的產(chǎn)生式如果如果A是一個(gè)產(chǎn)生式，且是一個(gè)產(chǎn)生式，且=，則則A.是是LR(0)項(xiàng)目，其中項(xiàng)目，其中和和可以是空串可以是空串。如果如果A是一個(gè)產(chǎn)生式，則它只對(duì)應(yīng)了一個(gè)項(xiàng)目是一個(gè)產(chǎn)生式，則它只對(duì)應(yīng)了一個(gè)項(xiàng)目A.項(xiàng)目的解釋：項(xiàng)目的解釋：項(xiàng)目項(xiàng)目A.表

27、示已經(jīng)看到了表示已經(jīng)看到了(此時(shí)，此時(shí)，必須出現(xiàn)在棧的必須出現(xiàn)在棧的頂部頂部)，且可能從下面的輸入符號(hào)中獲取，且可能從下面的輸入符號(hào)中獲取項(xiàng)目項(xiàng)目A.表示將要用產(chǎn)生式表示將要用產(chǎn)生式A來(lái)識(shí)別來(lái)識(shí)別A，這種項(xiàng)目這種項(xiàng)目也稱為初始項(xiàng)目也稱為初始項(xiàng)目項(xiàng)目項(xiàng)目A.表示表示出現(xiàn)在分析棧的頂部，而且如果出現(xiàn)在分析棧的頂部，而且如果A在下一個(gè)歸約中使用，則它可能是句柄，這種項(xiàng)目稱在下一個(gè)歸約中使用，則它可能是句柄，這種項(xiàng)目稱為完整項(xiàng)目為完整項(xiàng)目25LR分析器分析器（13）例例2：考慮文法：考慮文法S(S)S | ，給出給出LR(0)項(xiàng)目項(xiàng)目首先構(gòu)造拓廣文法：加入一個(gè)產(chǎn)生式首先構(gòu)造拓廣文法：加入一個(gè)產(chǎn)生式SS

28、，分析器執(zhí)行歸分析器執(zhí)行歸約約SS時(shí)，表示分析成功時(shí)，表示分析成功在構(gòu)造在構(gòu)造LR(0)項(xiàng)目，共項(xiàng)目，共8個(gè)個(gè) S.S SS. S.(S)S S(.S)S S(S.)S S(S).S S(S)S. S.26LR分析器分析器（14）LR(0)項(xiàng)目集合的有限自動(dòng)機(jī)的構(gòu)造項(xiàng)目集合的有限自動(dòng)機(jī)的構(gòu)造若有項(xiàng)目若有項(xiàng)目A.，且假設(shè)且假設(shè)以符號(hào)以符號(hào)X（終結(jié)符或非終終結(jié)符或非終結(jié)符）開(kāi)始（即結(jié)符）開(kāi)始（即=X），），則讀入則讀入X后，項(xiàng)目變?yōu)楹?，?xiàng)目變?yōu)锳X.，在自動(dòng)機(jī)中有一個(gè)標(biāo)記為在自動(dòng)機(jī)中有一個(gè)標(biāo)記為X的由狀態(tài)的由狀態(tài)A.X到狀態(tài)到狀態(tài)AX.的轉(zhuǎn)換的轉(zhuǎn)換這個(gè)轉(zhuǎn)換的意義是：這個(gè)轉(zhuǎn)換的意義是：如果如果X是一

29、個(gè)終結(jié)符，表示是一個(gè)終結(jié)符，表示X在分析中被從輸入移進(jìn)到在分析中被從輸入移進(jìn)到棧的頂部棧的頂部如果如果X是一個(gè)非終結(jié)符，可以理解為是用產(chǎn)生式是一個(gè)非終結(jié)符，可以理解為是用產(chǎn)生式X歸約時(shí)發(fā)生，這個(gè)歸約前面必須有一個(gè)歸約時(shí)發(fā)生，這個(gè)歸約前面必須有一個(gè)的識(shí)別，而由的識(shí)別，而由初始項(xiàng)目初始項(xiàng)目X.給出的狀態(tài)表明這個(gè)識(shí)別的開(kāi)始，此時(shí)給出的狀態(tài)表明這個(gè)識(shí)別的開(kāi)始，此時(shí)，必須考慮加入下面的轉(zhuǎn)換，必須考慮加入下面的轉(zhuǎn)換如果如果X是非終結(jié)符，則對(duì)每個(gè)項(xiàng)目是非終結(jié)符，則對(duì)每個(gè)項(xiàng)目A.X，添加一添加一個(gè)到項(xiàng)目個(gè)到項(xiàng)目X.的的轉(zhuǎn)換（如果以轉(zhuǎn)換（如果以X為左部的產(chǎn)生式多為左部的產(chǎn)生式多于一個(gè)，則每個(gè)都要如此處理）于一個(gè)

30、，則每個(gè)都要如此處理）27LR分析器分析器（15）自動(dòng)機(jī)的初始狀態(tài)與分析程序的初始狀態(tài)對(duì)應(yīng)：棧是自動(dòng)機(jī)的初始狀態(tài)與分析程序的初始狀態(tài)對(duì)應(yīng)：棧是空的，且將要識(shí)別一個(gè)文法的開(kāi)始符號(hào)空的，且將要識(shí)別一個(gè)文法的開(kāi)始符號(hào)S，但由于但由于S可可能出現(xiàn)在多個(gè)產(chǎn)生式的左部，所以拓廣文法，加入能出現(xiàn)在多個(gè)產(chǎn)生式的左部，所以拓廣文法，加入S和產(chǎn)生式和產(chǎn)生式SS，S是拓廣文法的開(kāi)始符號(hào)，是拓廣文法的開(kāi)始符號(hào)，S.S是是自動(dòng)機(jī)的開(kāi)始狀態(tài)自動(dòng)機(jī)的開(kāi)始狀態(tài)自動(dòng)機(jī)的接受狀態(tài)：此處的自動(dòng)機(jī)是用于了解分析的自動(dòng)機(jī)的接受狀態(tài)：此處的自動(dòng)機(jī)是用于了解分析的狀態(tài)，而不是完全識(shí)別串，因此分析程序本身決定何狀態(tài)，而不是完全識(shí)別串，因此分

31、析程序本身決定何時(shí)接受，自動(dòng)機(jī)不必關(guān)心，所以可以沒(méi)有接受狀態(tài)時(shí)接受，自動(dòng)機(jī)不必關(guān)心，所以可以沒(méi)有接受狀態(tài)28LR分析器分析器（16）例例2對(duì)應(yīng)的對(duì)應(yīng)的NFA：S S. .S SS S. .( (S S) )S SS S( (. .S S) )S SS SS S. .S S. .S S( (S S) )S S. .S S( (S S. .) )S SS S( (S S) ). .S SS S( (S S) )S S29LR分析器分析器（17）例例2對(duì)應(yīng)的對(duì)應(yīng)的DFA：S.SS.SS.(S)SS.(S)SS.S.0 0S(.S)SS(.S)SS.(S)SS.(S)SS.S.2 2SS.SS.1 1

32、S(S.)SS(S.)S3 3S(S).SS(S).SS.(S)SS.(S)SS.S.4 4S(S)S.S(S)S.5 5S S( (S S) )S S( ( (30LR分析器分析器（18）文法的文法的LR項(xiàng)目的閉包計(jì)算項(xiàng)目的閉包計(jì)算對(duì)于文法對(duì)于文法G的的LR項(xiàng)目集項(xiàng)目集I，閉包閉包c(diǎn)losure(I)的計(jì)算：的計(jì)算：J := Irepeatfor J 的每個(gè)項(xiàng)目的每個(gè)項(xiàng)目A.B和和G的每個(gè)產(chǎn)生式的每個(gè)產(chǎn)生式B，若若B.不在不在J中中 do把把B.加入加入Juntil 沒(méi)有更多的項(xiàng)目可以加入沒(méi)有更多的項(xiàng)目可以加入JLR(0)分析算法分析算法僅根據(jù)棧中的符號(hào)就可以決定動(dòng)作僅根據(jù)棧中的符號(hào)就可以決

33、定動(dòng)作若項(xiàng)目若項(xiàng)目A.a屬于屬于Ik且且GO1(Ik，a)= Ij，a為終結(jié)符，則置為終結(jié)符，則置ACTIONk，a為為sj若項(xiàng)目若項(xiàng)目A.屬于屬于Ik，那么對(duì)任何終結(jié)符，那么對(duì)任何終結(jié)符a（或結(jié)束符（或結(jié)束符$），置），置ACTIONk，a為為rj(假定產(chǎn)生式假定產(chǎn)生式A是文法的第是文法的第j個(gè)產(chǎn)生式個(gè)產(chǎn)生式)若項(xiàng)目若項(xiàng)目SS.屬于屬于Ik，則置，則置ACTIONk，$為接受為接受若若GOIk，A= Ij ，A為非終結(jié)符，則置為非終結(jié)符，則置gotok，A=j。分析表中凡不能用規(guī)則分析表中凡不能用規(guī)則14填入信息的空白格均置為報(bào)錯(cuò)填入信息的空白格均置為報(bào)錯(cuò)1此處的此處的GO是指自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)

34、換，而不是是指自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換，而不是LR分析中的轉(zhuǎn)移表（用分析中的轉(zhuǎn)移表（用goto表示）表示）31LR分析器分析器（19）項(xiàng)目的分類：項(xiàng)目的分類：核心項(xiàng)目：包括初始項(xiàng)目核心項(xiàng)目：包括初始項(xiàng)目S.S和所有點(diǎn)不在左和所有點(diǎn)不在左端的項(xiàng)目端的項(xiàng)目非核心項(xiàng)目：它們的點(diǎn)都在左端非核心項(xiàng)目：它們的點(diǎn)都在左端項(xiàng)目分類的意義：項(xiàng)目分類的意義：DFA應(yīng)用的項(xiàng)目集是核心項(xiàng)目的閉包形成應(yīng)用的項(xiàng)目集是核心項(xiàng)目的閉包形成若有一個(gè)文法，核心項(xiàng)目唯一地判斷出狀態(tài)以及若有一個(gè)文法，核心項(xiàng)目唯一地判斷出狀態(tài)以及它的轉(zhuǎn)換，則只需指出核心項(xiàng)目就可以完整地表它的轉(zhuǎn)換，則只需指出核心項(xiàng)目就可以完整地表示出項(xiàng)目集合的示出項(xiàng)目集合的D

35、FA32LR分析器分析器（20）SLR分析分析規(guī)范的規(guī)范的LR(0)族：提供了構(gòu)造族：提供了構(gòu)造SLR分析表的基礎(chǔ)分析表的基礎(chǔ)對(duì)于對(duì)于LR(0)規(guī)范族中的項(xiàng)目集：規(guī)范族中的項(xiàng)目集：I = X.b, A. , B. LR(0)無(wú)法區(qū)分這三個(gè)不沖突的項(xiàng)目，此時(shí)要考察無(wú)法區(qū)分這三個(gè)不沖突的項(xiàng)目，此時(shí)要考察FOLLOW(A)和和FOLLOW(B)集合集合構(gòu)造算法：構(gòu)造算法：C := closure(S.S)repeatfor 對(duì)對(duì)C的每個(gè)項(xiàng)目集的每個(gè)項(xiàng)目集I和每個(gè)文法符號(hào)和每個(gè)文法符號(hào)X，若若goto(I , X)非空且不在非空且不在C中中 do把把goto(I , X)加入加入C中中until 沒(méi)有

36、更多的項(xiàng)目可以加入沒(méi)有更多的項(xiàng)目可以加入C33LR分析器分析器（21）例例3：拓廣的表達(dá)式文法：拓廣的表達(dá)式文法：EEEE+T | TTT*F | FF(E) | id對(duì)應(yīng)的對(duì)應(yīng)的LR(0)項(xiàng)目集規(guī)范族如下：項(xiàng)目集規(guī)范族如下：I0:E.E I5: Fid.E .E+TE .T I6: EE+.TT .T*FT.T*FT .FT.FF .(E)F.(E)F .idF.id34LR分析器分析器（22）I1:EE. I7: TT*.FE E.+TF.(E)F.idI2: E T.T T.*F I8: F(E.)EE.+TI3: T F. I9: EE+T.I4: F (.E)TT.*FE .E+TE

37、 .T I10: TT*F.T .T*FT .F I11: F(E).F .(E)F .id35LR分析器分析器（23）I I0 0I I1 1I I6 6I I9 9I I2 2E E+ +T T* *指向I指向I7 7F F指向I指向I3 3( (指向I指向I4 4idid指向I指向I5 5I I7 7I I1010* *F F( (指向I指向I4 4idid指向I指向I5 5I I3 3I I4 4I I8 8I I1111E E) )+ +指向I指向I6 6T T指向I指向I2 2F F指向I指向I3 3I I5 5idididid( (F FT T( (36LR分析器分析器（24）如

38、果將這個(gè)如果將這個(gè)DFA中的每個(gè)狀態(tài)定為接受狀態(tài)，而中的每個(gè)狀態(tài)定為接受狀態(tài)，而I0定為初定為初態(tài)，則這個(gè)態(tài)，則這個(gè)DFA識(shí)別文法的活前綴識(shí)別文法的活前綴對(duì)于項(xiàng)目對(duì)于項(xiàng)目A1.2對(duì)活前綴對(duì)活前綴1是是有效有效的，是指存的，是指存在推導(dǎo)序列在推導(dǎo)序列A1.2對(duì)活前綴對(duì)活前綴1有效表明當(dāng)有效表明當(dāng)1在分析棧頂時(shí)在分析棧頂時(shí)v如果如果2是是，則則A1是句柄，應(yīng)該用這個(gè)產(chǎn)生式歸約是句柄，應(yīng)該用這個(gè)產(chǎn)生式歸約v如果如果2不是不是，則表示句柄還沒(méi)有完全進(jìn)棧，要繼續(xù)移進(jìn)則表示句柄還沒(méi)有完全進(jìn)棧，要繼續(xù)移進(jìn)同一個(gè)活前綴的兩個(gè)有效項(xiàng)目可能對(duì)應(yīng)了不同的動(dòng)作同一個(gè)活前綴的兩個(gè)有效項(xiàng)目可能對(duì)應(yīng)了不同的動(dòng)作，引起了沖突

39、，引起了沖突v這種沖突可以通過(guò)向前看幾個(gè)符號(hào)解決，也可以通過(guò)其這種沖突可以通過(guò)向前看幾個(gè)符號(hào)解決，也可以通過(guò)其它方式解決它方式解決AS21rm*rm37LR分析器分析器（25）SLR分析表的構(gòu)造分析表的構(gòu)造輸入：拓廣文法輸入：拓廣文法G輸出：輸出：G的的SLR分析表函數(shù)分析表函數(shù)action和和goto方法：方法：(1)構(gòu)造構(gòu)造C=I0 , I1 , , In ，即即G的的LR(0)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族 (2)狀態(tài)狀態(tài)i從從Ii構(gòu)造，它的動(dòng)作如下確定：構(gòu)造，它的動(dòng)作如下確定： (a) 如果如果A.a在在Ii中，并且中，并且( Ii , a) = Ij，則置則置 action(i , a)為

40、為sj,含義是把含義是把a(bǔ)和狀態(tài)和狀態(tài)j移進(jìn)棧移進(jìn)棧, a必須為終結(jié)符必須為終結(jié)符 (b) 如果如果A.在在Ii中，則對(duì)中，則對(duì)FOLLOW(A)中的所有中的所有a，置置 action(i , a)為為rj, j是產(chǎn)生式是產(chǎn)生式A的編號(hào)。含義是按產(chǎn)生的編號(hào)。含義是按產(chǎn)生 式式A歸約，這里歸約，這里A不是不是S (c) 如果如果SS.在在Ii中，則置中，則置action(i , $)=acc，表示接受表示接受 (3)對(duì)所有的非終結(jié)符對(duì)所有的非終結(jié)符A，使用下面的規(guī)則構(gòu)造狀態(tài)使用下面的規(guī)則構(gòu)造狀態(tài)i的轉(zhuǎn)移：的轉(zhuǎn)移： 如果如果( Ii , A) = Ij，則則gotoi , A=j (4)不能由規(guī)則

41、不能由規(guī)則(2)和和(3)定義的條目置為出錯(cuò)定義的條目置為出錯(cuò) (5)分析器的初始狀態(tài)是包含分析器的初始狀態(tài)是包含S.S的項(xiàng)目集對(duì)應(yīng)的狀態(tài)的項(xiàng)目集對(duì)應(yīng)的狀態(tài)38LR分析器分析器（26）如果在規(guī)則如果在規(guī)則(2)的構(gòu)造中產(chǎn)生的動(dòng)作有沖突，則該文的構(gòu)造中產(chǎn)生的動(dòng)作有沖突，則該文法不是法不是SLR(1)文法文法由上述算法生成的分析表成為文法由上述算法生成的分析表成為文法G的的SLR(1)分析表分析表每個(gè)每個(gè)SLR(1)文法都不是二義的文法都不是二義的存在非二義的文法，這個(gè)文法不是存在非二義的文法，這個(gè)文法不是SLR(1)的的對(duì)于在棧頂狀態(tài)對(duì)于在棧頂狀態(tài)s中的任何項(xiàng)目中的任何項(xiàng)目A.X，當(dāng)當(dāng)X是一個(gè)是

42、一個(gè)終結(jié)符，且終結(jié)符，且X在在FOLLOW (B)中時(shí)，中時(shí)，s中沒(méi)有完整的項(xiàng)中沒(méi)有完整的項(xiàng)目目B.。（。（若不滿足，則存在移進(jìn)若不滿足，則存在移進(jìn)-歸約沖突）歸約沖突）對(duì)于在對(duì)于在s中的任何兩個(gè)完整項(xiàng)目中的任何兩個(gè)完整項(xiàng)目A.和和B.，F(xiàn)OLLOW(A)與與FOLLOW(B)的交集為空集。（若不滿的交集為空集。（若不滿足，則存在歸約足，則存在歸約-歸約沖突）歸約沖突）SLR(1)分析能力比分析能力比LR(0)強(qiáng)，但仍然不能夠滿足要求強(qiáng)，但仍然不能夠滿足要求39LR分析器分析器（27）LR(1)規(guī)范分析規(guī)范分析SLR分析不能解決某些移進(jìn)分析不能解決某些移進(jìn)-歸約沖突，而歸約沖突，而LR(1)規(guī)

43、范規(guī)范分析可以，參考陳意云書(shū)的例分析可以，參考陳意云書(shū)的例3.31和和3.32LR(1)項(xiàng)目：項(xiàng)目：A.，a，其中其中A是產(chǎn)生式，是產(chǎn)生式，a是終結(jié)符號(hào)或是終結(jié)符號(hào)或$。1是指第二個(gè)成分的長(zhǎng)度，這個(gè)成分稱為項(xiàng)目的搜索符是指第二個(gè)成分的長(zhǎng)度，這個(gè)成分稱為項(xiàng)目的搜索符搜索符對(duì)搜索符對(duì)非空的項(xiàng)目非空的項(xiàng)目A.，a是不起作用的，但對(duì)是不起作用的，但對(duì)項(xiàng)目項(xiàng)目A. ，a，表示只有在下一個(gè)輸入符號(hào)為表示只有在下一個(gè)輸入符號(hào)為a時(shí)才能要求按時(shí)才能要求按A歸約歸約SLR(1)和和LR(1)對(duì)向前看符號(hào)的使用的不同：對(duì)向前看符號(hào)的使用的不同：SLR(1)是在是在LR(0)項(xiàng)目的項(xiàng)目的DFA構(gòu)造完成后才考慮提供向

44、構(gòu)造完成后才考慮提供向前看的符號(hào)，前看的符號(hào)，DFA的構(gòu)造中不考慮向前看的符號(hào)的構(gòu)造中不考慮向前看的符號(hào)LR(1)是在一開(kāi)始就考慮向前看符號(hào)，是在一開(kāi)始就考慮向前看符號(hào)，DFA的構(gòu)造是在的構(gòu)造是在考慮向前看符號(hào)的基礎(chǔ)上進(jìn)行的考慮向前看符號(hào)的基礎(chǔ)上進(jìn)行的40LR分析器分析器（28）LR(1)項(xiàng)目項(xiàng)目A.，a對(duì)活前綴對(duì)活前綴是是有效有效的，如果存的，如果存在著推導(dǎo)在著推導(dǎo) 其中：其中： = a是是的第一個(gè)符號(hào)，或者的第一個(gè)符號(hào)，或者是是則則a是是$例：考慮文法例：考慮文法SBB BaB | b對(duì)于最右推導(dǎo)：對(duì)于最右推導(dǎo)： ，項(xiàng)目，項(xiàng)目Ba.B，a對(duì)于對(duì)于活前綴活前綴 =aaa是有效的，是有效的，=

45、aa，A=B，=ab， =a和和=B對(duì)于最右推導(dǎo)：對(duì)于最右推導(dǎo)： ，項(xiàng)目，項(xiàng)目Ba.B，$對(duì)于活前對(duì)于活前綴綴Baa是有效的是有效的ASrm*rmaaaBabaaBabSrm*rmBaaBBaBSrm*rm41LR分析器分析器（29）有效的有效的LR(1)項(xiàng)目集族的構(gòu)造方法本質(zhì)上和構(gòu)造項(xiàng)目集族的構(gòu)造方法本質(zhì)上和構(gòu)造LR(0)項(xiàng)目集項(xiàng)目集規(guī)范族的方法是一樣的規(guī)范族的方法是一樣的Closure函數(shù)的構(gòu)造：函數(shù)的構(gòu)造：v考慮對(duì)活前綴考慮對(duì)活前綴有效的項(xiàng)目集中的項(xiàng)目有效的項(xiàng)目集中的項(xiàng)目A.B，a。必定存在一個(gè)最右推導(dǎo)必定存在一個(gè)最右推導(dǎo) , 其中其中=，假定假定ax推出終結(jié)符串推出終結(jié)符串by，則對(duì)每

46、個(gè)形式則對(duì)每個(gè)形式B的產(chǎn)的產(chǎn)生式，有推導(dǎo)生式，有推導(dǎo) ，于是，于是B.，b對(duì)對(duì)有效有效vb可能是從可能是從推出的第一個(gè)終結(jié)符，或者推出的第一個(gè)終結(jié)符，或者是空串，是空串，b就成了就成了a，即即b = FIRST(ax)，但在此處，考慮到但在此處，考慮到a是終結(jié)符，所以是終結(jié)符，所以有有FIRST(ax)= FIRST(a)xBxASrm*rmaa byBbySrm*rm42LR分析器分析器（30）Closure函數(shù)構(gòu)造的算法：函數(shù)構(gòu)造的算法：Function closure(I)Beginrepeatfor 對(duì)對(duì)I的每個(gè)項(xiàng)目的每個(gè)項(xiàng)目A.B，a，G中的每個(gè)產(chǎn)生式中的每個(gè)產(chǎn)生式B 和和FIRST

47、(a)的每個(gè)終結(jié)符的每個(gè)終結(jié)符b,如果如果B.，b不在不在I中中 do把把B.，b加到加到I中中until 再?zèng)]有項(xiàng)目可加到再?zèng)]有項(xiàng)目可加到I中中return Iend43LR分析器分析器（31）Goto函數(shù)的構(gòu)造：函數(shù)的構(gòu)造：function goto( I , X )begin令令J是項(xiàng)目是項(xiàng)目A X.，a的集合，使得的集合，使得A .X，a 在在I中中return closure(J)end項(xiàng)目的構(gòu)造：項(xiàng)目的構(gòu)造：procedure items(G)beginC := closure(S.S，$)repeat for C的每個(gè)項(xiàng)目的每個(gè)項(xiàng)目I和每個(gè)文法符號(hào)和每個(gè)文法符號(hào)X，若若goto(

48、I , X)非空且非空且 不在不在C中中 do把把goto(I , X)加入加入C中中until 再?zèng)]有項(xiàng)目集可以加入再?zèng)]有項(xiàng)目集可以加入C中中end44LR分析器分析器（31）規(guī)范的規(guī)范的LR(1)分析表的構(gòu)造與分析表的構(gòu)造與SLR分析表的構(gòu)造相似分析表的構(gòu)造相似輸入：拓廣文法輸入：拓廣文法G輸出：輸出：G的的LR(1)分析表函數(shù)分析表函數(shù)action和和goto方法：方法：(1)構(gòu)造構(gòu)造C=I0 , I1 , , In ，即即G的的LR(1)項(xiàng)目集規(guī)范族項(xiàng)目集規(guī)范族 (2)狀態(tài)狀態(tài)i從從Ii構(gòu)造，它的動(dòng)作如下確定：構(gòu)造，它的動(dòng)作如下確定： (a) 如果如果A.a, b在在Ii中，并且中，并

49、且goto( Ii , a) = Ij，則置則置 action(i , a)為為sj,含義是把含義是把a(bǔ)和狀態(tài)和狀態(tài)j移進(jìn)棧移進(jìn)棧, a必須為終結(jié)符必須為終結(jié)符 (b) 如果如果A. , a在在Ii中且中且A不是不是S，則置則置action(i , a)為為rj, j是產(chǎn)生式是產(chǎn)生式A的編號(hào)。含義是按產(chǎn)生式的編號(hào)。含義是按產(chǎn)生式A歸約歸約 (c) 如果如果SS. , $在在Ii中，則置中，則置action(i , $)=acc，表示接受表示接受 (3)對(duì)所有的非終結(jié)符對(duì)所有的非終結(jié)符A，使用下面的規(guī)則構(gòu)造狀態(tài)使用下面的規(guī)則構(gòu)造狀態(tài)i的轉(zhuǎn)移：的轉(zhuǎn)移： 如果如果DFA的轉(zhuǎn)換函數(shù)的轉(zhuǎn)換函數(shù)goto(

50、 Ii , A) = Ij，則則gotoi , A=j (4)不能由規(guī)則不能由規(guī)則(2)和和(3)定義的條目置為出錯(cuò)定義的條目置為出錯(cuò) (5)分析器的初始狀態(tài)是包含分析器的初始狀態(tài)是包含S.S , $的項(xiàng)目集對(duì)應(yīng)的狀態(tài)的項(xiàng)目集對(duì)應(yīng)的狀態(tài)45LR分析器分析器（32）如果這個(gè)分析表中的動(dòng)作函數(shù)沒(méi)有多重定義的條目，則如果這個(gè)分析表中的動(dòng)作函數(shù)沒(méi)有多重定義的條目，則這個(gè)文法是這個(gè)文法是LR(1)文法文法在實(shí)際中，除非有二義性，幾乎所有合理的程序設(shè)計(jì)語(yǔ)在實(shí)際中，除非有二義性，幾乎所有合理的程序設(shè)計(jì)語(yǔ)言的文法都是言的文法都是LR(1)文法文法LR(1)分析過(guò)于復(fù)雜，產(chǎn)生的項(xiàng)目集合過(guò)多，尤其是很分析過(guò)于復(fù)雜

51、，產(chǎn)生的項(xiàng)目集合過(guò)多，尤其是很多項(xiàng)目集合的不同僅僅是因?yàn)榈诙€(gè)成分的不同多項(xiàng)目集合的不同僅僅是因?yàn)榈诙€(gè)成分的不同例例4：考慮拓廣文法：考慮拓廣文法S SS CCC cC | d46LR分析器分析器（33）S S . .S S, ,$ $S S. .C CC C, ,$ $C C. .c cC C, , c c/ /d dC C. .d d, ,c c/ /d dI I0 0S S S S. ., ,$ $I I1 1S SC C. .C C, ,$ $C C. .c cC C, ,$ $C C. .d d, ,$ $I I2 2S SC CC C. ., ,$ $I I5 5C Cc c.

52、.C C, ,$ $C C. .c cC C, ,$ $C C. .d d, ,$ $I I6 6C Cc cC C. ., ,$ $I I9 9C Cd d. ., ,$ $I I7 7C Cc c. .C C, ,c c/ /d dC C. .c cC C, ,c c/ /d dC C. .d d, ,c c/ /d dI I3 3C Cc cC C. ., ,c c/ /d dI I8 8C Cd d. ., ,c c/ /d dI I4 4d dd dC CC CC CS Sc cd dc cc cC Cc cd d47LR分析器分析器（34）狀狀 態(tài)態(tài)動(dòng)動(dòng) 作作c c d d $ $

53、0 0s s3 31 12 23 34 45 56 67 78 89 9s s6 6a ac cc cs s7 7r r1 11 1r r2 2轉(zhuǎn)轉(zhuǎn) 移移S S C C2 29 9s s4 45 58 8s s3 3s s4 4r r3 3r r3 3s s6 6s s7 7r r3 3r r2 2r r2 248LR分析器分析器（35）LALR(1)分析（分析（lookahead-LR分析）分析）引入引入LALR分析：分析：LR(1)項(xiàng)目集合的項(xiàng)目集合的DFA狀態(tài)過(guò)于龐大，且很多狀態(tài)的狀態(tài)過(guò)于龐大，且很多狀態(tài)的引入只是因?yàn)橄蚯翱吹姆?hào)的不同引入只是因?yàn)橄蚯翱吹姆?hào)的不同構(gòu)造同心的構(gòu)造同心的L

54、R(1)項(xiàng)目集：它們的第一個(gè)成分集合相項(xiàng)目集：它們的第一個(gè)成分集合相同同vLR(1)項(xiàng)目的項(xiàng)目的DFA的狀態(tài)核心是的狀態(tài)核心是LR(0)項(xiàng)目的項(xiàng)目的DFA的一個(gè)狀態(tài)的一個(gè)狀態(tài)v若具有相同核心的若具有相同核心的LR(1)項(xiàng)目的項(xiàng)目的DFA的兩個(gè)狀態(tài)的兩個(gè)狀態(tài)s1和和s2，假設(shè)假設(shè)在符號(hào)在符號(hào)X上有一個(gè)從狀態(tài)上有一個(gè)從狀態(tài)s1到狀態(tài)到狀態(tài)t1的轉(zhuǎn)換，則在的轉(zhuǎn)換，則在X上必然有上必然有一個(gè)從狀態(tài)一個(gè)從狀態(tài)s2到一個(gè)狀態(tài)到一個(gè)狀態(tài)t2的轉(zhuǎn)換，且狀態(tài)的轉(zhuǎn)換，且狀態(tài)t1和和t2具有相同的具有相同的核心核心LALR具有和具有和SLR一樣個(gè)數(shù)的狀態(tài)，但保留了一樣個(gè)數(shù)的狀態(tài)，但保留了LR分分析的一些特征，能力比

55、析的一些特征，能力比SLR要強(qiáng)要強(qiáng)LALR分析表的構(gòu)造：分析表的構(gòu)造：v將具有相同核心的將具有相同核心的LR(1)項(xiàng)目合并，動(dòng)作和轉(zhuǎn)移函數(shù)也做相項(xiàng)目合并，動(dòng)作和轉(zhuǎn)移函數(shù)也做相應(yīng)的合并應(yīng)的合并49LR分析器分析器（36）LALR(1)分析表是在分析表是在LR(1)分析表的基礎(chǔ)上構(gòu)造的，分析表的基礎(chǔ)上構(gòu)造的，但可能引入但可能引入LR(1)分析中不存在的沖突分析中不存在的沖突v不會(huì)引入移進(jìn)不會(huì)引入移進(jìn)-歸約沖突（因?yàn)槿绻麣w約沖突（因?yàn)槿绻鸏ALR(1)分析表中存在分析表中存在這類沖突，則在同心項(xiàng)目合并前的這類沖突，則在同心項(xiàng)目合并前的LR(1)分析表中必定存在分析表中必定存在沖突）沖突）v可能引進(jìn)歸

56、約可能引進(jìn)歸約-歸約沖突歸約沖突LR(1)能發(fā)現(xiàn)的錯(cuò)誤，能發(fā)現(xiàn)的錯(cuò)誤，LALR(1)也能發(fā)現(xiàn)，只是在報(bào)也能發(fā)現(xiàn)，只是在報(bào)錯(cuò)前可能要多作一些虛假的歸約錯(cuò)前可能要多作一些虛假的歸約對(duì)例對(duì)例4的的LR(1)分析，構(gòu)造分析，構(gòu)造LALR(1)分析：分析：合并同心項(xiàng)目：合并同心項(xiàng)目：I36：Cc.C , c/d/$ C.cC , c/d/$ C.d , c/d/$ I47：Cd. , c/d/$ I89：CcC. , c/d/$50LR分析器分析器（37）狀狀 態(tài)態(tài)動(dòng)動(dòng) 作作c c d d $ $0 0s s3 36 61 12 23 36 64 47 75 58 89 9s s3 36 6a ac c

57、c cs s4 47 7r r1 11 1r r2 2轉(zhuǎn)轉(zhuǎn) 移移S S C C2 2s s4 47 75 58 89 9s s3 36 6s s4 47 7r r3 3r r3 3r r3 3r r2 2r r2 2考慮輸入串考慮輸入串ccd$，對(duì)于對(duì)于LR(1)分析，把分析，把0 c 3 c 3 d 4入棧，在狀態(tài)入棧，在狀態(tài)4發(fā)現(xiàn)錯(cuò)誤發(fā)現(xiàn)錯(cuò)誤而對(duì)于而對(duì)于LALR(1)分析，把分析，把0 c 36 c 36 d 47入棧入棧然后用然后用Cd歸約，棧的內(nèi)容變?yōu)闅w約，棧的內(nèi)容變?yōu)? c 36 c 36 C 89再用再用CcC歸約，棧的內(nèi)容變?yōu)闅w約，棧的內(nèi)容變?yōu)? c 36 C 89第二次用第二次

58、用CcC歸約，棧的內(nèi)容變?yōu)闅w約，棧的內(nèi)容變?yōu)? C 2此時(shí)發(fā)現(xiàn)錯(cuò)誤此時(shí)發(fā)現(xiàn)錯(cuò)誤51二義文法的應(yīng)用二義文法的應(yīng)用二義性文法不是二義性文法不是LR文法，但二義性文法在一些情況下的表示更為文法，但二義性文法在一些情況下的表示更為簡(jiǎn)單簡(jiǎn)單在在LR分析中消除二義性的規(guī)則分析中消除二義性的規(guī)則使用優(yōu)先級(jí)和結(jié)合規(guī)則來(lái)解決分析動(dòng)作的沖突使用優(yōu)先級(jí)和結(jié)合規(guī)則來(lái)解決分析動(dòng)作的沖突移進(jìn)優(yōu)先于歸約的規(guī)則可以解決最長(zhǎng)匹配問(wèn)題如懸掛移進(jìn)優(yōu)先于歸約的規(guī)則可以解決最長(zhǎng)匹配問(wèn)題如懸掛else的問(wèn)的問(wèn)題題特殊情況產(chǎn)生式引起的二義性，可能導(dǎo)致歸約特殊情況產(chǎn)生式引起的二義性，可能導(dǎo)致歸約-歸約沖突，可歸約沖突，可以規(guī)定此時(shí)按特殊情況

59、產(chǎn)生式歸約以規(guī)定此時(shí)按特殊情況產(chǎn)生式歸約如文法：如文法：EE sub E sup E | E sub E | E sup E | E | c如果描述如果描述E sub E sup E的文法符號(hào)和狀態(tài)序列已經(jīng)在分析的文法符號(hào)和狀態(tài)序列已經(jīng)在分析棧中，當(dāng)面臨棧中，當(dāng)面臨或或$時(shí)，選擇下面的哪個(gè)產(chǎn)生式歸約？時(shí)，選擇下面的哪個(gè)產(chǎn)生式歸約？EE sub E sup EEE sup E此時(shí)可以通過(guò)規(guī)定哪個(gè)產(chǎn)生式優(yōu)先歸約來(lái)解決此時(shí)可以通過(guò)規(guī)定哪個(gè)產(chǎn)生式優(yōu)先歸約來(lái)解決52自底向上分析程序中的錯(cuò)誤校正（自底向上分析程序中的錯(cuò)誤校正（1）綜述：綜述：何時(shí)發(fā)現(xiàn)錯(cuò)誤？何時(shí)發(fā)現(xiàn)錯(cuò)誤？當(dāng)分析表中檢測(cè)到一個(gè)空白項(xiàng)（或錯(cuò)誤項(xiàng)

60、），表示發(fā)現(xiàn)了錯(cuò)誤當(dāng)分析表中檢測(cè)到一個(gè)空白項(xiàng)（或錯(cuò)誤項(xiàng)），表示發(fā)現(xiàn)了錯(cuò)誤LR分析中訪問(wèn)轉(zhuǎn)移表不會(huì)發(fā)現(xiàn)錯(cuò)誤分析中訪問(wèn)轉(zhuǎn)移表不會(huì)發(fā)現(xiàn)錯(cuò)誤如何更好地發(fā)現(xiàn)錯(cuò)誤？如何更好地發(fā)現(xiàn)錯(cuò)誤？盡可能多的空白項(xiàng)可以使得分析程序盡可能早地發(fā)現(xiàn)錯(cuò)誤，這盡可能多的空白項(xiàng)可以使得分析程序盡可能早地發(fā)現(xiàn)錯(cuò)誤，這樣的錯(cuò)誤信息更有意義，且是確定的樣的錯(cuò)誤信息更有意義，且是確定的但過(guò)多的空白項(xiàng)使得分析表過(guò)于龐大（考慮但過(guò)多的空白項(xiàng)使得分析表過(guò)于龐大（考慮LALR和和LR分析分析），如果減少錯(cuò)誤項(xiàng)，可能在報(bào)錯(cuò)前會(huì)有一些不必要的歸約動(dòng)），如果減少錯(cuò)誤項(xiàng)，可能在報(bào)錯(cuò)前會(huì)有一些不必要的歸約動(dòng)作發(fā)生，使得報(bào)錯(cuò)不準(zhǔn)確作發(fā)生，使得報(bào)錯(cuò)不準(zhǔn)確特定