自下而上語(yǔ)法分析課件

1、1第五章 語(yǔ)法分析自下而上分析 5.1 自下而上分析基本問(wèn)題5.2 算符優(yōu)先分析5.3 LR分析法5.4 語(yǔ)法分析器的自動(dòng)產(chǎn)生工具YACC（略）25.1 自下而上分析基本問(wèn)題一、歸約1.“移進(jìn)規(guī)約”的思想： 用一個(gè)寄存符號(hào)的先進(jìn)后出棧，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的一個(gè)候選式時(shí)，即把棧頂?shù)倪@一部分替換成（歸約為）該產(chǎn)生式的左部符號(hào)。3舉例：已知文法G為(1)SaAcBe (2)Ab (3)AAb (4)Bd 及輸入串a(chǎn)bbcde歸約過(guò)程如下:eBcAa進(jìn)9BcAa歸8dcAa進(jìn)7cAa進(jìn)6bAa進(jìn)4Aa歸5Aa歸3ba進(jìn)2S歸10a進(jìn)1動(dòng)作:步驟:5.1 自下而上分析基本

2、問(wèn)題42.自下而上分析的關(guān)鍵:“可歸約串”如何精確定義？“可歸約串”的不同定義，形成了不同的自下而上的分析方法。從上例的步驟（）可發(fā)現(xiàn)5.1 自下而上分析基本問(wèn)題“算符優(yōu)先分析”中：“最左素短語(yǔ)”“可歸約串”“規(guī)范歸約分析”中：“句柄”“可歸約串”例：5.自下而上分析的中心問(wèn)題： 怎樣判斷棧頂?shù)姆?hào)串的可歸約性以及如何歸約。5.1 自下而上分析基本問(wèn)題各種自下而上分析法的共同特點(diǎn)： 邊輸入單詞符號(hào)（移進(jìn)符號(hào)棧），邊歸約。即：在從左到右移進(jìn)輸入串的過(guò)程中，一旦發(fā)現(xiàn)棧頂呈現(xiàn)可歸約串就立即進(jìn)行歸約。6二.規(guī)范歸約簡(jiǎn)述5.1 自下而上分析基本問(wèn)題(1)短語(yǔ):若且,則稱(chēng)是句型相對(duì)于 非終結(jié)符的短語(yǔ)。*

3、+(2)直接短語(yǔ):若，則稱(chēng)是句型相對(duì)于規(guī)則 的直接短語(yǔ)。(3)句柄：一個(gè)句型的最左直接短語(yǔ)成為該句型的句柄。.定義：令是一個(gè)文法，是的開(kāi)始符號(hào)， 假定是文法的一個(gè)句型， 即 *75.1 自下而上分析基本問(wèn)題規(guī)范規(guī)約中的概念短語(yǔ)：直接短語(yǔ)：句柄：是句型的短語(yǔ)僅當(dāng) S A 且A S.A.A =最左直接短語(yǔ)8例1：EE+T | TTT*F | FF(E) | i i1*i2+i3短語(yǔ)：直接短語(yǔ)：句柄： i1，i2，i3，i1*i2，i1*i2+i3 i1，i2，i3i19練習(xí)：EE+T | TTT*F | FF(E) | i E+T*F+i 短語(yǔ)：直接短語(yǔ)：句柄： E+T*F+i, E+T*F, T

4、*F, i T*F, i T*FEETETTFFi+*10例2：利用句柄對(duì)句子進(jìn)行歸約5.1 自下而上分析基本問(wèn)題句型歸約規(guī)則aAbcdeaAcdeaAcBeS對(duì)文法(1)SaAcBe; (2)Ab; (3)AAb; (4)Bd 的句子abbcde進(jìn)行歸約。 abbcde(2)Ab(3)AAb(4)Bd(1)SaAcBe112.規(guī)范歸約規(guī)范歸約是關(guān)于的一個(gè)最右推導(dǎo)的逆過(guò)程.5.1 自下而上分析基本問(wèn)題例: S aAcBe aAcde aAbcde abbcde (1) (2) (3) (4)(1)定義:設(shè)是文法G的一個(gè)句子,我們稱(chēng)序列n, n-1,0 是的一個(gè)規(guī)范歸約,若此序列滿足:n=;0=

5、S，S為文法開(kāi)始符號(hào);對(duì)任何i,0in, i-1是經(jīng)把i的句柄替換為相應(yīng)產(chǎn)生式的左部符號(hào)而得到的.12(2)規(guī)范推導(dǎo):即最右推導(dǎo).5.1 自下而上分析基本問(wèn)題 規(guī)范句型:由規(guī)范推導(dǎo)所得到的句型,稱(chēng)為規(guī)范句型. 若文法G是無(wú)二義的,則規(guī)范推導(dǎo)(最右推導(dǎo))的逆過(guò)程必是規(guī)范歸約(最左歸約)。(3)規(guī)范歸約的實(shí)質(zhì):在移進(jìn)過(guò)程中，當(dāng)發(fā)現(xiàn)棧頂呈現(xiàn)句柄時(shí)， 就用相應(yīng)產(chǎn)生式的左部符號(hào)進(jìn)行替換。2.規(guī)范歸約規(guī)范歸約的中心問(wèn)題：如何尋找或確定一個(gè)句型的句柄。給出了尋找句柄的不同算法就給出了不同的規(guī)范歸約方法。13三、符號(hào)棧的使用1.與LL(1)方法區(qū)別：符號(hào)棧輸入串開(kāi)始#W#分析成功#S#符號(hào)棧輸入串開(kāi)始#SW#

6、分析成功#LL(1)分析:5.1 自下而上分析基本問(wèn)題142.舉例：規(guī)范歸約（課本88頁(yè)例5.3） 語(yǔ)法分析對(duì)符號(hào)棧的使用有四類(lèi)操作：5.1 自下而上分析基本問(wèn)題“移進(jìn)”指把輸入串的一個(gè)符號(hào)移進(jìn)棧.“歸約”指發(fā)現(xiàn)棧頂呈可規(guī)約串,并用適當(dāng)?shù)南鄳?yīng)符號(hào)去 替換這個(gè)串.“接受”指宣布最終分析成功.“出錯(cuò)處理” 指發(fā)現(xiàn)棧頂?shù)膬?nèi)容與輸入串相悖,分析工 作無(wú)法正常進(jìn)行,此時(shí)需調(diào)用出錯(cuò)處理程序.15例2：有文法：E-E+T|TT-T*F|FF-(E)|i對(duì)輸入串 i1+i2*i3 的規(guī)范規(guī)約過(guò)程：16 動(dòng)作 棧 輸入緩沖區(qū)1) 準(zhǔn)備 # i1+i2*i3#2) 移進(jìn) #i1 +i2*i3#3) 歸約 Fi #

7、F +i2*i3#4) 歸約 TF #T +i2*i3# 5) 歸約 ET #E +i2*i3#6) 移進(jìn) #E+ i2*i3#7) 移進(jìn) #E+i2 *i3#8) 歸約 Fi #E+F *i3#9) 歸約 TF #E+T *i3# 10) 移進(jìn) #E+T* i3#11) 移進(jìn) #E+T*i3 #12) 歸約 Fi #E+T*F #13) 歸約 TT*F #E+T #14) 歸約 EE+T #E # 15) 接受所得的結(jié)果是：用產(chǎn)生式序列表示語(yǔ)法分析樹(shù)E-E+T|TT-T*F|FF-(E)|ii1 + i2 * i3FTEFTFTE175.2 算符優(yōu)先分析算符優(yōu)先分析： 不是一種規(guī)范歸約法，是

8、一種自下而上的語(yǔ)法分析法，關(guān)鍵在于規(guī)定算符（即終結(jié)符）之間的優(yōu)先順序和結(jié)合性質(zhì)，借助這種優(yōu)先關(guān)系尋找“可歸約串”進(jìn)行歸約。特點(diǎn)：有利于表達(dá)式分析，宜于手工實(shí)現(xiàn)。18一、算符優(yōu)先文法及優(yōu)先表構(gòu)造1.算符優(yōu)先文法算符文法:一個(gè)文法，如果它的任一產(chǎn)生式的右部都不含 兩個(gè)相繼（并列）的非終結(jié)符，即不含如下形 式的產(chǎn)生式右部：則我們稱(chēng)該文法為算符文法。5.2 算符優(yōu)先分析19算符優(yōu)先文法:如果一個(gè)算符文法G中的任何終結(jié)符對(duì)(a,b) 至多只滿足下述三關(guān)系之一: a b，a b，a b 則稱(chēng)G是一個(gè)算符優(yōu)先文法。 假定是一個(gè)不含-產(chǎn)生式的算符文法。對(duì)于任何一對(duì)終結(jié)符a、b，我們說(shuō)： a b當(dāng)且僅當(dāng) 文法G

9、中含有形如 Pab或aQb的產(chǎn)生式；5.2 算符優(yōu)先分析+ (2) a b當(dāng)且僅當(dāng) G中含有形如 PaR 的產(chǎn)生式, 而Rb或R Qb;+ (3) a b當(dāng)且僅當(dāng) G中含有形如 PRb的產(chǎn)生式, 而R a或R aQ 。+ + FIRSTVT(R)LASTVT(R)20按定義,我們用以下兩條規(guī)則構(gòu)造集合FIRSTVT(P):(1)若有產(chǎn)生式Pa或PQa, 則aFIRSTVT(P);(2)若aFIRSTVT(Q), 且有產(chǎn)生式PQ, 則aFIRSTVT(P)。返回 5.2 算符優(yōu)先分析構(gòu)造集合FIRSTVT(P):構(gòu)造集合LASTVT(P):按定義,我們用以下兩條規(guī)則構(gòu)造集合LASTVT(P):(

10、1)若有產(chǎn)生式Pa或PaQ, 則aLASTVT(P);(2)若aLASTVT(Q), 且有產(chǎn)生式PQ, 則aLASTVT(P)。215.2 算符優(yōu)先分析文法G：(1)EE+T|T (2)TT*F|F (3)FPF|P (4)P(E)|iFIRSTVT(E)=FIRSTVT(T)=FIRSTVT(F)=FIRSTVT(P)=+, *, , (,i (,i ,(,i *,(,i LASTVT(E)=LASTVT(T)=LASTVT(F)=LASTVT(P)= ),i +, *, , ),i ,),i *,),i 22（1）a b：找出滿足“ ”的所有終結(jié)符對(duì)。(借助于FIRSTVT(P)和LAST

11、VT(P)實(shí)現(xiàn))5.2 算符優(yōu)先分析2.構(gòu)造優(yōu)先表（3）構(gòu)造出優(yōu)先表（2）ab，ab：找出滿足“”和“”的所有終結(jié)符對(duì)。ab: 有形如aP的候選,且bFIRSTVT(P)；ab: 有形如Pb的候選,且aLASTVT(P)。23另:“”是作為語(yǔ)句的起始和結(jié)束標(biāo)記,認(rèn)為存在候選式： #開(kāi)始符號(hào)#（1）#=#（2）#5.2 算符優(yōu)先分析24例:優(yōu)先關(guān)系和優(yōu)先表考慮文法G：(1)EE+T|T (2)TT*F|F (3)FPF|P (4)P(E)|i5.2 算符優(yōu)先分析FIRSTVT(E)=FIRSTVT(T)=FIRSTVT(F)=FIRSTVT(P)=+, *, , (,i (,i ,(,i *,(

12、,i LASTVT(E)=LASTVT(T)=LASTVT(F)=LASTVT(P)= ),i +, *, , ),i ,),i *,),i 25按定義,我們可得文法G終結(jié)符對(duì)的優(yōu)先關(guān)系表,如下所示:+*i()#+*i()# (1)EE+T|T (2)TT*F|F (3)FPF|P (4)P(E)|i26返回按定義,我們可得文法G終結(jié)符對(duì)的優(yōu)先關(guān)系表,如下所示:+*i()#+*i()#對(duì)于G的任何終結(jié)對(duì)(a,b),至多只有一種關(guān)系成立。 因此，G是一個(gè)算符優(yōu)先文法。27二、算符優(yōu)先分析算法1.最左素短語(yǔ) 素短語(yǔ):是指這樣的一個(gè)短語(yǔ),它至少含有一個(gè)終結(jié)符,并且, 除它自身之外不再含任何更小的素短

13、語(yǔ)。 最左素短語(yǔ)：指處于句型最左邊的那個(gè)素短語(yǔ)。5.2 算符優(yōu)先分析28練習(xí)：EE+T | TTT*F | FF(E) | i 練習(xí)：(1)EE+T|T(2)TT*F|F(3)FPF|P(4)P(E)|i29一個(gè)算符優(yōu)先文法G的任何句型的最左素短語(yǔ)是滿足 如下條件的最左子串：NjajNiaiNi+15.2 算符優(yōu)先分析aj-1 ajaj aj+1, ,ai-1 aiai ai+1句型的一般形式：#N1a1N2a2 aj-1 NjajNiaiNi+1ai+1 NnanNn+1#N1a1N2a2 aj-1 ai+1 NnanNn+1#302.算法 過(guò)程：讀入一個(gè)輸入符號(hào)a, 然后比較棧頂終結(jié)符a。

14、Si存放“文法符號(hào)”的分析棧始終指向VT符號(hào)始終指向棧頂存放“輸入符號(hào)”的字符變量用于存放待比較的終結(jié)符號(hào)：j5.2 算符優(yōu)先分析31K:=1; SK:=#; REPEAT 把下一個(gè)輸入符號(hào)讀進(jìn)a中； IF SkVT THEN j:=k ELSE j:=k-1;WHILE Sja DO BEGIN REPEAT Q:=Sj; IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q; 把 Sj+1Sk歸約為某個(gè)N； k:=j+1; Sk:=N END OF WHILE; IF Sj a OR Sja THEN BEGIN k:=k+1; Sk:=a END EL

15、SE ERROR;UNTIL a=#aj-1 aj aj+1,ai-1 ai ai+1Sj Q Sk=Q a32REPEATQ:=S j;IF Sj-1 VT THEN j:=j-1 ELSE j:=j-2UNTIL Sj Q使得Q不斷向左移,指向新終結(jié)符使得j指向VT左符號(hào)Sj與右符號(hào)Q之間還可能滿足:Sj Q 不可能出現(xiàn),若成立則前面已經(jīng)歸約過(guò)了;Sj Q 此時(shí),符合“最左素短語(yǔ)” 定義,一直repeat;S j與Q無(wú)優(yōu)先關(guān)系不可能出現(xiàn), 若成立則前面已經(jīng)報(bào)告“Error”5.2 算符優(yōu)先分析335.2 算符優(yōu)先分析+*i()#+*i()#步驟分析棧剩余輸入串動(dòng)作 1 # i+i*ii #

16、 2 #i +i*ii # 移進(jìn) #*R=RS A a B a=*R=RbFirst( a)b, a71(2)GO(I,X) = CLOSURE(J)AX, a IAX, a J72例：(0)SS(1)SBB (2)BaB(3)BbLR(1)項(xiàng)目集規(guī)范族：I0:SS, # S BB , B aB, B b,#a/ba/bI1:SS , #I2:S BB ,# B aB, B b,#I3: Ba B,a/b B aB, B b,a/ba/bI4: B b , a/bI5:S BB ,#I6: Ba B,# B aB, B b,#I7: B b , #I8: Ba B ,a/bI9: Ba B ,

17、#73狀態(tài)ACTIONGOTOab#SB012345678974練習(xí)：若有文法GS:SS;M|MMMbD|DDD(S)|（1）證明GS是SLR文法，并構(gòu)造它的分析表；（2）給出GS的LR(1)項(xiàng)目集規(guī)范族中的I0。75五、LALR分析表的構(gòu)造同心集的合并：76同心集的合并 不會(huì)產(chǎn)生新的移進(jìn)-歸約沖突 但會(huì)產(chǎn)生新的歸約-歸約沖突A , aB , bA , bB , aA , a/bB , b/b77五、LALR分析表的構(gòu)造1、SLRLR(1)LALR(1)之間的關(guān)系LALR(1)一種折衷的方法對(duì)于同一個(gè)文法,LALR分析表永遠(yuǎn)具有相同數(shù)目的狀態(tài)5.3 L分析法782、同義集合并 (1)同心集:若

18、兩個(gè)LR(1)項(xiàng)目集,除去搜索符外,這兩 個(gè)集合相同,則稱(chēng)它們是同心集 (2)引出的問(wèn)題 A.同心集合并不會(huì)產(chǎn)生“移進(jìn)歸約”沖突 證明:(反證)假設(shè)合并后才存在“移進(jìn)歸約”沖突,則:對(duì)當(dāng)前輸入符號(hào)a,項(xiàng)目A ,a要求歸約 項(xiàng)目Ba ,b要求移進(jìn)既然兩項(xiàng)目處于合并后的一個(gè)集合中,則:合并前,必c、d,使得A ,a與Ba ,b 已同處于某一集合中。即合并前,已有LR(1)項(xiàng)目集 存在“移進(jìn)歸約”沖突故同心集合并不會(huì)產(chǎn)生“移進(jìn)歸約”沖突 B.同心集合并會(huì)產(chǎn)生“歸約歸約”沖突5.3 L分析法79例:考慮文法(0)SS(1)SaAd|bBd|aBe|bAe(2)Ac(3)Bc項(xiàng)目集:Ac ,d,Bc ,e Ac ,e,Bc ,d(合并)Ac ,d/e,Bc ,d/e問(wèn)題:面臨a=d/e時(shí),采用哪一個(gè)歸約?5.3 L分析法803、構(gòu)造LALR(1)分析表的步驟:(1)文法拓廣: