1、編譯原理,第一章 編譯程序概述 第二章 PL/0編譯程序的實現(xiàn) 第三章 文法和語言 第四章 詞法分析 第五章 自頂向下語法分析方法 第六章 自底向上優(yōu)先分析方法 第七章 LR分析方法 第八章 語法制導(dǎo)翻譯和中間代碼生成 第九章 符號表 第一章 代碼優(yōu)化 第一一章 代碼生成,第5章 自頂向下語法分析方法,語法分析是編譯程序的核心部分：在詞法分析的基礎(chǔ)上，識別單詞符號序列是否是給定文法的正確句子（程序）。,常用方法,自頂向下分析,自底向上分析,確定 不確定,算符優(yōu)先分析 LR分析,自頂向下語法分析方法,自頂向下分析法就是從文法的開始符號出發(fā)，試圖推導(dǎo)出與輸入的單詞串完全匹配的句子。 如果能夠推導(dǎo)出

2、，則該輸入串是給定文法的句子； 如果不能推導(dǎo)出，則該輸入串不是給定文法的句子。,自頂向下語法分析要解決的關(guān)鍵問題,假定要被代換的最左非終結(jié)符號是B，且有n條規(guī)則：BA1|A2|An，那么如何確定用哪個右部去替代B？,自頂向下語法分析方法,自頂向下分析法分確定性和不確定性兩種。 自頂向下的確定性分析法對文法有一定的限制，但實現(xiàn)簡單直觀，便于手工或自動構(gòu)造； 自頂向下的不確定性分析法是帶有回溯的分析方法，效率低，代價高，極少使用。,第5章 自頂向下語法分析方法,一、確定的自頂向下分析思想 二、LL(1)文法的判別 三、某些非LL(1)文法到LL(1)文法等價變換 四、不確定的自頂向下分析思想 五、

3、確定的自頂向下分析方法,自頂向下語法分析要解決的關(guān)鍵問題,假定要被代換的最左非終結(jié)符號是B，且有n條規(guī)則：BA1|A2|An，那么如何確定用哪個右部去替代B？,一、確定的自頂向下分析思想 1、方法：從開始符號出發(fā)，不斷替換非終結(jié)符，根據(jù)當前的單詞符號就可以唯一選定要替換的產(chǎn)生式。,例1：文法G(S)：SpA SqB AcAd Aa 輸入串 W=pccadd 自頂向下的推導(dǎo)過程為:,a,相應(yīng)的語法樹：,SpA pcAd pccAdd pccadd,例1：文法G(S)：SpA SqB AcAd Aa 該文法的特點： （1）每個產(chǎn)生式的右部都由終結(jié)符號開始； （2 ）如果兩個產(chǎn)生式有相同的左部，則它

4、們的右部由不同的終結(jié)符開始。 對于這樣的文法，其推導(dǎo)過程可以根據(jù)當前的輸入符號決定選擇哪個產(chǎn)生式往下推導(dǎo)，因此，分析過程是唯一確定的。,例2：文法G(S)為： S Ap S Bq A acA BbdB 該文法的特點： （1）產(chǎn)生式的右部不全是由終結(jié)符號開始； （2 ）如果兩個產(chǎn)生式有相同的左部，則它們的右部由不同的終結(jié)符或非終結(jié)符開始。 （3）無空產(chǎn)生式。 ccap 如何根據(jù)輸入串的第1個符號來確定產(chǎn)生式呢？,例2：文法G(S)為： S Ap S Bq A acA BbdB 當輸入W=ccap推導(dǎo)： 自頂向下的推導(dǎo)過程為：,例2：文法G(S)為： S Ap S Bq A acA BbdB 當輸

5、入W=ccap推導(dǎo)： 自頂向下的推導(dǎo)過程為： S Ap cAp ccAp ccap 語法樹為：,a,例2：文法G(S)為： S Ap S Bq A acA BbdB 該文法的特點： （1）產(chǎn)生式的右部不全是由終結(jié)符號開始； （2 ）如果兩個產(chǎn)生式有相同的左部，則它們的右部由不同的終結(jié)符或非終結(jié)符開始。 （3）無空產(chǎn)生式。 ccap 如何根據(jù)輸入串的第1個符號來確定產(chǎn)生式呢？,2、開始符號集合的定義：,設(shè)G=（VT，VN， P ，S ）是上下文無關(guān)文法， 開始符號集合為First()= a | a，aVT， 、V* 規(guī)則右部的開始符號集包括所有終結(jié)符 a，使得規(guī)則右部經(jīng)過若干推導(dǎo)后得到的字符串以

6、a為起始。 若 ，則規(guī)定First() 。,*,*,例3：上例中文法是： SAp|Bq A a | cA B b | dB 則：FIRST(Ap)=？； FIRST(Bq)=？,針對產(chǎn)生式規(guī)則的右部產(chǎn)生開始符號集合,2、開始符號集合的定義：,設(shè)G=（VT，VN， P ，S ）是上下文無關(guān)文法， 開始符號集合為First()= a | a，aVT， 、V* 規(guī)則右部的開始符號集包括所有終結(jié)符 a，使得規(guī)則右部經(jīng)過若干推導(dǎo)后得到的字符串以a為起始。 若 ，則規(guī)定First() 。,*,*,例3：上例中文法是： SAp|Bq A a | cA B b | dB 則：FIRST(Ap)=a，c； FI

7、RST(Bq)=b，d,針對產(chǎn)生式規(guī)則的右部產(chǎn)生開始符號集合,如何根據(jù)輸入串的第1個符號來確定產(chǎn)生式呢？ 根據(jù)當前輸入符號屬于哪個產(chǎn)生式右部的開始符號集合而決定選擇相應(yīng)產(chǎn)生式進行推導(dǎo)。,例3：文法GS ： S aA | d A bAS| 若輸入W=abd，則推導(dǎo)過程為：,例3：文法GS ： S aA | d A bAS| 若輸入W=abd，則推導(dǎo)過程為： S aA abAS abS abd 語法樹為：,當某一非終結(jié)符的產(chǎn)生式中含有空產(chǎn)生式時，第二步推導(dǎo)的產(chǎn)生式該如何確定呢？根據(jù)后跟符號集合確定,3、后跟符號集合的定義：,設(shè)G=（VT，VN，P，S）是上下文無關(guān)文法，AVN，S是開始符號， Fo

8、llow(A)=a | S uA且aVT，a First()，uVT*，V+。針對非終結(jié)符 若S uA，且 ，則#Follow(A) （#表示輸入串的結(jié)束符，或句子括號）,可寫成為： Follow(A)a|SAa， aVT 若SA，則#Follow(A)。,*,*,*,*,*,Follow(A)是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或“#”。,例4：在例2中文法GS為：S Ap | Bq A a | cA B b | dB 求Follow集。,解：Follow(S)=？ Follow(A)=？ Follow(B)=？,換句話說： Follow(A)是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或“#”。,

9、例4：在例2中文法GS為：S Ap | Bq A a | cA B b | dB 求Follow集。,解：Follow(S)=# Follow(A)=p Follow(B)=q,自上而下語法分析要解決的關(guān)鍵問題,假定要被代換的最左非終結(jié)符號是B，且有n條規(guī)則：BA1|A2|An，那么如何確定用哪個右部去替代B？ 根據(jù)規(guī)則的選擇集合來確定。,4、選擇集合的定義 給定上下文無關(guān)文法的產(chǎn)生式A，AVN， V*，若，則Select（A）=First()， 若，則Select(A)=（First()-）Follow(A),*,*,給定輸入串，根據(jù)產(chǎn)生式規(guī)則的選擇集合選擇產(chǎn)生式進行推導(dǎo)。,5、LL(1)文

10、法的定義： 一個上下文無關(guān)文法是LL(1)文法的充分必要條件是對每個非終結(jié)符A的兩個不同產(chǎn)生式： A，A滿足Select(A)Select(A)=，其中、不同時推出 只有對滿足LL(1)文法的句子，才能進行確定的自頂向下分析： 給定輸入串，就可以根據(jù)產(chǎn)生式規(guī)則的選擇集合確定唯一的產(chǎn)生式進行推導(dǎo)。,LL(1)的含義：從左L向右掃描輸入串，分析過程中采用最左L推導(dǎo)，只需向右看1個符號就可確定如何推導(dǎo)（選擇哪個產(chǎn)生式進行推導(dǎo)）。,例5：上例3文法： SaA|d AbAS| 證明該文法為LL(1)文法。,例5：上例3文法： SaA|d AbAS| 證明該文法為LL(1)文法。 不難看出：Select(

11、Sa A)=First(aA)a Select (Sd)= First(d)=d Select (AbAS)=b Select (A)=（first()- ）follow(A)=a,d,# Select (S aA) Select(Sd) ad= Select(AbAS) Select(A) ba,d,#= 所以上述文法是LL(1)文法。,SAa aA ,*,SaA abAS abAd S aA abAS abAaA 所以Follow(A)=a,d,#,例：設(shè)文法GS為： S aAS | b A bA | 判別是否是LL(1)文法。,解：Select(S aAS)=first(aAS)=a S

12、elect ( S b ) =b Select ( A bA ) =b Select ( A ) =（first()-）follow(A)=a,b Select( SaAS ) Select(Sb ) a b = Select(A bA) Select(A )ba,b 因此，該文法不是LL（1）文法，因而也就不可能用確定的自頂向下分析。,當需要選用自頂向下分析技術(shù)時，首先必須判定所給的文法是否是LL(1)文法。,二、 LL(1)文法的判別,例：若文法GS為： S AB | bC A | b B | aD C AD | b D aS | c 判別文法是否是LL(1)文法。,解：(1) 計算fir

13、st集： 方法一：計算first 集合的算法： 對于每一個文法符號xV，計算first(x)的方法如下：,若xVT，則first(x)x 若xVN，且有xa，aVT，則afirst(x) 若xVN，x ，則first(x) 若xVN，y1，y2，yi都VN，產(chǎn)生式xy1y2yn，當y1，y2，yi-1都 時(1in)， 則first(y1)， first(y2)， first(yi1)，first(yi)都包含在first(x)中。 e) 當上式中所有yi (1in)， 則first(x)first(y1) first(y2) first(yn) ,*,*,first(S)= first(A)

14、= first(B)= first(C)= first(D)=,S AB | bC A | b B | aD C AD | b D aS | c,按上面的規(guī)則可得上例文法中每個文法符號的first集合如下：,first(S)=first(A)- first(B)- b=a,b, first(A)=b =b, first(B)= a=a, first(C)=first(A)- first(D) first(b)=a,b, c first(D)=a c=a,c,S AB | bC A | b B | aD C AD | b D aS | c,按上面的規(guī)則可得上例文法中每個文法符號的first集合如

15、下：,一個文法符號串的first集合計算方法：,如果文法符號串V*, =X1X2Xn, 1、當X1，則first()=first(X1) 2、當對任何j（1ji-1，2 i n），first(Xj) 則first()=(first(X1)-) (first(X2)-) (first(Xi-1)-) first(Xi) 3、當first(Xj)都含有時(1 j n)，則first()=first(X1) first(X2) first(Xj) ,*,根據(jù)上面規(guī)則，每個產(chǎn)生式的右部符號串開始符號集合為： first(AB)= first(bC)= first()=,first(aD)= first

16、(AD)= first(b)= first(aS)= first(c)=,根據(jù)上面規(guī)則，每個產(chǎn)生式的右部符號串開始符號集合為： first(AB)=first(A) first(B) =a, b, first(bC)=b first()= ,根據(jù)規(guī)則2 因為A D,first(aD)=a first(AD)=(first(A)-) first(D)=a,b,c first(b)=b first(aS)=a first(c)=c,根據(jù)規(guī)則3 因為A B,方法二：由關(guān)系圖法求文法符號的first集合,1、每個文法符號對應(yīng)圖中的一個結(jié)點，終結(jié)符結(jié)點用符號本身標記，非終結(jié)符結(jié)點用first(A)標記。

17、 2、若文法中有AX， ，則從對應(yīng)A的結(jié)點到對應(yīng)X結(jié)點連一條箭弧。 3、凡是從first(A)結(jié)點有路徑可到達的終結(jié)符結(jié)點所標記的終結(jié)符都為first(A)的成員。 4、根據(jù)判別步驟1確定是否為某非終結(jié)符first的成員，若是則將加入該非終結(jié)符的first集中。,*,first(S),first(B),first(C),first(A),first(D),b,a,c,文法為： S AB | bC A | b B | aD C AD | b D aS | c,(1) 規(guī)則1：終結(jié)符結(jié)點用符號本身標記，本文法中有a,b,c。,(2) 規(guī)則1：非終結(jié)符結(jié)點用first(A)標記。本文法中有S,A,B

18、,C,D。,(3)規(guī)則2：AX， ，則A到X畫一條箭弧。,S AB看成 ，XA, =B 因此從S到A畫一條弧。,S AB看成 A，XB, = A ,因此從S到B畫一條弧。,S bC看成 ，Xb, =C 因此從S到b畫一條弧。,同理：從A到b，從B到a， 從C到A、D、b， 從D到a、c畫一條弧。,(4)規(guī)則3： first(A)結(jié)點有路徑可到達的終結(jié)符結(jié)點所標記的終結(jié)符都為first(A)的成員。,所以，first(S)a,b first(A)b first(B)a first(C ) a,b,c first(D)a,c,(5)規(guī)則4： 若是某非終結(jié)符first的成員，則將加入該非終結(jié)符的fi

19、rst集中。,所以，first(S)a,b, first(A)b, first(B)a, first(C ) a,b,c first(D)a,c,求follow集的算法： (1)設(shè)S為開始符號，則#follow(S); (2) Follow(A)是所有句型中出現(xiàn)在緊接A之后的終結(jié)符或“#”。,（2）計算Follow 集： 方法一：根據(jù)Follow定義計算，算法如下：,() 構(gòu)造集合FOLLOW的算法,若S為開始符號,則把“#”加入FOLLOW(S)中,(2)若A B (),則把FIRST()-加入FOLLOW(B),設(shè)S, A, BVn , 算法：連續(xù)使用以下規(guī)則，直至FOLLOW集合不再擴大

20、,Follow(S)= Follow(A)= Follow(B)= Follow(C)= Follow(D)=,文法為： S AB | bC A | b B | aD C AD | b D aS | c,S AB B Bb A AaD,Follow(S)=# Follow(A)=a，#，c Follow(B)=# Follow(C)=# Follow(D)=#,文法為： S AB | bC A | b B | aD C AD | b D aS | c,S為開始符號，#加入follow(S)中。,S AB A A AB AaD bC bADbAc,方法二：根據(jù)關(guān)系圖法求非終結(jié)符Follow集。(

21、略),(3) 計算Select集： 選擇集合的定義 給定上下文無關(guān)文法的產(chǎn)生式A，AVN， V*，若，則Select（A）=First()， 若，則Select(A)=（First()-）Follow(A),文法為： S AB | bC A | b B | aD C AD | b D aS | c,(3) 計算Select集： 每個產(chǎn)生式的Select集合計算為: Select(SAB)= first (AB)/Follow(S)=b,a,# Select(S bC)= first (bC)=b Select(A)= first ()/Follow (A)=c,a,# Select(Ab)=

22、first (b) =b Select(B)= first () / Follow (B)= # Select(BaD)= first (aD) =a Select(CAD)= first (AD) =b,a,c,因為A B ,Select(Cb)= first (C) =b Select(DaS)= first (aS) = a Select(Dc)= first (c) =c 所以select的交集為：,Select(SAB) Select (SbC)= b Select(A) Select (Ab)= Select(B) Select (BaD)= Select(CAD) Select

23、(Cb)= b Select(DaS) Select (Dc)= 因此該文法不是LL(1)文法。,三、 某些非LL(1)文法到LL(1)文法的等價變換,若文法中含有直接或間接左遞歸，含有左公共因子，該文法肯定不是LL(1)文法，要進行變換。,1、 提取左公共因子 若文法中含有形如A|的產(chǎn)生式，這導(dǎo)致了對相同左部的產(chǎn)生式其右部的First集相交,也就是Select(A)Select(A) ，不滿足LL(1)文法的充分必要條件. 則須進行提取左公共因子的等價變換: A (|) 寫成一般形式： AA A ,例1：若文法G1的產(chǎn)生式為： SaSb SaS S 提取左公因子后得：,例1：若文法G1的產(chǎn)生

24、式為： SaSb SaS S 提取左公因子后得：SaS( b |) S 進一步變換：SaSA Ab A S,例2：若文法G2的產(chǎn)生式： Aad ABc BaA BbB,解： A ad A aAc A bBc B aA B bB,Aa(d|Ac),A aA A bBc A d A Ac B aA B bB,最后變換為：,上例不難驗證經(jīng)提取左公共因子后文法仍不是LL(1)文法 。 經(jīng)過文法提取左公共因子后的文法不一定是 LL(1)文法。,經(jīng)過文法提取左公共因子后的文法，若有多余的產(chǎn)生式，則必須進行化簡 。,例3：若有文法G3的產(chǎn)生式：SaSd S Ac A aS A b,解：文法替換：SaSd S

25、 aSc Sbc A aS A b,SaSA A d|c Sbc AaS Ab,SaS(d|c),SaSA A d|c Sbc,文法中非終結(jié)符A變成不可到達的符號,產(chǎn)生式也就變?yōu)槎嘤嗟?，所以?yīng)刪除.,此外也存在某些文法不能在有限步驟內(nèi)提取左公共因子。 例4: 若有文法G4的產(chǎn)生式: S Ap|Bq A aAp|d B aBq|e,SAp|Bq AaAp|d B aBq|e,SaApp|aBqq Sdp|eq AaAp|d B aBq|e,Sa(App|Bqq),SaS SApp|Bqq Sdp|eq AaAp|d B aBq|e,SaS Sdp|eq SaAppp|aBqqq Sdpp|eqq

26、 AaAp|d B aBq|e,SaS Sdp|eq SaS Sdpp|eqq SAppp|Bqqq AaAp|d B aBq|e,可以看出產(chǎn)生式A.B繼續(xù)替換，只能使文法的產(chǎn)生式愈來愈多無限增加下去，變成循環(huán)遞歸，不能得到提取左公共因子的預(yù)期結(jié)果。,上面例子說明： 不一定每個文法的左公共因子都能在有限的步驟內(nèi)替換成無左公共因子的文法。 一個文法提取了左公共因子后，只解決了相同左部產(chǎn)生式右部的FIRST集不相交問題，當改寫后的文法不含空產(chǎn)生式，且無左遞歸時，則改寫后的文法是LL(1)文法。否則還需用LL(1)文法的判別方式進行判斷才能確定是否為LL(1)文法。,2、消除左遞歸,1. 一個文法含

27、有下列形式的產(chǎn)生式時， a) AA AVN, V* b) AB B A A,BVN, ， V* 稱為左遞歸文法。其中a)是直接遞歸，b)是間接遞歸。 如果一個 文法是左遞歸時，則不能采用自頂向下分析法。,例1：文法S Sa S b 是直接左遞歸,所產(chǎn)生的語言是：L ban | n0,輸入串：baaa#,例2： 文法為：AaB ABb BAc Bd,是間接左遞歸, 消除左遞歸的變換方法：,(1) 消除直接左遞歸： 方法：改為右遞歸。如 SSa 改寫為： Sb S Sb Sa S|,輸入串：adbcbcbc#,(2) 消除間接左遞歸： 方法：間接左遞歸直接左遞歸右遞歸,例3：文法G6為: AaB

28、ABb BAc Bd,AaB ABb BaBc BBbc Bd,BaBc|d BBbc,B(aBc|d)B BbcB|,AaB ABb B(aBc|d)B Bbc B|,對文法中一切左遞歸的消除要求文法中不含回路，即無AA的推導(dǎo)。 滿足該文法的充分條件是：文法中不包含形如AA的有害規(guī)則和A的產(chǎn)生式。,四、不確定的自頂向下分析思想,假定要被代換的最左非終結(jié)符號是B，且有n條規(guī)則：BA1|A2|An，那么如何確定用哪個右部去替代B？ LL(1)文法：確定的自頂向下分析法：根據(jù)規(guī)則的選擇集合來確定。 非LL(1)文法：不確定的自頂向下分析法帶回溯的自頂向下分析法 “不確定”的意思：當某個非終結(jié)符的產(chǎn)

29、生式有多個候選，而面臨當前的輸入符號無法確定選用哪個產(chǎn)生式，從而引起回溯。,下面講三個例子說明回溯：,1、由于相同左部的產(chǎn)生式的右部First集交集不為空而引起回溯。,例：文法SxAy Aab|a 求輸入串為xay語法樹。,例：文法SxAy Aab|a 求輸入串為xay語法樹。,first(ab)與first(a)的交集不為空,a,b,a,回溯,SxAy,若選擇Aab，就于xay不匹配,回溯，用Aa就匹配,2、由于相同左部非終結(jié)符的右部能，且該非終結(jié)符Follow集中含有其右部First集的元素而引起回溯。,例：S aAS |b A bAS | 求對輸入串a(chǎn)b#的推導(dǎo)樹。,*,2、由于相同左部

30、非終結(jié)符的右部能，且該非終結(jié)符Follow集中含有其右部First集的元素而引起回溯。,例：S aAS |b A bAS | 求對輸入串a(chǎn)b#的推導(dǎo)樹。,A Follow(A)=a,b first(bAs)=b,b,A,S,回溯,b,*,3、由于文法含有左遞歸而引起回溯。,例：SSa Sb 若推導(dǎo)baa#,3、由于文法含有左遞歸而引起回溯。,例：SSa Sb 若推導(dǎo)baa#,S,b,回溯,b,回溯,b,消除左遞歸后，再試一遍,3、由于文法含有左遞歸而引起回溯。,例：SbS SaS S 若推導(dǎo)baa#,由以上例子可以看出：帶回溯的自頂向下分析是一個試探過程，當分析不成功時則推翻分析，退回到適當位

31、置再重新試探其余可能的推導(dǎo)。 因此，需要記錄所選過的產(chǎn)生式，直到把所有可能的推導(dǎo)序列都試完仍不成功，才能確認輸入串不是該文法的句子。（為證明輸入串不合法，需要窮舉或遍例所有的推導(dǎo)） 編譯程序真正實現(xiàn)時往往邊分析邊插入語義動作，因而帶回溯分析代價很高，效率很低，在實用編譯程序中幾乎不用。,五、確定的自頂向下分析方法,1、遞歸子程序法： 要求文法滿足LL(1)文法。是比較簡單直觀易于構(gòu)造的一種語法分析方法。 PL/0編譯程序的語法分析部分就是采用的遞歸子程序法。 基本思想是：對應(yīng)文法中每個非終結(jié)符編寫一個遞歸過程，每個過程的功能是識別由該非終結(jié)符推出的串。,例：遞歸子程序?qū)崿F(xiàn) 表達式的語法分析,表

32、達式的EBNF表達式=+|-項（+|-）項項=因子（*|/）因子因子=ident|number|（表達式）,表達式=+|-項（+|-）項 procedure expr;begin if sym in plus, minus then begin getsym; term; endelse term; while sym in plus, minus do begin getsym; term; endend;,項=因子（*|/）因子 Procedure term; begin factor; while sym in times,slash do begin getsym;factor end

33、 end;,因子=ident|number|（表達式） Procedure factor; begin if sym=ident then getsym else if sym=number then getsym else if sym=( then begin getsym; expr; if sym=) then getsym else error end else error end;,五、確定的自頂向下分析方法,2、預(yù)測分析方法： 自頂向下分析的另一種方法 預(yù)測分析器的組成：,預(yù)測分析程序 先進后出棧 預(yù)測分析表與文法有關(guān),預(yù)測分析表可用一個矩陣表示。矩陣元素MA,a中的A表示非終結(jié)

34、符， a表示終結(jié)符或句子結(jié)束符#，矩陣元素MA,a中的內(nèi)容是一條關(guān)于A的產(chǎn)生式，表明當用非終結(jié)符A向下推導(dǎo)時，面臨輸入符a時，所采用的候選產(chǎn)生式，當元素內(nèi)容無產(chǎn)生式時，表明用A為左部向下推導(dǎo)時遇到了不該出現(xiàn)的符號，因此元素內(nèi)容為轉(zhuǎn)向出錯處理。 如何構(gòu)造預(yù)測分析表？,79,79,() 構(gòu)造分析表,基本思想是: 當文法中某一非終結(jié)符呈現(xiàn)在棧頂時,根據(jù)當前的輸入符號,分析表應(yīng)指示要用該非終結(jié)符里的哪一條規(guī)則去匹配輸入串(即進行下一步最左推導(dǎo)) 根據(jù)這個思想,我們不難把構(gòu)造分析表算法構(gòu)造出來!,終結(jié)符號,非終結(jié)符號,表驅(qū)動的預(yù)測分析程序模型,(2)分析過程：,#S進棧，當前終結(jié)符送a,上托棧頂符號放入

35、X,XVT？,Xa？,X=#？,END,error,M(X,a)是 產(chǎn)生式嗎？,Xa？,error,若產(chǎn)生式為 Xx1x2xn 按逆序即 xnx2x1入棧,讀下一 個符號,y,y,y,n,n,n,y,y,n,n,82,82,執(zhí)行程序主要實現(xiàn)如下操作:,1.把#和文法識別符號E推進棧,并讀入輸入串的第一 個符a,重復(fù)下述過程直到正常結(jié)束或出錯.,2.測定棧頂符號X和當前輸入符號a,執(zhí)行如下操作:,(1)若X=a=#，分析成功，停止。E匹配輸入串成功. (2)若X=a#，把X推出棧，再讀入下一個符號。 (3)若XVn，查分析表M（詳細步驟見下頁）,83,83,(3)若XVn，查分析表M。 a) M

36、X,a= X=UVW 則將X彈出棧，將UVW壓入 注：U在棧頂 （最左推導(dǎo)） b) MX, a = error 轉(zhuǎn)出錯處理 c) MX, a = X:= -a為X的后繼符號 則將X彈出棧 （不讀下一符號） 繼續(xù)分析。,分析算法,BEGIN 首先把#然后把文法開始符號推入棧；把第一個輸入符號讀進a; FLAG：=TRUE； WHILE FLAG DO BEGIN 把棧頂符號上托出去并放在中； IF X Vt THEN IF X=a THEN 把下一個輸入符號讀進a ELSE ERROR ELSE IF X=# THEN IF X=a THEN FLAG:=FALSE ELSE ERROR ELS

37、E IF X,b=X X1X2.XK THEN 把XK，X K-1,.,X1一一推進棧 ELSEERROR END OF WHILE; STOP/*分析成功，過程完畢* END,預(yù)測分析表構(gòu)造算法,1.對文法G的每個產(chǎn)生式 執(zhí)行第二步 和第三步； 2.對每個終結(jié)符aFIRST()，把 加 至A,a中， 3.若 FIRST()，則對任何bFOLLOW(A) 把 加至A,b中， 4.把所有無定義的A,a標上“出錯標志”。 可以證明，一個文法G的預(yù)測分析表不含多重入口，當且僅當該文法是LL(1)的,(3)實例分析：給定文法，構(gòu)造預(yù)測分析表，并針對輸入串i+i*i#構(gòu)造預(yù)測分析過程。,例：文法為：E

38、E+T | T T T*F | F F i | (E) 步驟：,（1） 判斷文法是否為LL(1)文法。 如果文法中含有左遞歸，必須先消除左遞歸： （2）構(gòu)造預(yù)測分析表 ： Select(A ) （3）列出預(yù)測分析過程,S Sa S bS S b SaS| E E+T E T,(3)實例分析：給定文法，構(gòu)造預(yù)測分析表，并針對輸入串i+i*i#構(gòu)造預(yù)測分析過程。,例：文法為：E E+T | T T T*F | F F i | (E) 構(gòu)造步驟有：, 判斷文法是否為LL(1)文法。 由于文法中含有左遞歸，所以必須先消除左遞歸：,E E+T | T,E TE E +TE|,T T*F | F,TFT T*FT|,ETE E+TE| TFT T*FT| F i | (E),文法變?yōu)椋? 求First集合： First(E)= ( ，i First(E )= + ， First(T)= ( ，i First (T )= * ， First (F)= ( ，i ,ETE T不， E不 First(E)=first(T) =first(F)= ( , i ,求Follow集： Follow (E)= ，# Follow (E )= ，# Follow (T)= + ， ，# Follow (T )= + ， ，# Follow (F)