編譯原理第4章小結(jié)網(wǎng)

1、確定的自上而下分析法 自下而上分析法 遞歸下降分析法預(yù)測分析法 本章介紹了四種典型的語法分析方法算符優(yōu)先分析法LR分析法 LR(0)分析法 SLR(1)分析法 LR(1)分析法 LALR(1)分析法 編譯原理第4章小結(jié)網(wǎng) 確定的自上而下分析法要求描述 語言的文法是 LL(1)文法。 1. LL(1)文法的判別方法。 (1) 求文法每個產(chǎn)生式右部符號串的 FIRST集。(2)求文法各個非終結(jié)符的FOLLOW集。一.確定的自上而下分析法編譯原理第4章小結(jié)網(wǎng)(3)求文法每個產(chǎn)生式的SELECT集。(4)求相同左部產(chǎn)生式的SELECT交集。對文法G的每一個非終結(jié)符A的產(chǎn)生式SELECT(A i)SEL

2、ECT(A j)= (ij)則文法G是一個LL(1)文法A 1 | 2 | n下面條件成立:編譯原理第4章小結(jié)網(wǎng)2. LL(1)文法是無左遞歸、無二義性文 法。3. 將非LL(1)文法改寫為LL(1)文法的方 法。(1) 消除文法直接左遞歸PP | 改寫為 PP , P P | 或 P編譯原理第4章小結(jié)網(wǎng)(2) 提取公共左因子若 A 1 | 2 | | n 提取公共左因子將文法改寫成: A AA 1| 2| | n編譯原理第4章小結(jié)網(wǎng)4.根據(jù)文法規(guī)則構(gòu)造遞歸下降分析程序 和預(yù)測分析表的方法5. 注意LL(1)分析法與LR分析法的區(qū)別LL(1)分析法(預(yù)測分析法)是自上而下的語法分析法,要求文法

3、為LL(1)文法LR分析法是自下而上的語法分析法, 只要文法是上下文無關(guān)文法編譯原理第4章小結(jié)網(wǎng)例1 設(shè)有文法GE：為消除文法直接左遞規(guī),請改寫文法,改 寫后的文法為:E E+T | ET | TT T*F | T/F | FF (E) | id編譯原理第4章小結(jié)網(wǎng) T +T | T E E E+T | ET | TT T*F | T/F | FF (E) | id F *F | /F T (E) | id F 編譯原理第4章小結(jié)網(wǎng)例2 設(shè)有文法GSSaAbDe | dABSD | eBSAc | cD | DSe | 1. 計算文法GS每個非終結(jié)符的FIRST集 和FOLLOW集 。2. 判

4、斷文法GS 是否LL(1)文法。 編譯原理第4章小結(jié)網(wǎng)對每一文法符號XV, 求FIRST(X)的規(guī)則: FIRST() = a | a且 aVT *,則規(guī)定 FIRST()若 *1. 若 XVT , 則FIRST(X) =X2. 若 XVN 且有 X a, 則把 a 加入 FIRST(X)中 ,若 X , 則把 加入FIRST(X)中 3. 若 XY, YVN ,則把 FIRST(Y)中所有 非 元素加入FIRST(X)中 編譯原理第4章小結(jié)網(wǎng) FIRST(S)=FIRST(aAbDe)FIRST(d)= a,d FIRST(A)=FIRST(B)FIRST(e) =FIRST(S)FIRST

5、(cD)e= a,d,c,e SaAbDe | dABSD | eBSAc | cD | DSe | 問: 能否 因為從 A */ , 所以 FIRST(A) FIRST(B)=FIRST(S)FIRST(cD)= a,d,c, FIRST(D)=FIRST(Se)= a, d, 編譯原理第4章小結(jié)網(wǎng)FOLLOW(A) = a | S Aa 且aVT *若有S A ,*則規(guī)定 $FOLLOW(A)。 求FOLLOW(A)的規(guī)則:1. 對文法的開始符號S , 令$FOLLOW(S)2.若 AB是一條規(guī)則, 則將FIRST() 加到FOLLOW(B)中3.若 AB是一條規(guī)則, 或 AB是一條規(guī)則而

6、 , 則把FOLLOW(A)加到FOLLOW(B)中*編譯原理第4章小結(jié)網(wǎng) FOLLOW(S)=$,a,b,c,d,eFOLLOW(A)=b,cFOLLOW(B)=a,dFOLLOW(D)=a,b,c,d,eSaAbDe | dABSD | eBSAc | cD | DSe | FIRST(D)= a, d, FIRST(S)= a,d FIRST(A)= a,d,c,e 編譯原理第4章小結(jié)網(wǎng)根據(jù)LL(1)文法的定義有:SELECT(SaAbDe)SELECT(Sd)=FIRST(aAbDe)FIRST(d)=SELECT(ABSD)SELECT(Ae)=FIRST(BSD)FIRST(e)=

7、SaAbDe | dABSD | eBSAc | cD | DSe | SELECT(BSAc)SELECT(BcD)=FIRST(SAc)FIRST(cD)=SELECT(BSAc)SELECT(B)=FIRST(SAc) , a, d FOLLOW(B)=a,d所以該文法不是LL(1)文法編譯原理第4章小結(jié)網(wǎng)例3 已知一個有限輸入字符集合=a, b, 請用高級程序語言編寫一個能識別集合 L=an bn | n0的程序。分析 首先給出識別該語言的文法為SaSb | 該文法無左遞歸且為LL(1)文法根據(jù)文法給出識別該語言的分析程序如下:編譯原理第4章小結(jié)網(wǎng)main( ) scaner( );

8、S( ); if (sym=$) printf (“right”); else error( ); S( ) if sym=a scaner( ); S( ); if (sym=b) scaner( ); else error( ); else if ( sym!=b) & (sym!=$) error( ); SaSb | 編譯原理第4章小結(jié)網(wǎng)例 設(shè)有文法GE： 試構(gòu)造該文法的預(yù)測分析表。 EE + T | TTT * F | FF(E) | id 編譯原理第4章小結(jié)網(wǎng)分析 首先消去文法左遞歸，得到文法 GEE TEE +TE | T FTT *FT | F (E) | idEE +

9、 T | TTT * F | FF(E) | id 編譯原理第4章小結(jié)網(wǎng) 無左遞歸的文法不一定是LL(1)文法，根據(jù)LL(1)文法的判斷條件，對非終結(jié)符 E, T, F有： E TEE +TE | T FTT *FT | F (E) | idETEETE T FTF (E) (TE ) ETE T FT +ETE FT + TE +ETE (FT ) 編譯原理第4章小結(jié)網(wǎng) SELECT(E +TE)SELECT(E ) =FIRST(+TE)FIRST()FOLLOW(E) = + ), $ = SELECT(T *FT)SELECT(T ) =FIRST(*FT)FIRST()FOLLOW(

10、T) = * ), $, + = 編譯原理第4章小結(jié)網(wǎng) SELECT(Fid )SELECT(F(E) = FIRST(id)FIRST(E)=id(= 所以文法GE是LL(1)文法。 編譯原理第4章小結(jié)網(wǎng) E E T T F (, id ), $ (, id +, ), $ (, id +, ), $, * +, ), $ *, +, ), $ FIRSTFOLLOWE TEE +TE | T FTT *FT | F (E) | id編譯原理第4章小結(jié)網(wǎng) id + * ( ) $ E E T T F對規(guī)則E TEFIRST(TE) = (, id ETEETE FIRST(+TE) = +

11、E +TE FOLLOW(E)= ), $ EETFTTFTTTTT*FTFidF(E)E TEE +TE | T FTT *FT | F (E) | id對規(guī)則E +TE 對規(guī)則E 編譯原理第4章小結(jié)網(wǎng)句子 id+id*id $ 的分析過程 分析棧 輸入串$ E id+id*id $ $ ET id+id*id $ ETF id+id*id $ETid id+id*id $ ET +id*id $ E +id*id $ ET+ +id*id $ ET id*id $ $ 編譯原理第4章小結(jié)網(wǎng)1. 算符優(yōu)先分析法特別適合于分析算 術(shù)表達式,但不是專用于分析算術(shù)表 達式的。二. 自下而上語法分析

12、法(一). 算符優(yōu)先分析法編譯原理第4章小結(jié)網(wǎng)2. 算符優(yōu)先文法的判別方法(1) 判所給文法G是否算符文法。若文法 中沒有形如 ABC 規(guī)則，則稱G 為算符文法。 (2) 對算符文法G，計算每個非終結(jié) 符的 FIRSTVT 和 LASTVT集。編譯原理第4章小結(jié)網(wǎng)(3) 根據(jù)算符優(yōu)先關(guān)系定義，計算文法 G中任意兩個終結(jié)符之間的優(yōu)先關(guān) 系,即構(gòu)造優(yōu)先關(guān)系表。(4) 若任意兩個終結(jié)符之間至多只有 、 、 三種關(guān)系的一種成 立，則G是一個算符優(yōu)先文法。 .編譯原理第4章小結(jié)網(wǎng)3. 算符優(yōu)先分析法只在終結(jié)符之間定 義了優(yōu)先關(guān)系，因而它的歸約過程 與規(guī)范歸約是不同的，它不是對句 柄進行歸約，而是對最左素

13、短語進 行歸約。編譯原理第4章小結(jié)網(wǎng)4. 求最左素短語的方法(1) 畫出句型的語法樹。(2) 根據(jù)語法樹求出句型的所有短語。(3) 滿足下列條件的短語:至少含有一 個終結(jié)符;除自身之外不再包含其 他素短語。編譯原理第4章小結(jié)網(wǎng)5. 根據(jù)優(yōu)先關(guān)系定義構(gòu)造優(yōu)先關(guān)系表 的方法。6. 由于算符優(yōu)先分析法忽略了非終結(jié) 符 在歸約過程中的作用，可能導(dǎo) 致把不是句子的輸入串誤認為是句 子。編譯原理第4章小結(jié)網(wǎng)例1 設(shè)有文法GS:S AA B | AiBB C | B+CC )A*|( 給出句型C+C i (的所有短語、句柄和素 短語。分析 首先畫出句型的語法樹編譯原理第4章小結(jié)網(wǎng)SAAiBB+CCC(短語:

14、 C+C i ( C+C C ( 句柄: C 素短語: C+C ( 編譯原理第4章小結(jié)網(wǎng)例2 設(shè)有文法GE:E ET+ | TT TF* | FF F | a 給出句型FF*的所有短語、句柄和素 短語。分析 首先畫出句型的語法樹編譯原理第4章小結(jié)網(wǎng)ETTF*FFF根據(jù)語法樹求短語FF*FFF素短語F句柄F編譯原理第4章小結(jié)網(wǎng)例3 設(shè)有表格結(jié)構(gòu)文GS：S a | | (T)T T, S | S(1)計算文法GS的FIRSTVT集和 LASTVT集。(2) 構(gòu)造GS的優(yōu)先關(guān)系表，并判斷GS是否算符優(yōu)先文法。編譯原理第4章小結(jié)網(wǎng)計算文法GS的FIRSVT集和LASTVT集如下:FIRSTVT(A)=

15、b | A b或A Bb,bVT , BVN +LASTVT(A)=a | A a 或A aB, aVT, BVN +編譯原理第4章小結(jié)網(wǎng) FIRSTVT LASTVT S TS a | | (T)T T, S | S a, , ( a, , ) , ,a,( , ,a,) 編譯原理第4章小結(jié)網(wǎng) 尋找終結(jié)符在左邊，非終結(jié)符在右邊的符號對有 尋找非終結(jié)符在左邊，終結(jié)符在右邊的符號對有 T ) LASTVT(T) ).T , LASTVT(T) ,.( T ( FIRSTVT(T)., S , FIRSTVT(S).=.返回編譯原理第4章小結(jié)網(wǎng)S a | | (T)T T, S | S 文法GS是

16、一個算符優(yōu)先文法。因為文法GS的任何規(guī)則右部都不含兩個相鄰的非終結(jié)符,并且任何兩個終結(jié)符之間至多只存在一種優(yōu)先關(guān)系。編譯原理第4章小結(jié)網(wǎng)(二) LR分析法大多數(shù)用上下文無關(guān)文法描述的語言都可以用相應(yīng)的LR分析器予以識別。1. LR分析法是一種規(guī)范歸約分析法，編譯原理第4章小結(jié)網(wǎng)2. 從給定的上下文無關(guān)文法構(gòu)造 LR分析表的方法是： 對LR(1)或 LALR(1)分析表，構(gòu)造 LR(1)項目集規(guī)范族。(1) 對LR(0)或 SLR(1)分析表，構(gòu)造 LR(0)項目集規(guī)范族;編譯原理第4章小結(jié)網(wǎng)(2)構(gòu)造識別文法規(guī)范句型活前綴的DFA。 (3)將DFA轉(zhuǎn)換成相應(yīng)的LR分析表。 注意文法一定要拓廣。

17、注意文法一定要拓廣。 四種分析表的構(gòu)造基本相同，僅對含僅對含歸約項目的項目集構(gòu)造分析表元素不同。歸約項目的項目集構(gòu)造分析表元素不同。 3. 四種LR文法的判別方法 (1) 任何的二義性文法都不是LR類文法。編譯原理第4章小結(jié)網(wǎng) SLR(1)文法是文法是LR(0)項目集中所有項目集中所有含沖突的項目集都能用含沖突的項目集都能用SLR規(guī)則解決沖規(guī)則解決沖突突。 (或SLR(1)分析表中不含多重定義) (2)根據(jù)項目集中是否含沖突項目項目集中是否含沖突項目或相應(yīng)分析表中是否含多重定義元素進行判斷： LR(0)文法是所有的所有的LR(0)項目集中項目集中沒有沒有移進移進歸約沖突或歸約歸約沖突或歸約歸約

18、沖突歸約沖突。(或LR(0)分析表中不含多重定義)編譯原理第4章小結(jié)網(wǎng) SLR規(guī)則：規(guī)則： I: A .b B 1 1. B2 2. b FOLLOW(B1)= FOLLOW(B1)FOLLOW(B2)= b FOLLOW(B2)= a b 移進移進 a FOLLOW(B1) 用用B 1 1 歸約歸約 a FOLLOW(B2) 用用B2 2 歸約歸約 編譯原理第4章小結(jié)網(wǎng) LR(1)項目集中無移進歸約沖突或歸約歸約沖突。（或LR(1)分析表中不含多重定義） 注意注意 : 搜索符只對歸約項目起作用。搜索符只對歸約項目起作用。 I: A .b , a B 1 1. , a I: A .b , a

19、B 1 1. , b I: B 1 1. , a B2 2. , a I: B 1 1. , a B2 2. , b 編譯原理第4章小結(jié)網(wǎng) LALR(1)項目集中無歸約歸約沖突。(或LALR(1) 分析表中不含多重定義）4.四種LR類文法之間的關(guān)系 一個文法是一個文法是LR(0)文法一定也是文法一定也是SLR(1)文法文法，也是LALR(1)、LR(1)文法，反之則不一定成立。即LR(0)SLR(1)LALR(1)LR(1)編譯原理第4章小結(jié)網(wǎng)例1 考慮文法SAS | bASA | a(1) 構(gòu)造識別文法活前綴的DFA。(2) 該文法是LR(0)文法嗎？請說明理由。(3) 該文法是SLR(1)

20、的嗎？若是，構(gòu)造它 的SLR(1)分析表。(4) 該文法是LR(1)或LALR(1)文法嗎? 請說明理由。編譯原理第4章小結(jié)網(wǎng)解：首先將文法拓廣，并對規(guī)則進行編號 0. S S1. S AS2. S b3. A SA4. A a編譯原理第4章小結(jié)網(wǎng)(1) 識別文法活前綴的DFA如下圖所示。 I0: SSS ASS bA SAA aSSA SAS bA SAA aS ASI1:S ASS bA SAA aS ASI2:S ASS bA SAA aA SAS ASI5:I3: S bI4: A a S AS S bA SAA aA SAS ASI6:SAbbbaaaAAabSSAbaA識別文法GS

21、活前綴DFA編譯原理第4章小結(jié)網(wǎng)(1) 識別文法活前綴的DFA如下圖所示。 I0: SSS ASS bA SAA aSSA SAS bA SAA aS ASI1:S ASS bA SAA aS ASI2:A SAS bA SAA aS ASI7:S ASS bA SAA aA SAS ASI5:I3: S bI4: A a S AS S bA SAA aA SAS ASI6:SAbbbaaaAAabSSAbaASSbASa識別文法GS活前綴DFA編譯原理第4章小結(jié)網(wǎng)(2) 由上圖不難看出，項目集I1, I5, I6 中存在著移進歸約沖突，所以該文法不是LR(0)文法。 (3) 由于對該文法句子

22、abab對應(yīng)下面兩棵不同的語法樹：(見下圖) 編譯原理第4章小結(jié)網(wǎng)SSAaSASAbabSSAaSASAbab 所以該文法為二義性文法，任何二義性所以該文法為二義性文法，任何二義性文法絕不是文法絕不是SLR(1)文法，也不是文法，也不是LALR(1)或或LR(1)文法。文法。 0. SS1. S AS2. S b3. A SA4. A a編譯原理第4章小結(jié)網(wǎng) 例2 設(shè)有文法GS:S (S) | 試判斷該文法是否SLR(1)文法，若不是，請說明理由；若是，請構(gòu)造SLR(1)分析表。 解: 首先將文法拓廣，并給出每條規(guī)則編號 0. SS1. S (S)2. S 編譯原理第4章小結(jié)網(wǎng)I0:SSS (

23、S)S I3: S (S) 構(gòu)造該文法的LR(0)項目集族和轉(zhuǎn)換函數(shù)如下圖所示。 該文法不是LR(0)文法。因為I0，I2中含有移進歸約的沖突。 I1: SS.I2:S (S)S (S)S I4: S (S)S(S()0. S S1. S (S)2. S 見表編譯原理第4章小結(jié)網(wǎng)但是I0，I2中的移進歸約的沖突可以用SLR(1)方法解決：FOLLOW(S)=), $(=所以該文法是SLR(1)文法。其SLR(1)分析表如下表：編譯原理第4章小結(jié)網(wǎng)ACTIONGOTO( ) $SO1234S2 r2 r2acc1S2 r2 r23S4r1 r1文法GS的SLR(1)分析表0. S S1. S (

24、S)2. S 見圖編譯原理第4章小結(jié)網(wǎng)例3 設(shè)有文法GS:試證明該文法是SLR(1)文法，但不是LR(0)文法。解：首先將文法拓廣，并對規(guī)則進行編號 直接構(gòu)造LR(0)項目集如下： S aSb | aSd | 0. S S1. S aSb2. S aSd3. S 編譯原理第4章小結(jié)網(wǎng)I0:S SS aSbS aSdS I1:SSI2:S aSbS aSdS aSbS aSdS I3:S aSbS aSdI4:S aSbI5:S aSd0. S S 2. S aSb1. S aSd 3. S 編譯原理第4章小結(jié)網(wǎng) 檢查每個項目集可知，項目集I0和I2中有移進歸約沖突, 因此該文法不是LR(0)文

25、法。 又因為 所以項目集I0和I2中移進歸約沖突可以用SLR(1)方法解決。因此該文法是SLR(1)文法，但不是LR(0)文法。 FOLLOW(S)=b,d,$a= 編譯原理第4章小結(jié)網(wǎng) 例4 設(shè)有文法GS:2.試判斷該文法是否SLR(1)文法, 若不是, 請說明理由；若是，請構(gòu)造出SLR(1)分析表, 并給出符號串( )$的分析過程。1.構(gòu)造識別文法規(guī)范句型活前綴的DFA( LR(0)項目集族和GO函數(shù) )。S S(S) | 編譯原理第4章小結(jié)網(wǎng)3. 試判斷該文法是否LR(1)文法，若不是，請說明理由；若是，請構(gòu)造LR(1)分析表。4. 試判斷該文法是否LALR(1)文法，請說明理由。編譯原理第4章小結(jié)網(wǎng)分析 首先將文法拓廣，并對規(guī)則編號:0. SS S S(S) 1. S 構(gòu)造LR(0)項目集規(guī)范族和轉(zhuǎn)換函數(shù)如下圖所示:編譯原理第4章小結(jié)網(wǎng)S S(S.)S S.(S)I0:SSS S(S)S I1: SS.I2:I4: S S(S)S(S()0. SS S S(S) 1. S S S.(S)S S(S