《《自下而上語(yǔ)法分析》PPT課件.ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《《自下而上語(yǔ)法分析》PPT課件.ppt（52頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、第四章(2) 自下向上語(yǔ)法分析,本章要求: 1. 掌握自下向上語(yǔ)法分析的基本思想和基本概念 2. 了解算符優(yōu)先語(yǔ)法分析；求FIRSTVT集和LASTVT集，構(gòu)造算符優(yōu)先關(guān)系表；能運(yùn)用算符優(yōu)先分析方法進(jìn)行表達(dá)式分析（選學(xué)） 3. 掌握句柄的定義與判定 4. 理解規(guī)范歸約的過(guò)程和LR分析過(guò)程中的實(shí)現(xiàn) 5. 掌握LR語(yǔ)法分析的實(shí)現(xiàn)過(guò)程,回顧: 歸約和推導(dǎo)的概念 例S aABe A Abc | b B d 用歸約的方法對(duì)句子abbcde進(jìn)行語(yǔ)法分析。,例S aABe A Abc | b B d abbcde,例S aABe A Abc | b B d abbcde aAbcde aAbcde,例S a
2、ABe A Abc | b B d abbcde aAbcde aAde,例S aABe A Abc | b B d abbcde aAbcde aAde aABe,例S aABe A Abc | b B d abbcde aAbcde aAde aABe S,例S aABe A Abc | b B d abbcde aAbcde aAde aABe S S rm aABe rm aAde rm aAbcde rm abbcde,自下而上的語(yǔ)法分析的一般過(guò)程,實(shí)現(xiàn)思想 從輸入符號(hào)串開(kāi)始，從左到右進(jìn)行掃描，將輸入符號(hào)逐個(gè)移入一個(gè)棧中，邊移入邊分析，一旦棧頂符號(hào)串形成某個(gè)產(chǎn)生式的右部時(shí)，就用該產(chǎn)生
3、式的左部非終結(jié)符代替，稱(chēng)為歸約。重復(fù)這一過(guò)程，直到歸約到棧中只剩下文法的開(kāi)始符號(hào)時(shí)，則分析成功， 稱(chēng)為“移進(jìn)-歸約”方法。 從語(yǔ)法樹(shù)的角度看：從語(yǔ)法樹(shù)的樹(shù)葉開(kāi)始，逐步向上歸約構(gòu)造分析樹(shù)，直到形成根結(jié)點(diǎn)。是推導(dǎo)的逆過(guò)程。,最左推導(dǎo)(Left-most Derive) 每次推導(dǎo)都替換當(dāng)前句型的最左邊的非終結(jié)符。 與最右歸約對(duì)應(yīng)。 最右推導(dǎo)(Right-most Derive) 每次推導(dǎo)都替換當(dāng)前句型的最右邊的非終結(jié)符。 與最左歸約(規(guī)范歸約)對(duì)應(yīng)，得規(guī)范句型。,例：設(shè)有文法GS： (1) S aABe (2) A b (3) A A
4、bc (4) B d 使用最右推導(dǎo)： 因?yàn)镾 aABe aAde aAbcde abbcde，所以 abbcde是文法G的句子。,步驟 動(dòng)作,(1)S aABe(2)A b (3)A Abc(4)B d,最左歸約過(guò)程是最右推導(dǎo)的逆過(guò)程， 對(duì)輸入串a(chǎn)bbcde的移進(jìn)歸約過(guò)程如下：,該分析過(guò)程反復(fù)執(zhí)行“移進(jìn)”和“歸約”兩個(gè)動(dòng)作，直到棧中只有開(kāi)始符號(hào)為止。,a,b a,A a,b A a,c b A a,A a,d A a,B A a,e B A a,S,“移進(jìn)-歸約”分析法中棧的使用,移進(jìn)-歸約分析器使用了一個(gè)符號(hào)棧和一個(gè)輸入緩沖區(qū) 1、句型表示,符號(hào)棧內(nèi)容 + 輸入
5、緩沖區(qū)內(nèi)容 # 當(dāng)前句型 #,2、分析器結(jié)構(gòu),3. 過(guò)程描述：do do 將輸入串最左邊的符號(hào)移入棧內(nèi); while (在棧里符號(hào)串中找到一個(gè)可歸約串)； 歸約可歸約串 while （文法開(kāi)始符號(hào)出現(xiàn)在棧頂或者發(fā)現(xiàn)錯(cuò)誤）；,分析成功的條件：棧頂為文法符號(hào)，輸入串為空。 注意：該過(guò)程并未涉及如何在棧里找可歸約串。實(shí)際上，不同的找可歸約串的方法，構(gòu)成了不同的分析算法。,分析器的四種動(dòng)作,1) 移進(jìn)：讀入下一個(gè)輸入符號(hào)并把它下推進(jìn)棧。 2) 歸約：當(dāng)棧頂符號(hào)串形成一個(gè)可歸約的串（如：句柄）時(shí)，直接進(jìn)行歸約，即用產(chǎn)生式左側(cè)的非終結(jié)符替換棧頂?shù)木浔?3) 接受：當(dāng)棧底只有“#”和開(kāi)始符號(hào)，而輸
6、入也已經(jīng)到達(dá)右端標(biāo)志符號(hào)“#”時(shí)，識(shí)別出符號(hào)串是句子，執(zhí)行該動(dòng)作，表示分析成功，是歸約的一種特殊情況。 4) 出錯(cuò)：棧頂?shù)膬?nèi)容與輸入符號(hào)相悖，即當(dāng)識(shí)別程序發(fā)現(xiàn)輸入符號(hào)串不是句子時(shí)，進(jìn)行出錯(cuò)處理。 注意：決定移進(jìn)和歸約的依據(jù)是什么？ 棧頂是否出現(xiàn)了可歸約的符號(hào)串。,“移進(jìn)歸約”語(yǔ)法分析小結(jié)： 從輸入串的開(kāi)始依次讀入單詞(移進(jìn)棧中) 。 一旦發(fā)現(xiàn)可歸約串(某個(gè)產(chǎn)生式的右端)就立即歸約。 歸約就是將棧頂?shù)囊淮?hào)用文法產(chǎn)生式的左部代替，歸約可能重復(fù)多次，然后繼續(xù)移進(jìn)。 若最終能歸約成文法的開(kāi)始符號(hào)，則分析成功（接受）；否則出錯(cuò)。 由于總是將句型的最左邊的可歸約串替換成非終結(jié)符，該方法通常得到是最右推
7、導(dǎo)。 關(guān)鍵是如何識(shí)別可歸約的符號(hào)串？,語(yǔ)法分析中問(wèn)題的提出： 在構(gòu)造語(yǔ)法樹(shù)的過(guò)程中，何時(shí)歸約？ 當(dāng)可歸約串出現(xiàn)在棧頂時(shí)就進(jìn)行歸約。 如何知道在棧頂符號(hào)串中已經(jīng)形成可歸約串？ 如何進(jìn)行歸約？ 通過(guò)不同的自底向上的分析算法來(lái)解釋?zhuān)煌乃惴▽?duì)可歸約串的定義是不同的，但分析過(guò)程都有一個(gè)共同的特點(diǎn)：邊移進(jìn)邊歸約。,自下而上語(yǔ)法分析主要有以下三種方法： 簡(jiǎn)單優(yōu)先分析法(規(guī)范歸約)文法按 一定原則規(guī)定文法符號(hào)的優(yōu)先關(guān)系 算符優(yōu)先分析法(不規(guī)范歸約)規(guī)定 算符之間的優(yōu)先關(guān)系 LR分析法（規(guī)范歸約） LR(0)、LR(1)、SLR(1)和LALR(1),語(yǔ)法分析樹(shù)的生成演示,a b b c d e
8、,A,A,B,S,,,,,,,,,Ab,AAbc,Bd,SaABe,(1)S aABe(2)A b (3)A Abc(4)B d,,S aABe aAde aAbcde abbcde,規(guī)范歸約相關(guān)概念復(fù)習(xí),有文法G，開(kāi)始符號(hào)為S, 如果有S=xy,則xy是文法G的句型，x,y是任意的符號(hào)串 如果有S=xAy, 且有A=,則是句型xy相對(duì)于非終結(jié)符A的短語(yǔ) 如果有S=xAy, 且有A-,則是句型xy相對(duì)于A-的直接短語(yǔ) 位于一個(gè)句型最左邊的直接短語(yǔ)稱(chēng)為句柄. 句型--- 短語(yǔ) --- 直接短語(yǔ) ---句柄,注: 每次歸約的部分就是分析為句柄的字符串(最右推導(dǎo))。 在規(guī)范歸約中，關(guān)鍵問(wèn)題就轉(zhuǎn)化為如
9、何識(shí)別句柄?,回到上例用句柄對(duì)句子abbcde進(jìn)行歸約有：,用句柄對(duì)句子進(jìn)行歸約的過(guò)程與用移進(jìn)-歸約過(guò)程是一致的，使用歸約的產(chǎn)生式及其順序是一致的。,(1)S aABe(2)A b (3)A Abc(4)B d,(2) Ab,(3)A Abc,aAbcde,aAde,(4)B d,(1)S aABe,aABe,S,,,,,練習(xí)：有文法如下 E-E+T|T T-T*F|F F-(E)|id 1）寫(xiě)出輸入串 id1+id2*id3 的規(guī)范歸約過(guò)程； 2）給出該文法“移進(jìn)-歸約”語(yǔ)法分析的過(guò)程。,E=E+T =E+T*F =E+T*id =E+F*id =E+id*id =T+id*id =F+id
10、*id =id+id*id,動(dòng)作 棧 輸入緩沖區(qū) 1) 準(zhǔn)備 # id1+id2*id3# 2) 移進(jìn) #id1 +id2*id3# 3) 歸約 Fid #F +id2*id3# 4) 歸約 TF #T +id2*id3# 5) 歸約 ET #E +id2*id3# 6) 移進(jìn) #E+ id2*id3# 7) 移進(jìn) #E+id2 *id3# 8) 歸約 Fid #E+F *id3# 9) 歸約 TF #E+T *id3# 10) 移進(jìn) #E+T* id3# 11) 移進(jìn) #E+T*id3 # 12) 歸約 Fid #E+T*F
11、 # 13) 歸約 TT*F #E+T # 14) 歸約 EE+T #E # 15) 接受,,,,,,,,,,所得的結(jié)果是：用產(chǎn)生式序列表示語(yǔ)法分析樹(shù),E-E+T|T T-T*F|F F-(E)|id,id1 + id2 * id3,F,,T,,E,F,,T,F,T,E,移進(jìn)歸約分析中的問(wèn)題,1) 移進(jìn)-歸約沖突 在分析到某一步時(shí)，既可以移進(jìn)，又可以歸約 上例第10)步可以移進(jìn)*，也可以按產(chǎn)生式EE+T進(jìn)行歸約。 2) 歸約-歸約沖突 存在兩個(gè)可選的句柄，可對(duì)棧頂符號(hào)進(jìn)行歸約 例如上述第13)步，可以用TF進(jìn)行歸約，又可以按TT*F進(jìn)行歸約。 各種分析方法中處理沖突的技術(shù)不同,
12、算符優(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) 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...(
13、P,Q,R屬于非終結(jié)符),則G是一個(gè)算符文法。 2.算符優(yōu)先關(guān)系的定義(自底向上,可通過(guò)樹(shù)形結(jié)構(gòu)觀(guān)察) a b,G中有P-...ab...或P-...aQb... (在同一產(chǎn)生式中)a b,G中有P-...aR...的產(chǎn)生式,且R=b...或R=Qb... (注意ab相鄰)a b,G中有P-...Rb...的產(chǎn)生式,且R=...a或R=...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)先文法
14、 算符文法G的任何終結(jié)符a,b之間要么沒(méi)有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系,至多有 = , 中的一種成立,則G為一算符優(yōu)先文法。,算符優(yōu)先關(guān)系表的構(gòu)造,用表格形式來(lái)表示各終結(jié)符號(hào)的優(yōu)先關(guān)系，這種表稱(chēng)為優(yōu)先表。 構(gòu)造優(yōu)先關(guān)系表的方法： 按照定義手工計(jì)算 使用算法,由F-(E) 得 ( = ),例: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
15、相鄰。 a,b之間未必有優(yōu)先關(guān)系( , , ),算符優(yōu)先關(guān)系表的構(gòu)造算法,1.FIRSTVT集 定義：對(duì)每個(gè)非終結(jié)符P, FIRSTVT(P)=a|P=a...或P=Qa...,a為終結(jié)符,P，Q為非終結(jié)符,由優(yōu)先性低于的定義和FIRSTVT集合的定義可以得出： 若存在某個(gè)產(chǎn)生式：aP，對(duì)所有：bfirstVT(P) 都有：a < b。,構(gòu)造FIRSTVT集算法:,按照下面兩條規(guī)則來(lái)構(gòu)造FIRSTVT集： 若有產(chǎn)生式P-a...或P-Qa...,則aFIRSTVT(P) 若有產(chǎn)生式P-R...,則FIRSTVT(R)包含在FIRSTVT(P)中,所有終結(jié)符,所有非終結(jié)符,數(shù)組值為真假，為真的
16、條件是c FIRSTVT(Q),通過(guò)構(gòu)造一個(gè)二維數(shù)組F來(lái)實(shí)現(xiàn),該從數(shù)組F反映任何一個(gè)非終結(jié)符P的FIRSRVT集中的元素。步驟：,先用第一條規(guī)則進(jìn)行初始化,使用第二條規(guī)則對(duì)數(shù)組F進(jìn)行修改，修改方法是： (1) 用一個(gè)棧，將所有F數(shù)組中值為真的元素FP,a的符號(hào)對(duì)(P,a)壓入堆棧； (2) 對(duì)棧施行如下操作：若棧不空，將棧頂符號(hào)對(duì)出棧，記為(Q,a)，檢查所有的產(chǎn)生式，若有形為：PQ的產(chǎn)生式，且FP,a為假，則使FP,a為真，且將(P,a)壓入堆棧； (3) 重復(fù)這一過(guò)程，直到棧空,求文法各非終結(jié)符的firstVT：,定義數(shù)組：,EE+T | TTT*F | FF(E) | i,從而得到： F
17、irstVT(E) = +, *,(, I FirstVT(T) = *,(,I FirstVT(F) = (,I,Begin For 對(duì)每個(gè)非終結(jié)符P和終結(jié)符a do FP,a = false For 對(duì)每個(gè)形如Pa或PQa的產(chǎn)生式 do Insert(P,a) While stack 非空 Begin 把棧頂項(xiàng)出棧，記為(Q,a) For 對(duì)每條形如PQ的產(chǎn)生式 do insert(P,a) End; End.,PROCEDURE insert(P,a); IF not FP,a then begin fp,a = true; (P,a)進(jìn)棧 end;,對(duì)數(shù)組初始化,應(yīng)用規(guī)則1,應(yīng)用規(guī)
18、則2,2. 求LASTVT集 定義：LASTVT(P)=a|P = ...a或P =... aQ,a為終結(jié)符,P，Q為非終結(jié)符,+,+,構(gòu)造LASTVT集算法: (思考？),3.構(gòu)造優(yōu)先關(guān)系表 如果每個(gè)非終結(jié)符的FIRSTVT和LASTVT集均已知,則可構(gòu)造優(yōu)先關(guān)系表。 若產(chǎn)生式右部有...aP...的形式,則對(duì)于每個(gè)bFIRSTVT(P)都有a b(優(yōu)先集) 若產(chǎn)生式右部有...Pb的形式,則對(duì)于每個(gè)aLASTVT(P)集,都有a b 若產(chǎn)生是形如：Aab 或 AaBb形式，則有a b 構(gòu)造優(yōu)先關(guān)系表的算法如下：,For 每條形如PX1X2Xn的產(chǎn)生式 do for i =1 to n-1
19、 do begin if Xi和Xi+1都是終結(jié)符 then Xi = Xi+1 if i Xi+1 ; end;,構(gòu)造優(yōu)先關(guān)系表,算符優(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é)符組成的句柄。不能保證每次對(duì)句柄進(jìn)行歸約,在算符優(yōu)先分析過(guò)程中,每次歸約的符號(hào)串,是當(dāng)前句型的最左素短語(yǔ). 2.素短語(yǔ)：至少含有一個(gè)終結(jié)符,且除自身外,不再包含任何其它更小的素短語(yǔ)。 3.最左
20、素短語(yǔ)(leftmost prime phrase)：是指位于句型最左邊的那個(gè)素短語(yǔ)。,例：下述文法的一個(gè)句型： T * F + i 其短語(yǔ)、素短語(yǔ)、最左素短語(yǔ)分別是？,ET | E+T TF | T*F Fi | (E),短語(yǔ)有：i, T * F, T * F + i 素短語(yǔ)有： i, T * F 最左素短語(yǔ)是：T * F,,一個(gè)算符文法G的某個(gè)句型的最左素短語(yǔ)可描述： 設(shè)句型的一般形式為(NiVN,ai VT #N1a1 N2a2 Nnan # 它的最左素短語(yǔ)是滿(mǎn)足下列條件的最左子串： Niai Ni+1ai+1 Njaj Nj+1 其中：ai-1ai,, aiai+1..aj-1aj
21、， 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ù)如圖：,根據(jù)語(yǔ)法樹(shù)可知： 句型#T+T*F+i#的短語(yǔ)有： T 相對(duì)非終結(jié)符E的短語(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ǔ)的定義可知： i和T*F為素短語(yǔ)。 其中：T+T*F (含T*F素短語(yǔ))、 T+T*F+i (含T*F素短語(yǔ)) 和 T(不含終結(jié)符)也不是素短語(yǔ) T*F為最左素短語(yǔ)。,3.算符優(yōu)先分析過(guò)程：(根據(jù)最左素短語(yǔ)
22、的定義) 句型的一般形式: #N1a1N2a2...NnanNn+1#(ai為終結(jié)符,Ni為可有可無(wú)的非終結(jié)符) 從左向右掃描各符號(hào),依次查看算符優(yōu)先矩陣,直至找到滿(mǎn)足ai ai+1的終結(jié)符為止,一直移進(jìn).再?gòu)腶i開(kāi)始往左掃描,直至找到滿(mǎn)足關(guān)系aj-1 aj的終結(jié)符為止,進(jìn)行歸約。 此時(shí),形如:Nj aj Nj+1 aj+1.....Ni ai Ni+1的子串即為最左素短語(yǔ)，應(yīng)被歸約。 分析過(guò)程的結(jié)束：分析棧中為#S，輸入串為#,例: E-E+T|T T-T*F|FF-(E)|i 把#入棧,讀一符號(hào)i, 因?yàn)? + ,所以歸約:F-i 因# * , 所以歸約:F-i 因+ # , 所以歸約:
23、F-i 因* # , 所以歸約:T-F*F 因+ # , 所以歸約:E-T+F 分析成功,求i+i*i的算符優(yōu)先分析過(guò)程,棧 輸入緩沖區(qū) # i+i*i# #i +i*i# #F +i*i# #F+ i*i# #F+i *i# #F+F *i# #F+F* i# #F+F*i # #F+F*F # #F+T # #E #,k:=1;sk = #; Repeat a := 下一個(gè)輸入符號(hào); If sk Vt THEN j:=k ELSE j:=k-1; WHILE sj a DO BEGIN repeat q:=sj;
24、if sj-1 Vt THEN j:=j-1 else j:=j-2; UNTIL sj < q; 把sj+1.sk歸約為某個(gè)N； k:=j+1; sk := N; END If sj < a or sj = a THEN begin k:=k+1; sk:=a; end; else error; UNTIL a=#;,算符優(yōu)先分析一般并不等價(jià)于規(guī)范規(guī)約 并不對(duì)文法的非終結(jié)符定義優(yōu)先關(guān)系，無(wú)法發(fā)現(xiàn)由單個(gè)非終結(jié)符組成的“可歸約串”。即無(wú)法使用單非產(chǎn)生式(如：TF)進(jìn)行歸約。 算符優(yōu)先分析比規(guī)范歸約過(guò)程要快，跳過(guò)了所有的單非產(chǎn)生式。 可能將本來(lái)不是句子的輸入串誤認(rèn)為是句子。,總結(jié)歸約的策略: 在文法中尋找這樣的產(chǎn)生式:它的右部形如:uj aj uj+1 aj+1... ui ai ui+1,其中每個(gè)終結(jié)符號(hào)與最左素短語(yǔ)對(duì)應(yīng)位置上的終結(jié)符號(hào)完全相同,而每一個(gè)非終結(jié)符號(hào)uk應(yīng)與相應(yīng)位置上的非終結(jié)符號(hào)Nk相對(duì)應(yīng),不必完全相同。,算符優(yōu)先分析法小結(jié),優(yōu)點(diǎn) 簡(jiǎn)單、效率高 能夠處理部分二義性文法 缺點(diǎn) 文法書(shū)寫(xiě)限制大 占用內(nèi)存空間大 不規(guī)范、存在查不到的語(yǔ)法錯(cuò)誤,設(shè)文法為： E#E# TF EE+T FPF|P ET P（E ） TT*F PI 求算符優(yōu)先關(guān)系表。(分析過(guò)程見(jiàn)呂映芝課本),練習(xí),
《自下而上語(yǔ)法分析》PPT課件.ppt
