[理學(xué)]第四章2 自下而上語(yǔ)法分析ppt課件

1、第四章第四章2 2 自下向上語(yǔ)法分析自下向上語(yǔ)法分析本章要求本章要求:1. 掌握自下向上語(yǔ)法分析的根本思想和根本概念掌握自下向上語(yǔ)法分析的根本思想和根本概念2. 理解算符優(yōu)先語(yǔ)法分析；求理解算符優(yōu)先語(yǔ)法分析；求FIRSTVT集和集和LASTVT集，構(gòu)造算符優(yōu)先關(guān)系表；能運(yùn)用算集，構(gòu)造算符優(yōu)先關(guān)系表；能運(yùn)用算符優(yōu)先分析方法進(jìn)展表達(dá)式分析選學(xué)符優(yōu)先分析方法進(jìn)展表達(dá)式分析選學(xué)3. 掌握句柄的定義與斷定掌握句柄的定義與斷定4. 理解標(biāo)準(zhǔn)歸約的過(guò)程和理解標(biāo)準(zhǔn)歸約的過(guò)程和LRLR分析過(guò)程中的實(shí)現(xiàn)分析過(guò)程中的實(shí)現(xiàn) 5. 掌握掌握LR語(yǔ)法分析的實(shí)現(xiàn)過(guò)程語(yǔ)法分析的實(shí)現(xiàn)過(guò)程例例S aABe A Abc | bB

2、d用歸約的方法對(duì)句子用歸約的方法對(duì)句子abbcde進(jìn)展語(yǔ)法分析。進(jìn)展語(yǔ)法分析。例例S aABe A Abc | bB dabbcde例例S aABe A Abc | bB dabbcdeaAbcdeaAbcde例例S aABe A Abc | bB dabbcdeaAbcdeaAde例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABe例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS 例例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS S rm aABe rm aAde rm aAbcde rm

3、abbcde自下而上的語(yǔ)法分析的一般過(guò)程自下而上的語(yǔ)法分析的一般過(guò)程 實(shí)現(xiàn)思想實(shí)現(xiàn)思想從輸入符號(hào)串開(kāi)場(chǎng)，從左到右進(jìn)展掃描，將輸入符號(hào)逐個(gè)移入一個(gè)棧中，邊移入邊分析，一一旦棧頂符號(hào)串形成某個(gè)產(chǎn)生式的右部時(shí)旦棧頂符號(hào)串形成某個(gè)產(chǎn)生式的右部時(shí)，就用該產(chǎn)生式的左部非終結(jié)符代替，稱為歸約歸約。重復(fù)這一過(guò)程，直到歸約到棧中只剩下文法的開(kāi)場(chǎng)符號(hào)時(shí)，那么分析成功， 稱為“移進(jìn)-歸約方法。從語(yǔ)法樹(shù)的角度語(yǔ)法樹(shù)的角度看：從語(yǔ)法樹(shù)的樹(shù)葉開(kāi)場(chǎng)，逐步向上歸約構(gòu)造分析樹(shù)，直到形成根結(jié)點(diǎn)。是推導(dǎo)推導(dǎo)的逆過(guò)程。 最左推導(dǎo)最左推導(dǎo)Left-most Derive 每次推導(dǎo)都交換當(dāng)前句型的最左邊的非終結(jié)符。 與最右歸約對(duì)應(yīng)。 最

4、右推導(dǎo)最右推導(dǎo)Right-most Derive 每次推導(dǎo)都交換當(dāng)前句型的最右邊的非終結(jié)符。 與最左歸約標(biāo)準(zhǔn)歸約標(biāo)準(zhǔn)歸約對(duì)應(yīng)，得標(biāo)準(zhǔn)句型。例：例：設(shè)有文法GS： 1 S aABe 2 A b 3 A Abc 4 B d 使用最右推導(dǎo)：因?yàn)镾 aABe aAde aAbcde abbcde，所以abbcde是文法G的句子。)1(rm)2(rm)3(rm)4(rm 步驟步驟動(dòng)作動(dòng)作1S aABe2A b 3A Abc4B d最左歸約過(guò)程是最右推導(dǎo)的逆過(guò)程， 對(duì)輸入串a(chǎn)bbcde的移進(jìn)歸約過(guò)程如下：該分析過(guò)程反復(fù)執(zhí)行該分析過(guò)程反復(fù)執(zhí)行“移進(jìn)和移進(jìn)和“歸約兩個(gè)動(dòng)作，直到棧中只有開(kāi)場(chǎng)符號(hào)為止。歸約兩個(gè)動(dòng)

5、作，直到棧中只有開(kāi)場(chǎng)符號(hào)為止。ab aA ab A acbA aA ad A aBA aeBA aS1移進(jìn)a2移進(jìn)b3歸約24移進(jìn)b5移進(jìn)c6歸約37移進(jìn)d8歸約49移進(jìn)e10歸約1“移進(jìn)-歸約分析法中棧的使用 移進(jìn)-歸約分析器使用了一個(gè)符號(hào)棧和一個(gè)輸入緩沖區(qū) 1、句型表示 a1 a2 a3 # X1X2X3#“移進(jìn)-歸約”分析程序輸出棧(存放句型前綴)輸入串符號(hào)棧內(nèi)容符號(hào)棧內(nèi)容 + 輸入緩沖區(qū)內(nèi)容輸入緩沖區(qū)內(nèi)容 # 當(dāng)前句型當(dāng)前句型 #一般形式： 符號(hào)棧的內(nèi)容剩余輸入串初態(tài)：#輸入串#終態(tài)：#S#2、分析器構(gòu)造 3. 過(guò)程描繪：過(guò)程描繪：do do 將輸入串最左邊的符號(hào)移入棧內(nèi); while

6、 在棧里符號(hào)串中找到一個(gè)可歸約在棧里符號(hào)串中找到一個(gè)可歸約串串； 歸約可歸約串 while 文法開(kāi)場(chǎng)符號(hào)出如今棧頂或者發(fā)現(xiàn)錯(cuò)誤；分析成功的條件分析成功的條件：棧頂為文法符號(hào)，輸入串為空。該過(guò)程并未涉及如何在棧里找可歸約串。實(shí)際上，不同的找可歸約串的方法，構(gòu)成了不同的分析算法。分析器的四種動(dòng)作分析器的四種動(dòng)作 1 1 移進(jìn)移進(jìn)：讀入下一個(gè)輸入符號(hào)并把它下推進(jìn)棧。 2 2 歸約歸約：當(dāng)棧頂符號(hào)串形成一個(gè)可歸約的串如：句句柄柄時(shí)，直接進(jìn)展歸約，即用產(chǎn)生式左側(cè)的非終結(jié)符交換棧頂?shù)木浔?3 3 承受承受：當(dāng)棧底只有“#和開(kāi)場(chǎng)符號(hào)，而輸入也已經(jīng)到達(dá)右端標(biāo)志符號(hào)“#時(shí)，識(shí)別出符號(hào)串是句子，執(zhí)行該動(dòng)作，表示

7、分析成功，是歸約的一種特殊情況。 4 4 出錯(cuò)出錯(cuò)：棧頂?shù)膬?nèi)容與輸入符號(hào)相悖，即當(dāng)識(shí)別程序發(fā)現(xiàn)輸入符號(hào)串不是句子時(shí)，進(jìn)展出錯(cuò)處理。 注意：決定移進(jìn)和歸約的根據(jù)是什么？注意：決定移進(jìn)和歸約的根據(jù)是什么？ 棧頂是否出現(xiàn)了可歸約的符號(hào)串。棧頂是否出現(xiàn)了可歸約的符號(hào)串。 “移進(jìn)歸約語(yǔ)法分析小結(jié)： 從輸入串的開(kāi)場(chǎng)依次讀入單詞移進(jìn)移進(jìn)棧中 。 一旦發(fā)現(xiàn)可歸約串可歸約串某個(gè)產(chǎn)生式的右端就立即歸歸約約。 歸約就是將棧頂?shù)囊淮?hào)用文法產(chǎn)生式的左部代替，歸約可能重復(fù)屢次，然后繼續(xù)移進(jìn)。 假設(shè)最終能歸約成文法的開(kāi)場(chǎng)符號(hào)，那么分析成功承受承受；否那么出錯(cuò)出錯(cuò)。 由于總是將句型的最左邊的可歸約串交換成非終結(jié)符，該方法

8、通常得到是最右推導(dǎo)。 關(guān)鍵是如何識(shí)別可歸約的符號(hào)串如何識(shí)別可歸約的符號(hào)串？語(yǔ)法分析中問(wèn)題的提出：語(yǔ)法分析中問(wèn)題的提出： 在構(gòu)造語(yǔ)法樹(shù)的過(guò)程中，何時(shí)歸約？ 當(dāng)可歸約串出如今棧頂時(shí)就進(jìn)展歸約。 如何知道在棧頂符號(hào)串中已經(jīng)形成可歸約串？ 如何進(jìn)展歸約？ 通過(guò)不同的自底向上的分析算法來(lái)解釋，不同的算法對(duì)可歸約串的定義是不同的，但分析過(guò)程都有一個(gè)共同的特點(diǎn)：邊移進(jìn)邊歸約邊移進(jìn)邊歸約。規(guī)范歸約：使用句柄句柄來(lái)定義可歸約串算符優(yōu)先：使用最左素短語(yǔ)最左素短語(yǔ)來(lái)定義可歸約串 自下而上語(yǔ)法分析主要有以下三種方法：自下而上語(yǔ)法分析主要有以下三種方法：簡(jiǎn)單優(yōu)先分析法簡(jiǎn)單優(yōu)先分析法標(biāo)準(zhǔn)歸約標(biāo)準(zhǔn)歸約文法按文法按一定原那么

9、規(guī)定文法符號(hào)的優(yōu)先關(guān)系一定原那么規(guī)定文法符號(hào)的優(yōu)先關(guān)系算符優(yōu)先分析法算符優(yōu)先分析法不標(biāo)準(zhǔn)歸約不標(biāo)準(zhǔn)歸約規(guī)定規(guī)定算符算符之間的優(yōu)先關(guān)系之間的優(yōu)先關(guān)系 LR分析法標(biāo)準(zhǔn)歸約分析法標(biāo)準(zhǔn)歸約 LR0、LR1、SLR1和和LALR1語(yǔ)法分析樹(shù)的生成演示語(yǔ)法分析樹(shù)的生成演示a b b c d ea b b c d eAABSAbAbAAbcAAbcBdBdSaABeSaABe1S aABe2A b 3A Abc4B dS aABe aAde aAbcde abbcde標(biāo)準(zhǔn)歸約相關(guān)概念復(fù)習(xí) 有文法G，開(kāi)場(chǎng)符號(hào)為S, 假如有S=xy,那么xy是文法G的句型句型，x,y是任意的符號(hào)串 假如有S=xAy, 且有A=

10、,那么是句型xy相對(duì)于非終結(jié)符A的短語(yǔ)短語(yǔ) 假如有S=xAy, 且有A-,那么是句型xy相對(duì)于A-的直接短語(yǔ)直接短語(yǔ) 位于一個(gè)一個(gè)句型最左邊的直接短語(yǔ)稱為句柄句柄. 句型- 短語(yǔ) - 直接短語(yǔ) -句柄 *+*注: 每次歸約的部分就是分析為句柄句柄的字符串最右推導(dǎo)。在標(biāo)準(zhǔn)歸約中，關(guān)鍵問(wèn)題就轉(zhuǎn)化為如何識(shí)別句柄如何識(shí)別句柄? ?回到上例用回到上例用句柄句柄對(duì)句子對(duì)句子abbcde進(jìn)展歸約有：進(jìn)展歸約有： 用句柄對(duì)句子進(jìn)展歸約的過(guò)程與用移進(jìn)-歸約過(guò)程是一致的，使用歸約的產(chǎn)生式及其順序是一致的。句型歸約規(guī)那么abbcde1S aABe2A b 3A Abc4B d2 Ab3A AbcaAbcdeaAde

11、4B d1S aABeaABeS練習(xí)：有文法如下練習(xí)：有文法如下 E-E+T|T T-T*F|F F-E|id1寫(xiě)出輸入串寫(xiě)出輸入串 id1+id2*id3 的標(biāo)準(zhǔn)歸約過(guò)程；的標(biāo)準(zhǔn)歸約過(guò)程；2給出該文法給出該文法“移進(jìn)移進(jìn)-歸約語(yǔ)法分析的過(guò)程。歸約語(yǔ)法分析的過(guò)程。E=E+T =E+T*F =E+T*id =E+F*id =E+id*id =T+id*id =F+id*id =id+id*id 動(dòng)作動(dòng)作 棧棧 輸入緩沖區(qū)輸入緩沖區(qū)1 1 準(zhǔn)備準(zhǔn)備 # id# id1 1+id+id2 2* *idid3 3# #2 2 移進(jìn)移進(jìn) #id#id1 1 +id +id2 2* *idid3 3# #

12、3 3 歸約歸約 Fid #F +idFid #F +id2 2* *idid3 3# #4 4 歸約歸約 TF #T +idTF #T +id2 2* *idid3 3# # 5 5 歸約歸約 ET #E +idET #E +id2 2* *idid3 3# #6 6 移進(jìn)移進(jìn) #E+ id#E+ id2 2* *idid3 3# #7 7 移進(jìn)移進(jìn) #E+id#E+id2 2 * *idid3 3# #8 8 歸約歸約 Fid #E+F Fid #E+F * *idid3 3# #9 9 歸約歸約 TF #E+T TF #E+T * *idid3 3# # 1010 移進(jìn)移進(jìn) #E+T#E

13、+T* * id id3 3# #1111 移進(jìn)移進(jìn) #E+T#E+T* *idid3 3 # #1212 歸約歸約 Fid #E+TFid #E+T* *F #F #1313 歸約歸約 TTTT* *F #E+T #F #E+T #1414 歸約歸約 EE+T #E # EE+T #E # 1515 承受承受所得的結(jié)果是：用產(chǎn)生式序列表示語(yǔ)法分析樹(shù)所得的結(jié)果是：用產(chǎn)生式序列表示語(yǔ)法分析樹(shù)E-E+T|TT-T*F|FF-E|ididid1 1 + id + id2 2 * * id id3 3FTEFTFTE移進(jìn)歸約分析中的問(wèn)題移進(jìn)歸約分析中的問(wèn)題 1 1 移進(jìn)移進(jìn)- -歸約沖突歸約沖突 在分

14、析到某一步時(shí)，既可以移進(jìn)，又可以歸約上例第10步可以移進(jìn)*，也可以按產(chǎn)生式EE+T進(jìn)展歸約。 2 2 歸約歸約- -歸約沖突歸約沖突存在兩個(gè)可選的句柄，可對(duì)棧頂符號(hào)進(jìn)展歸約例如上述第13步，可以用TF進(jìn)展歸約，又可以按TT*F進(jìn)展歸約。 各種分析方法中處理沖突的技術(shù)不同各種分析方法中處理沖突的技術(shù)不同算符優(yōu)先分析算符優(yōu)先分析 算符優(yōu)先分析法的思想源于表達(dá)式的分析，即利用相鄰終結(jié)符號(hào)之間的關(guān)系來(lái)尋找可歸約串。 將句型中的終結(jié)符號(hào)當(dāng)作“算符，借助于算符之間的優(yōu)先關(guān)系確定句柄。 顯然，在一個(gè)符號(hào)串中，任意兩個(gè)相鄰終結(jié)符號(hào)a和b之間，只可能存在以下四種優(yōu)先關(guān)系：1 a, b優(yōu)先性一樣，記作a b。2

15、a優(yōu)先性高于b， 記作a b。3 a優(yōu)先性低于b ，記作a b。4 a與b不可能相鄰，即此符號(hào)串不是句型出錯(cuò)。 假如以上四種關(guān)系中的任意兩種都不會(huì)同時(shí)成立，那么可以根據(jù)終結(jié)符號(hào)之間的歸約關(guān)系進(jìn)展語(yǔ)法分析。 1.算符文法:一個(gè)上下無(wú)關(guān)文法G,假如沒(méi)有P-,且沒(méi)有P-.QR.P,Q,R屬于非終結(jié)符,那么G是一個(gè)算符文法。算符文法。 2.算符優(yōu)先關(guān)系算符優(yōu)先關(guān)系的定義自底向上,可通過(guò)樹(shù)形構(gòu)造觀察 a b,G中有P-.ab.或P-.aQb. 在同一產(chǎn)在同一產(chǎn)生式中生式中a b,G中有P-.aR.的產(chǎn)生式,且R=b.或R=Qb. 注意注意ab相鄰相鄰a b,G中有P-.Rb.的產(chǎn)生式,且R=.a或R=.

16、aQ 注意注意ab相鄰相鄰算符優(yōu)先文法的定義+例：EE+E | E*E | E | i 證明不是算符優(yōu)先文法。因?yàn)椋篍E+E ， EE*E 那么有 + *又因?yàn)椋篍E*E, EE+E 那么有 + *所以不是算符優(yōu)先文法。 3.算符優(yōu)先文法算符優(yōu)先文法算符文法G的任何終結(jié)符a,b之間要么沒(méi)有優(yōu)先關(guān)系，假設(shè)有優(yōu)先關(guān)系,至多有 = , 中的一種成立,那么G為一算符優(yōu)先文法算符優(yōu)先文法。算符優(yōu)先關(guān)系表算符優(yōu)先關(guān)系表的構(gòu)造的構(gòu)造 用表格形式來(lái)表示各終結(jié)符號(hào)的優(yōu)先關(guān)用表格形式來(lái)表示各終結(jié)符號(hào)的優(yōu)先關(guān)系，這種表稱為優(yōu)先表。系，這種表稱為優(yōu)先表。 構(gòu)造優(yōu)先關(guān)系表的方法：構(gòu)造優(yōu)先關(guān)系表的方法： 按照定義手工計(jì)算

17、按照定義手工計(jì)算 使用算法使用算法 由F-E 得 = T = i, 得 + T*F, 得 + E, 得 + E+TE = i, 得i +E = E+T, 得+ + E = T*F, 得* + E = E, 得 + +*i#+*i#例:P:E-E+T|T T-T*F|F F-E|i 求算符優(yōu)先表。終結(jié)符+#終結(jié)符+#對(duì)于結(jié)束符#和其它終結(jié)符a有關(guān)系: # # * 在優(yōu)先表中，空白部分是一種錯(cuò)誤關(guān)系 一樣的終結(jié)符之間的優(yōu)先關(guān)系不一定是 假如有a b,不一定有b a不具傳遞性，因?yàn)橹欢x相鄰運(yùn)算符之間的優(yōu)先關(guān)系，a,b相鄰時(shí)，不一定b,a相鄰。 a,b之間未必有優(yōu)先關(guān)系 , , 算符優(yōu)先關(guān)系表的構(gòu)造

18、算法算符優(yōu)先關(guān)系表的構(gòu)造算法 1.FIRSTVT1.FIRSTVT集集定義：對(duì)每個(gè)非終結(jié)符P, FIRSTVTP=a|P=a.或P=Qa.,a為終結(jié)符,P，Q為非終結(jié)符+由優(yōu)先性低于的定義和FIRSTVT集合的定義可以得出：若存在某個(gè)產(chǎn)生式：aP，對(duì)所有：bfirstVT(P)都有：a a.或P-Qa.,那么aFIRSTVTP 假設(shè)有產(chǎn)生式P-R.,那么FIRSTVTR包含在FIRSTVTP中abcPQ所有終結(jié)符所有非終結(jié)符數(shù)組值為真假，為真的條件是c FIRSTVTQ 通過(guò)構(gòu)造一個(gè)二維數(shù)組F來(lái)實(shí)現(xiàn),該從數(shù)組F反映任何一個(gè)非終結(jié)符P的FIRSRVT集中的元素。步驟： 先用第一條規(guī)那么進(jìn)展初始化

19、先用第一條規(guī)那么進(jìn)展初始化 使用第二條規(guī)那么對(duì)數(shù)組使用第二條規(guī)那么對(duì)數(shù)組F F進(jìn)展修改，進(jìn)展修改，修改方法是： 1 用一個(gè)棧，將所有F數(shù)組中值為真的元素FP,a的符號(hào)對(duì)P,a壓入堆棧； 2 對(duì)棧施行如下操作：假設(shè)棧不空，將棧頂符號(hào)對(duì)出棧，記為Q,a，檢查所有的產(chǎn)生式，假設(shè)有形為：PQ的產(chǎn)生式，且FP,a為假，那么使FP,a為真，且將P,a壓入堆棧； 3 重復(fù)這一過(guò)程，直到?？涨笪姆ǜ鞣墙K結(jié)符的firstVT： 定義數(shù)組：+*iE1T1F11EE+T | TTT*F | FFE | i11111從而得到：從而得到：FirstVTE = +, *, IFirstVTT = *,IFirstVTF

20、= ,IBeginFor 對(duì)每個(gè)非終結(jié)符對(duì)每個(gè)非終結(jié)符P和終結(jié)符和終結(jié)符a doFP,a = falseFor 對(duì)每個(gè)形如對(duì)每個(gè)形如Pa或或PQa的產(chǎn)生式的產(chǎn)生式 doInsertP,aWhile stack 非空非空Begin把棧頂項(xiàng)出棧，記為把棧頂項(xiàng)出棧，記為Q,aFor 對(duì)每條形如對(duì)每條形如PQ的產(chǎn)生式的產(chǎn)生式 do insertP,aEnd;End.PROCEDURE insertP,a;IF not FP,a then begin fp,a = true; P,a進(jìn)進(jìn)棧棧 end;對(duì)數(shù)組初始化應(yīng)用規(guī)那么1應(yīng)用規(guī)那么2 2. 求求LASTVT集集 定義：LASTVTP=a|P = .a

21、或P =. aQ,a為終結(jié)符,P，Q為非終結(jié)符+構(gòu)造LASTVT集算法: 考慮？ 3.3.構(gòu)造優(yōu)先關(guān)系表構(gòu)造優(yōu)先關(guān)系表假如每個(gè)非終結(jié)符的FIRSTVT和LASTVT集均,那么可構(gòu)造優(yōu)先關(guān)系表。假設(shè)產(chǎn)生式右部有.aP.的形式,那么對(duì)于每個(gè)bFIRSTVTP都有a b優(yōu)先集假設(shè)產(chǎn)生式右部有.Pb的形式,那么對(duì)于每個(gè)aLASTVTP集,都有a b 假設(shè)產(chǎn)生是形如：Aab 或 AaBb形式，那么有a b 構(gòu)造優(yōu)先關(guān)系表的算法如下：For 每條形如每條形如PX1X2Xn的的產(chǎn)生式產(chǎn)生式 dofor i =1 to n-1 dobeginif Xi和和Xi+1都是終結(jié)符都是終結(jié)符 then Xi = Xi

22、+1if i= n-2 且且 xi和和Xi+2都是終結(jié)符都是終結(jié)符, Xi+1為非終結(jié)符為非終結(jié)符 then Xi = Xi+2if Xi為終結(jié)符為終結(jié)符, Xi+1為非終結(jié)符為非終結(jié)符 then for firstVT中的每個(gè)元素中的每個(gè)元素a do Xi Xi+1 ;end;構(gòu)造優(yōu)先關(guān)系表算符優(yōu)先分析算法算符優(yōu)先分析算法 通過(guò)比較終結(jié)符間的優(yōu)先關(guān)系來(lái)實(shí)現(xiàn) 根據(jù)優(yōu)先分析的原理原理：語(yǔ)法分析程序的任務(wù)是：不斷移進(jìn)輸入符號(hào)，識(shí)別句柄并進(jìn)展歸約。 分析的方法分析的方法：根據(jù)優(yōu)先性“高于來(lái)識(shí)別句柄的頭，根據(jù)優(yōu)先性“低于來(lái)識(shí)別句柄的尾。各種優(yōu)先關(guān)系已經(jīng)存于優(yōu)先關(guān)系表中。 1.不能識(shí)別只由一個(gè)非終結(jié)符組

23、成的句柄。不能保證每次對(duì)句柄進(jìn)展歸約,在算符優(yōu)先分析過(guò)程中,每次歸約的符號(hào)串,是當(dāng)前句型的最左素短語(yǔ). 2.素短語(yǔ)：素短語(yǔ)：至少含有一個(gè)終結(jié)符,且除自身外,不再包含任何其它更小的素短語(yǔ)。 3.最左素短語(yǔ)最左素短語(yǔ)leftmost prime leftmost prime phrasephrase：是指位于句型最左邊的那個(gè)素短語(yǔ)。例：下述文法的一個(gè)句型： T * F + i 其短語(yǔ)、素短語(yǔ)、最左素短語(yǔ)分別是？ET | E+TTF | T*FFi | EEE + TFiTT * F短語(yǔ)有：i, T * F, T * F + i素短語(yǔ)有： i, T * F最左素短語(yǔ)是：T * F 一個(gè)算符文法一個(gè)算

24、符文法G的某個(gè)句型的最左素短語(yǔ)可描述：的某個(gè)句型的最左素短語(yǔ)可描述：設(shè)句型的一般形式為設(shè)句型的一般形式為(NiVVN N,ai VVT T#N1a1 N2a2 Nnan #它的它的最左素短語(yǔ)最左素短語(yǔ)是滿足下列條件的最左子串：是滿足下列條件的最左子串：Niai Ni+1ai+1 Njaj Nj+1其中：其中：ai-1ai, aiai+1.aj-1aj ， ajaj+1該定理說(shuō)明了最左素短語(yǔ)與周?chē)?hào)之間的關(guān)系 例:文法G E-E+T|T T-T*F|F F-E|i 句型T+T*F+i的語(yǔ)法樹(shù)如圖：EET+E+TFTT*FPi根據(jù)語(yǔ)法樹(shù)可知：句型#T+T*F+i#的短語(yǔ)短語(yǔ)有：T 相對(duì)非終結(jié)符E

25、的短語(yǔ)T*F 相對(duì)非終結(jié)符T的短語(yǔ)T+T*F 相對(duì)非終結(jié)符E的短語(yǔ)i 相對(duì)非終結(jié)符P、F、T的短語(yǔ)T+T*F+i 相對(duì)非終結(jié)符E的短語(yǔ)根據(jù)素短語(yǔ)素短語(yǔ)的定義可知： i和T*F為素短語(yǔ)。其中：T+T*F 含T*F素短語(yǔ)、 T+T*F+i 含T*F素短語(yǔ) 和 T不含終結(jié)符也不是素短語(yǔ)T*F為最左素短語(yǔ)最左素短語(yǔ)。 3.算符優(yōu)先分析過(guò)程：根據(jù)最左素短語(yǔ)的定義句型句型的一般形式: #N1a1N2a2.NnanNn+1#ai為終結(jié)符,Ni為可有可無(wú)的非終結(jié)符從左向右掃描各符號(hào),依次查看算符優(yōu)先矩陣,直至找到滿足ai ai+1的終結(jié)符為止,一直移進(jìn).再?gòu)腶i開(kāi)場(chǎng)往左掃描,直至找到滿足關(guān)系aj-1 aj的終結(jié)符為止,進(jìn)展歸約。此時(shí),形如:Nj aj Nj+1 aj+1.Ni ai Ni+1的子串即為最左素短語(yǔ)，應(yīng)被歸約。分析過(guò)程的完畢：分析棧中為#S，輸入串為# 例: E-E+T|T T-T*F|FF-E|i 把#入棧,讀一符號(hào)i, 因?yàn)? + ,所以歸約:F-i 因# + , 所以+入棧 因+ * , 所以歸約:F-i 因+ * , 所以*入棧 因* # , 所以歸約:F-i 因* # , 所以歸約:T-F*F 因+ # , 所以歸約:E-T+F 分析成功求i+i*i的算符優(yōu)先分析過(guò)