編譯原理自下而上語法分析.ppt

《編譯原理自下而上語法分析.ppt》由會員分享，可在線閱讀，更多相關(guān)《編譯原理自下而上語法分析.ppt（36頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、自下而上語法分析,掌握自底相上分析的基本思想，基本概念 掌握算符優(yōu)先關(guān)系的判定，求FIRSTVT集,LASTVT集,構(gòu)造算符優(yōu)先關(guān)系表，能運(yùn)用算符優(yōu)先分析方法進(jìn)行表達(dá)式分析 掌握最左素短語、句柄的定義與判定 理解規(guī)范規(guī)約與算符優(yōu)先歸約的區(qū)別 LR(0)和SLR文法的理解,自下而上的語法分析,實(shí)現(xiàn)思想 從輸入符號串開始，從左到右進(jìn)行掃描，將輸入符號逐個(gè)移入一個(gè)棧中，邊移入邊分析，一旦棧頂符號串形成某個(gè)產(chǎn)生式的右部時(shí)，就用該產(chǎn)生式的左部非終結(jié)符代替，稱為歸約。重復(fù)這一過程，直到歸約到棧中只剩下文法的開始符號時(shí)，則分析成功， 稱為“移進(jìn)-歸約”方法。 從語法樹的角度看：從語法樹的樹葉開始，逐步向上歸

2、約構(gòu)造分析樹，直到形成根結(jié)。是推導(dǎo)的逆過程。 核心 尋找可歸約串(這是關(guān)鍵)進(jìn)行規(guī)約。用不同的方法尋找可歸約串，就可獲得不同的分析方法。,最左推導(dǎo)(Left-most Derive) 每次推導(dǎo)都替換當(dāng)前句型的最左邊的非終結(jié)符。 與最右歸約對應(yīng) 最右推導(dǎo)(Right-most Derive) 每次推導(dǎo)都替換當(dāng)前句型的最右邊的非終結(jié)符。 與最左歸約(規(guī)范歸約)對應(yīng)，得規(guī)范句型,例：設(shè)有文法GS： (1) S aAcBe (2) A b (3) A Ab (4) B d 使用最右推導(dǎo)： 因?yàn)镾= aAcBe=

3、 aAcde= aAbcde= abbcde， 所以 abbcde是文法G的句子。,步驟 動作,(1)S aAcBe(2)A b (3)A Ab(4)B d,最左歸約過程是最右推導(dǎo)的逆過程， 對輸入串a(chǎn)bbcde的歸約過程如下：,該分析過程反復(fù)執(zhí)行“移進(jìn)”和“歸約”兩個(gè)動作，直到棧中只有開始符號為止。,a,b a,A a,b A a,A a,c A a,d c A a,B c A a,e B c A a,S,語法分析樹的生成演示,a b b c d e,A,A,B,S,,,,,,,,,,Ab,AAb,Bd,SaAcBe,(1)S aAcBe(2)A b (3)A Ab(4)B d,這

4、種分析過程具有如下特點(diǎn)： 從輸入串的開始依次讀入單詞(移進(jìn)棧中) 。 一旦發(fā)現(xiàn)可歸約串(某個(gè)產(chǎn)生式的右端)就立即歸約。 歸約就是將棧頂?shù)囊淮栍梦姆óa(chǎn)生式的左部代替，歸約可能重復(fù)多次，然后繼續(xù)移進(jìn)。 若最終能歸約成文法的開始符號，則分析成功。 關(guān)鍵是如何判斷可歸約串？,問題的提出： 在構(gòu)造語法樹的過程中，何時(shí)歸約？ 當(dāng)可歸約串出現(xiàn)在棧頂時(shí)就進(jìn)行歸約。 如何知道在棧頂符號串中已經(jīng)形成可歸約串？ 如何進(jìn)行歸約？ 通過不同的自底向上的分析算法來解釋，不同的算法對可歸約串的定義是不同的，但分析過程都有一個(gè)共同的特點(diǎn)：邊移進(jìn)邊歸約。,規(guī)范歸約概念,有文法G，開始符號為S, 如果有S=xy,則xy

5、是文法G的句型，x,y是任意的符號串 如果有S=xAy, 且有A=,則是句型xy相對于非終結(jié)符A的短語 如果有S=xAy, 且有A-,則是句型xy相對于A-的直接短語 位于一個(gè)句型最左邊的直接短語稱為句柄。,注: 每次歸約的部分必須是稱之為句柄的字符串(最右推導(dǎo))。關(guān)鍵的問題是如何識別句柄,例子,下面的例子說明作為短語的兩個(gè)條件缺一不可。 例考慮表達(dá)式文法： E T|E+T T F|T*F F i | (E) 對于句型i*i+i 推導(dǎo) E E+T E+F E+i T+i T*F+T T*i+i F*i+i i*i+i 盡管有E +i+i 但是, i+i 并不是該句型的一個(gè)短語，因?yàn)椴淮?/p>

6、在從E(文法開始符）到i*E的推導(dǎo)。,句型的短語和句柄舉例,文法：S (T)| TS|T,S|a 短語： 句型((a),S) S =* (T,S) T =+ (a) 句型((T,S),S) S =* ((T),S) T =+ T,S 句型(a,(T),(T,S))直接短語以及句柄： S =* (T,(T),(T,S)) T = a S =* (a,S,(T,S)) S =(T) S =* (a,(T),(T)) T =T,S,短語與語法樹的關(guān)系,短語：語法樹子樹的葉子結(jié)點(diǎn)組成的符號串。 直接短語：語法樹簡單子樹（只有父子兩代）的葉子結(jié)點(diǎn)組成的符號串。 句柄：語法樹最左邊簡單子樹的葉子結(jié)點(diǎn)

7、組成的符號串。,,短語與語法樹關(guān)系的例子,句型(a,(T),(T,S))的語法樹：,用句柄對句子abbcde進(jìn)行歸約,用句柄對句子進(jìn)行歸約的過程與用移進(jìn)-歸約過程是一致的，使用歸約的產(chǎn)生式及其順序是一致的。,(1)S aAcBe(2)A b (3)A Ab(4)B d,(2) Ab,(3)A Ab,aAbcde,aAcde,(4)B d,(1)S aAcBe,aAcBe,S,,,,,規(guī)范歸約的定義,假定是文法G的一個(gè)句子，如果序列： n, n-1, , 0 (=S)滿足如下條件，則序列 n, n-1, , 0是一個(gè)規(guī)范歸約: (1) n = 是給定的句子 (2) 0 =S 是文法的開始符號

8、 (3) 對任何i, 0

9、算法。 “移進(jìn)-歸約”分析法用棧實(shí)現(xiàn)的特點(diǎn)： 可歸約串必定位于棧頂，即可歸約串之后就是剩余的輸入串。 棧內(nèi)符號串與剩余輸入串正好構(gòu)成一個(gè)句型。,例：有文法： E-E+T|T T-T*F|F F-(E)|i 對輸入串 i1+i2*i3 的規(guī)范歸約過程：,動作 棧 輸入緩沖區(qū) 1) 準(zhǔn)備 # i1+i2*i3# 2) 移進(jìn) #i1 +i2*i3# 3) 歸約 Fi #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

10、+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)生式序列表示語法分析樹,E-E+T | T T-T*F | F F-(E) | i,i1 + i2 * i3,F,,T,,E,F,,T,F,T,E,算符優(yōu)先分析,算符優(yōu)先分析法的思想源于表達(dá)式的分析，即利用相鄰終結(jié)符號之間的關(guān)系來尋找可歸約串。 將句型中的終結(jié)符號當(dāng)作“算符”

11、，借助于算符之間的優(yōu)先關(guān)系確定可歸約串。 顯然，在一個(gè)符號串中，任意兩個(gè)相鄰終結(jié)符號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不可能相鄰，即此符號串不是句型(出錯(cuò))。 如果以上四種關(guān)系中的任意兩種都不會同時(shí)成立，則可以根據(jù)終結(jié)符號之間的歸約關(guān)系進(jìn)行語法分析。,算符文法:一個(gè)上下無關(guān)文法G,如果沒有P-,且沒有P-...QR...(P,Q,R屬于非終結(jié)符),則G是一個(gè)算符文法。 算符優(yōu)先關(guān)系的定義： a b,G中有P-...ab...或P-...aQb.

12、.. (在同一產(chǎn)生式中) a b,G中有P-...aR...的產(chǎn)生式,且R=b...或R=Qb... a b,G中有P-...Rb...的產(chǎn)生式,且R=...a或R=...aQ,算符優(yōu)先文法（OPG）的定義,+,+,+,+,例：EE+E | E*E | (E) | i 證明不是OPG文法。 因?yàn)椋篍E+E ， EE*E 則有 + * 又因?yàn)椋篍E*E, EE+E 則有 + * 所以不是算符優(yōu)先文法。,算符優(yōu)先文法 算符文法G的任何終結(jié)符a,b之間要么沒有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系,至多有 , , 中的一種成立,則G為一算符優(yōu)先文法。,算符優(yōu)先關(guān)系表的構(gòu)造,FIRSTVT集 定義：對每個(gè)非

13、終結(jié)符P, FIRSTVT(P)=a|P=a...或P=Qa...,a為終結(jié)符,P，Q為非終結(jié)符,由優(yōu)先性低于的定義和FIRSTVT集合的定義可以得出： 若存在某個(gè)產(chǎn)生式：aP，對所有： bFIRSTVT (P)，都有：a b。,按照下面兩條規(guī)則來構(gòu)造FIRSTVT集： 若有產(chǎn)生式P-a...或P-Qa...,則aFIRSTVT(P) 若有產(chǎn)生式P-R...,則FIRSTVT(R)包含在FIRSTVT(P)中,LASTVT集 定義：對每個(gè)非終結(jié)符P, LASTVT(P)=a|P = ...a或P =...aQ, a為終結(jié)符,P，Q為非終結(jié)符,+,+,由優(yōu)先性高于的定義和LASTVT集合的定

14、義可以得出： 若存在某個(gè)產(chǎn)生式：Pb，對所有： aLASTVT (P)，都有：a b。,按照下面兩條規(guī)則來構(gòu)造LASTVT集： 若有產(chǎn)生式P-...a或P- ...aQ,則aLASTVT(P) 若有產(chǎn)生式P-...R,則LASTVT(R)包含在LASTVT(P)中,構(gòu)造優(yōu)先關(guān)系表 如果每個(gè)非終結(jié)符的FIRSTVT和LASTVT集均已知,則可構(gòu)造優(yōu)先關(guān)系表。 若產(chǎn)生式右部有...aP...的形式,則對于每個(gè)bFIRSTVT(P)都有a b 若產(chǎn)生式右部有...Pb的形式,則對于每個(gè)aLASTVT(P)集,都有a b 若產(chǎn)生是形如：Aab 或 AaBb形式，則有a b 構(gòu)造優(yōu)先關(guān)系表的算法如下

15、：,For 每條形如PX1X2Xn的產(chǎn)生式 do for i =1 to n-1 do if Xi和Xi+1都是終結(jié)符 then Xi = Xi+1 if i Xi+1 ,算符優(yōu)先分析算法,通過比較終結(jié)符間的優(yōu)先關(guān)系來實(shí)現(xiàn) 根據(jù)優(yōu)先分析的原理，語法分析程序的任務(wù)是：不斷移進(jìn)輸入符號，識別可歸約串并進(jìn)行歸約。 分析的方法：根據(jù)優(yōu)先性“高于”來識別可歸約串的頭，根據(jù)優(yōu)先性“低于”來識別可歸約串的尾。各種優(yōu)先關(guān)系已經(jīng)存于優(yōu)先關(guān)系表中。,,不能識別只由一個(gè)非終結(jié)符組成的句柄。不能保證每次對句柄進(jìn)行歸約,在算符優(yōu)先分析過程中,每次歸約的符號串,是當(dāng)前句型的最左素短語。 素短語：至少含有一個(gè)終結(jié)符,且

16、除自身外,不再包含任何其它更小的素短語。 最左素短語(leftmost prime phrase)：是指位于句型最左邊的那個(gè)素短語。,例：下述文法的一個(gè)句型： T * F + i 其短語、素短語、最左素短語分別是？,ET | E+T TF | T*F Fi | (E),短語有：i, T * F, T * F + i 素短語有： i, T * F 最左素短語是：T * F,例:文法G E-E+T|T T-T*F|F F-(E)|i 句型T+T*F+i的語法樹如圖：,根據(jù)語法樹可知： 句型#T+T*F+i#的短語有： T 相對非終結(jié)符E的短語 T*F 相對非終結(jié)符T的短語 T+T*F 相對非終結(jié)

17、符E的短語 i 相對非終結(jié)符P、F、T的短語 T+T*F+i 相對非終結(jié)符E的短語,根據(jù)素短語的定義可知： i和T*F為素短語。 其中：T+T*F (含T*F素短語)、 T+T*F+i (含T*F素短語) 和 T(不含終結(jié)符)也不是素短語 T*F為最左素短語。,,一個(gè)算符文法G的某個(gè)句型的最左素短語可描述： 設(shè)句型的一般形式為(NiVN,ai VT #N1a1 N2a2 Nnan Nn+1# 它的最左素短語是滿足下列條件的最左子串： Niai Ni+1ai+1 Njaj Nj+1 其中：ai-1ai,, aiai+1 .. aj-1aj ， ajaj+1,該定理說明了最左素短語與

18、周圍符號之間的關(guān)系,算符優(yōu)先分析過程：(根據(jù)最左素短語的定義) 句型的一般形式: #N1a1N2a2...NnanNn+1#(ai為終結(jié)符,Ni為可有可無的非終結(jié)符) 從左向右掃描各符號,依次查看算符優(yōu)先矩陣,直至找到滿足ai ai+1的終結(jié)符為止,一直移進(jìn)，再從ai開始往左掃描,直至找到滿足關(guān)系aj-1 aj的終結(jié)符為止,進(jìn)行歸約。 此時(shí),形如:Nj aj Nj+1 aj+1.....Ni ai Ni+1的子串即為最左素短語，應(yīng)被歸約。 分析過程的結(jié)束：分析棧中為#S，輸入串為#,例: E-E+T|T T-T*F|FF-(E)|i 把#入棧,讀一符號i, 因?yàn)? + ,所以歸約:F-i 因

19、# * , 所以歸約:F-i 因+ # , 所以歸約:F-i 因* # , 所以歸約:T-F*F 因+ # , 所以歸約:E-T+F 分析成功,求i+i*i的算符優(yōu)先分析過程,棧 輸入緩沖區(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 = #; a = 下一個(gè)輸入符號; WHILE (a #) DO IF sk VT THEN j=k ELSE j=k-1; //sj為

20、棧頂終結(jié)符 WHILE sj a DO //當(dāng)棧頂終結(jié)符優(yōu)先級高于輸入符號時(shí) //尋找最左素短語進(jìn)行歸約 DO q=sj; if sj-1 VT THEN j=j-1 ELSE j=j-2; WHILE (not sj < q) //找到最左素短語的前一個(gè)終結(jié)符 把sj+1.sk歸約為某個(gè)N； k=j+1; sk = N; IF sj < a or sj = a THEN k=k+1; sk=a; a = 下一個(gè)輸入符號; ELSE error; ,,算符優(yōu)先分析一般并不等價(jià)于規(guī)范歸約 并不對文法的非終結(jié)符定義優(yōu)先關(guān)系，無法發(fā)現(xiàn)由單個(gè)非終結(jié)符組成的“可歸約串”。即無法使用單非產(chǎn)生式(如：TF)進(jìn)行歸約。 算符優(yōu)先分析比規(guī)范歸約過程要快，跳過了所有的單非產(chǎn)生式。 可能將本來不是句子的輸入串誤認(rèn)為是句子。,算符優(yōu)先分析法小結(jié),優(yōu)點(diǎn) 簡單、效率高 能夠處理部分二義性文法 缺點(diǎn) 文法書寫限制大 占用內(nèi)存空間大 不規(guī)范、存在查不到的語法錯(cuò)誤,