1、5.1 語法分析概述5.2 自頂向下語法分析概述5.3 LL分析法（預測分析法）5.4 遞歸子程序法 p413 附錄A 第五章 自頂向下語法分析方法1第5章 自頂向下語法分析 5.1 語法分析概述1.語法分析器的作用 詞法分析器語法分析器前端的其余部分源程序單詞取下一個單詞分析樹中間表示符號表2第5章 自頂向下語法分析 5.1 語法分析概述1.語法分析器的作用語法分析器主要作用有兩點：（1）根據(jù)詞法分析器提供的單詞流，為語法正確的輸入構造分析樹（或語法樹）。（2）檢查輸入中的語法（可能包括詞法）錯誤，并調(diào)用出錯處理器進行適當處理。 例如，對于C程序語句“IF (a10) b=5；”，詞法分析識

2、別出了IF、(、標識符、等單詞符號，而語法分析則要檢查這些單詞之間的搭配、結(jié)構是否正確。IF后面是否為(，(后面是否為正確的表達式等等。 3第5章 自頂向下語法分析 5.1 語法分析概述1.語法分析器的作用 語法分析是編譯過程的核心部分，它的主要任務是按照程序語言的語法規(guī)則，在詞法分析輸出的單詞符號串中識別出各類語法成分，同時進行語法檢查，為語義分析和代碼生成作準備。 執(zhí)行語法分析任務的程序叫語法分析程序或語法分析器。語 法分析器wS w * l 語 法分析器w自頂向下分析自底向上分析S w * r 45.1 語法分析概述2. 兩類語法分析方法（1）自頂向下分析方法 語法分析從頂部(樹根、文法

3、的開始符號)到底部(葉子、語言的終結(jié)符號)為輸入的符號串建立分析樹。 確定的自頂向下分析方法對文法要求比較嚴格，必須無二義性、且消除左遞歸和回溯。典型的方法是遞歸下降分析方法和LL分析方法。遞歸下降分析方法便于手工構造語法分析器。LL分析法便于用語法分析器的自動構造工具，自動構造語法分析器。52. 兩類語法分析方法（2）自底向上分析方法 語法分析從底部到頂部為輸入的符號串建立分析樹。最常見的LR分析方法采用的就是自底向上分析方法。 LR分析法能適應一大類文法，幾乎所有能用上下文無關文法描述的程序設計語言的語法分析，都可以用LR分析法進行語法分析，LR分析法在實際中有較強的適用性和廣泛的應用。

4、LR分析法便于用語法分析器的自動構造工具，自動構造語法分析器。當前應用最廣泛的工具之一是YACC系列。 無論采用哪種分析方法，語法分析都是自左向右地讀入符號。 5.1 語法分析概述63. 語法分析要點 （1）程序設計語言中的絕大部分語法特性屬于上下文無關的，因此語法分析是以上下文無關文法（CFG）作為程序設計語言語法分析的基礎。 屬于上下文有關的語法特性在語義分析階段檢查。5.1 語法分析概述73. 語法分析要點 （2）任何一個二義性文法不存在與其對應的語法分析器，因此需要為程序設計語言選擇能進行確定語法分析的非歧義文法。 對于自頂向下的語法分析而言，需要改造文法，使其無二義性、無左遞歸和回溯

5、，以便能進行確定的語法分析。 對于自底向上的LR語法分析方法，對某些二義性文法，可以人為地給出運算符的優(yōu)先性和結(jié)合性的規(guī)定，可以構造出比相應非二義性文法更優(yōu)越的LR分析器。 （3）語法分析最終為合法的輸入串建立與之匹配的語法樹。5.1 語法分析概述85.2 自頂向下語法分析概述 自頂向下的分析方法就是從文法的開始符號出發(fā)，按最左推導方式向下推導，試圖推出要分析的輸入串。 自頂向下分析常用的方法有：遞歸下降分析： 利用程序設計語言的遞歸函數(shù)實現(xiàn)，每個函數(shù)對應文法的一個非終極符。LL( 1 )分析：由一張預測分析表和一個總控程序組成。預測分析表給出了當面臨輸入符號時，運用到非終極符的推導所選用的產(chǎn)

6、生式。95.2 自頂向下語法分析概述 自頂向下語法分析確定的自頂向下語法分析（消除左遞歸和回溯）遞歸下降分析預測分析法（ LL (1) ）非確定的自頂向下語法分析 （帶回溯）105.2 自頂向下語法分析概述 遞歸下降分析方法實用性強，便于手工編寫語法分析器。LL (1)分析法在實際中不常用，但給出了一些重要、形式化的定義，用于指導歧義文法的改造、文法左遞歸和回溯的消除。為學習更強大和復雜的LR分析法做準備。11構造推導的關鍵問題 在構造最左推導的過程中,面對當前讀入的單詞符號a和當前被替換的非終極符A兩者,應該選擇A的哪條候選式去替換它(推導)。主要找出選擇一個非終極符號的候選式的方法; 在構

7、造最右推導的過程中,面對當前讀入的單詞符號a,已分析過的符號串中是否已構成一個產(chǎn)生式的右部，即句柄（可歸約） 。如果已構成句柄，即用相應的產(chǎn)生式左部(非終結(jié)符號)去替換它(歸約)，尋找句柄的方法。12構造最左推導（aabbaa) (1.自頂向下） SaASa A SbA SS baASaSbSAaaba aSbAS aabAS aabbaS aabbaa aAS S135.2.1 帶回溯的自頂向下語法分析 1.帶回溯的自頂向下語法分析實質(zhì) 帶回溯的自頂向下語法分析實質(zhì), 是一個反復使用不同的產(chǎn)生式, 進行試探以謀求匹配輸入串的過程。 該方法分析效率低, 在實際中并不適用, 但給出了自頂向下語法

8、分析的思想。145.2.1 帶回溯的自頂向下語法分析 1.帶回溯的自頂向下語法分析實質(zhì)例如： 文法GS S aAb A * | *利用自頂向下語法分析思想, 分析 a*b 是否是合法的句子。SaAb*(b) 試探失敗SaAb(a)SaAb*(c) 試探成功155.2.1 帶回溯的自頂向下語法分析 2.帶回溯的自頂向下語法分析面臨的問題問題(1): 出現(xiàn)回溯 由于文法中同一非終極符的各候選式有公共的左因子或隱含有公共的左因子，使得推導無法選擇唯一的候選式，導致盲目試探。問題(2):左遞歸問題 無論是直接左遞歸的， 還是間接左遞歸的，都會使分析過程無法終止。例如 U U 用于最左推導:U U U

9、U 16思考 1、自上而下分析能否分析所有的上下文無關文法？一、上下文無關文法的特性自嵌入性：一個文法G是自嵌入的，若存在一個非終極符A，有A * A ， 、V+非空判斷1：自嵌入文法描述的語言一定不是正則語言。 （錯） 2：非自嵌入文法不可能產(chǎn)生2型語言。 （對）172、為何選用CFG描述編程語言的語法規(guī)則？ CFG作為語言的語法描述有明顯的優(yōu)點:1.CFG對程序可給出精確易懂的描述2.從描述語言的文法，可自動構造出可用的分析程序3.在語言的語法描述之中，可方便地插入相關的語義描述，進行語法制導的語義翻譯思考18二、上下文無關語言的識別裝置：Push Down Automata1 定義：下推

10、自動機 PDA（等價于帶有下推棧的FA）PDA是一個六元組（K, , , f, S, Z0） 其中：K：狀態(tài)的有窮非空集 ：有窮輸入字母表 ：下推字母表，即棧符號的有窮集 f：K 到K的一個映射 SK是開始狀態(tài) Z0：棧中初始下推符號（可標記何時終止）19二、上下文無關語言的識別裝置：Push Down Automata例1. PDA識別成對的括號串,可由 G: SS(S) | 產(chǎn)生。（確定）PDA定義如下：M = ( A, “(”, “)”, 0, I), f, A, I)其中：(1) f ( A,I,“(” ) =(A, I0)(2) f ( A,0,”(” ) =(A, 00)(3) f

11、 ( A,0,”)” ) =(A, )(4) f ( A, I, ) =(A, )20二、上下文無關語言的識別裝置：Push Down AutomataCFL有一種等價的自動機記號，即“下推自動機”。它描述并且只描述所有的CFL，作為一種語言的定義機制是非常有用的（它與CFG等價性）()( () )控制I21例2. 識別語言XX-1 | X 0, 1*, X-1: X的逆串由下列文法產(chǎn)生：S 0S0 | 1S1 | PDA（該PDA是不確定PDA）如下定義：M=(A,B, 0,1, I,0,1, f, A, I)其中： (1) f(A, I, 0)=(A ,I0) (2) f(A, I, 1)

12、=(A, I1) (3) f(A, 0, 1)=(A, 01) (4) f(A, 1, 0)=(A, 10)(5) f(A,0,0)=(A,00), (B, ) (6) f(A, 1, 1)=(A, 11), (B, ) (7) f(B, 0, 0)=(B, ) (8) f(B, 1, 1)=(B, ) (9) f(B, I, )=(B, ) (10) f(A, I, )=(A, ) 狀態(tài)A對應讀串的前一半，狀態(tài)B對應讀串的后一半。讀前一半時，將所讀符號置于棧頂；讀后一半時，邊讀邊與棧頂符號比較，相等則移掉棧頂符號，否則出錯。22二、上下文無關語言的識別裝置：Push Down Automat

13、a 2.定理（1）每一個CFG，都對應一個PDA M，使L(M)=L(G)（2）存在一個PDA，它識別的語言不能被任何確定的PDA識別。 歸納：對上下文無關語言的分析，并不總是能以確定的方式進行，需要回溯。23二、上下文無關語言的識別裝置：Push Down Automata 小 結(jié) 1.能夠進行確定分析的語言稱為確定語言。大多數(shù)的編程語言是確定的語法分析的任務：有效地模擬PDA2.固有歧義的語言：就是根本不存在非歧義文法的語言。文法的非歧義性是不可判定的只有文法是非歧義的，語法分析才可唯一進行雖然不存在算法能在有窮步內(nèi)確定任意文法是否歧義，但對某些具體文法存在判定算法如：LL文法和LR文法，

14、可證是非歧義文法，并且存在算法，能檢查一文法是否是LL或LR文法24三、自上而下的分析方法1.主旨：從文法的S出發(fā)，反復使用各種產(chǎn)生式，尋找”匹配”于輸入符號串的推導（從S（根）出發(fā)，向下逐步建立語法樹，最終：為輸入串尋找一個最左推導）例1 GS: (1)ScAd | dBa (2) Aab (3) Aa (4) Bcd | c, 則cad是否為文法的句子SdScAScdAabScdAadcda dcdc 是不是分析過程是一個試探過程，必須一一試探所有候選式，直至與輸入串匹配成功，或者判定輸入串不是正確句子。25三、自上而下的分析方法2. 自上而下分析面臨的主要問題 1） 如何選擇候選式如果對

15、文法不做任何限制，對候選式的選擇成為無根據(jù)的，只好一一試探所有候選式，直至成功或失敗。致命弱點：不斷地回溯，大大影響速度。2）左遞歸文法將使自上而下分析陷入無限循環(huán)例、S Sa | b，若推導baaSSaSaSa263. 自上而下分析法的問題及解決Q1: 回溯低效、耗時，對高度遞歸的語言，無法接受。解決方案： 對文法加以一定的限制，使每次對候選式的選擇是唯一的，從而進行確定的自上而下分析。 如：LL（1）文法。（詳見5.3節(jié)）273. 自上而下分析法的問題及解決Q2：左遞歸文法將使自上而下分析陷入無限循環(huán) 1.重排規(guī)則順序 （解決方法1） 例S Sa | b, 改為： S b | Sa ，若推

16、導baaSb(不行)SSab（不行）SSabSa2.將左遞歸右遞歸（或迭代） （解決方法2） 如：上例生成語言 L = ba* 右遞歸文法：S bA A aA | 281.消除直接左遞歸AA|, , (VNVT)*, A VN, 不以A開頭則：A A A A | 或 A 例 文法 E E+T | T 或 E T+T （迭代） T T*F | F T F*F F (E) | a F (E) | a 消除左遞歸，得 E TE E +TE | T FT T *FT | F (E) | a5.2.2 消除左遞歸291.消除直接左遞歸若關于A的全部規(guī)則為 A A1 | A2 | | Am | 1 | 2

17、 | | n 其中， 每個i都不等于 ，每個i都不以A開頭則消除左遞歸，得 A (1 | 2 | | n )A A (1 | 2 | | m )A | 或 A (1 | 2 | | n )1 | 2 | | m 迭代 5.2.2 消除左遞歸302.消除間接左遞歸例 GS： S Qc | c Q Rb | b R Sa | a因 S Qc Rbc Sabc, 是左遞歸文法代入法： S (Rb | b)c | c S Rbc | bc | c S (Sa | a)bc | bc | c所以 S Sabc | abc | bc | c消除左遞歸，得 S abcS | bcS | cS S abcS

18、| 5.2.2 消除左遞歸315.3 LL分析法（預測分析法）5.3.1 概述5.3.2 LL(1)文法5.3.3 文法的變換5.3.4 LL(1)分析器325.3.1 LL分析概述兩類確定的自頂向下分析方法（1）遞歸下降法 （2）LL (K)方法1. LL(K)含義 從左（L）到右（R）掃描輸入串，并建立它的最左推導。 K：在選擇同一非終極符的不同規(guī)則時，通過向前看K個符號決定。LL(K)文法： 是非歧義文法中能構造出確定的自頂向下分析器的最大文法類。LL分析器又稱預測分析器，是PDA特例。332. 預測分析方法 自頂向下分析是從文法的開始符號出發(fā)，試構造出一個最左推導，從左至右匹配輸入的單

19、詞符號串。 如果在每步推導中，面對被替換的非終結(jié)符號A和當前從左至右讀入輸入串讀到的單詞符號a，如果A的定義（無-產(chǎn)生式） A1 |2 | |n 中，只有i（1in)推導出的第一個終極符號是a，那么，就可以用產(chǎn)生式Ai構造最左推導，即用i替換A。342. 預測分析方法一類簡單文法的分析器工作過程：(1) 定義 G為S-文法，當且僅當它滿足： 每條規(guī)則的右部都以VT開頭 如果一個VN有多條規(guī)則，那么它們都以不同的VT開頭例1 S aS | bA, A d | ccA 叫做預測分析矩陣（表），LL分析表Mabcd#SaSbAAccAd352. 預測分析方法對于上例，在推導過程中，完全可以根據(jù)當前的

20、向前看符號決定選擇哪個產(chǎn)生式進行推導，因此，分析過程是完全確定的。這種分析稱為自頂向下的預測分析。 原因在于，文法中，AVN, A12. n i,j (1i, j n ij)從 i推導出來的第一個終結(jié)符號集合（稱為FIRST( i) ）和從 j推導出來的第一個終結(jié)符號集合（稱為FIRST( j) ）是不相交的，即： FIRST( i) FIRST( j)=36（2）分析器（預測分析器PDA特例）分析器的動作總是由 棧頂元素X 當前輸入符號aabccd#決定的S#控制（總控程序）預測分析表1 2 4 3預測分析器預分析串輸入帶下推棧初始：# S其中，#棧底 S開始符保存用過的文法規(guī)則（即：左分析

21、）輸出帶37（2）分析器（預測分析器PDA特例）分析器的動作有3種：1.若棧頂符號是一個非終極符，則去查分析表MX, aMX, a是一文法規(guī)則X ，則用去替換棧頂?shù)腦（ 逆序推入棧中），并輸出文法規(guī)則編號MX, a無定義，則報錯并轉(zhuǎn)錯誤處理程序均不讀下一符號（相當于進行了一次最左推導）2.若棧頂符號X是一個終極符且X=a，則將棧頂符號彈出，并讀下一個符號，若XVT,且Xa，則err3.若X=“#”=a，則分析器停機，輸入串被接受385.3.2 LL(1)文法對于LL(k)文法，K=1最常見，只需根據(jù)棧頂符號X和當前輸入符號a，即可確定用哪條規(guī)則進行推導。（一）串(VNVT)*的FIRST集開頭

22、符號集 FIRST()=a| *a, a VT, , V* 若 *, 則 FIRST()定義1：設G是不帶規(guī)則的文法，若對所有 A 1 | 2 | | n的規(guī)則，有FIRST(i) FIRST(j)=,ij，則G為LL(1)文法。395.3.2 LL(1)文法下面討論有規(guī)則的文法。LL(1)條件？例2: (1) S aA (2) S d (3) A bAS (4) A 若對abd串，S aA abAS abSabd何時選用A 的空規(guī)則？SaASaAbASSaAbASSaAbASd參見語法樹 在分析時，只有見到它的后繼符號才能決定使用這條規(guī)則引進跟隨集405.3.2 LL(1)文法(二)每個非終

23、極符的Follow集規(guī)定 “#”屬于開始符號S的Follow集，#是句子結(jié)束符。Follow集定義：若G=(VN,VT,P,S)是CFG，A VN，F(xiàn)ollow(A)=a | S * A, aFirst(), V+，即: 句型中緊跟在A后面的那些終極符若 * ,則# Follow(A)；換句話說：若S * A，則規(guī)定# Follow(A)。415.3.2 LL(1)文法(二)每個非終極符的FOLLOW集定義2：一個文法G是LL(1)文法，當且僅當對文法中形如A 1 | 2 | | n都滿足LL(1)條件，即(1) First(i) First(j)=, ij； 且如果i * ,則(2) Fir

24、st(j) Follow(A)=, ij為簡化LL(1)條件，引進選擇集 Select(A )42第5章 自頂向下語法分析 5.3.2 LL(1)文法（ 三）每條規(guī)則的select集 select( A)=First() , 當不能推出Follow(A) (First() ) , 當*利用select集判斷LL(1)文法:定義3：一個文法G是LL(1)文法，當且僅當對文法中的所有形如 A1| 2| n 的產(chǎn)生式, 其各候選式都滿足如下的條件： select( Ai) select( Aj) = (對所有ij)435.3.2 LL(1)文法 LL(1)條件： 一個上下文無關文法G，對其所有形如A

25、 1 | 2 | | n的規(guī)則： select(A i) select(A j) =, ij只要一個CFG滿足LL(1)條件，就是LL(1)文法，能采用預測分析法進行確定的自頂向下分析。對不同的LL(1)文法，其預測分析器的總控程序完全一樣。不同僅在于分析表不同。445.3.2 LL(1)文法 LL(1)文法的定義 LL(1)的含義： 按自左向右的順序掃描輸入符號串，并按最左推導的方式進行推導。 “1”表示選擇同一非終極符的不同候選式時，是通過向前看一個輸入符號（即待匹配指針所指向的當前符號）決定的。 455.3.2 LL(1)文法 怎樣判斷一個文法是否為LL（1）文法？這類問題可以直接根據(jù)L

26、L(1)文法定義判斷，也可根據(jù)LL(1)分析表判斷。若LL(1)分析表中每一項沒有多重定義（即無二義性），就是LL(1) 文法。利用select集構造LL(1)分析表, 其元素MA,a按下述規(guī)則確定： (其中, AVN, aVT # ) 對于每個形如 A的產(chǎn)生式: 若 a select(A) , 則置 M A,a=“A” 否則置錯，用空白表示。46第5章 自頂向下語法分析 例1： 給定文法 S0S| 1S |是否為 LL(1) 文法？解： 構造LL(1)分析表: 01#SS0SS1SS 因為表中無多重定義， 所以該文法是 LL(1) 文法。 47第5章 自頂向下語法分析 例2： 給定文法 S0

27、S0| 1S1 |是否為 LL(1) 文法？解： 構造LL(1)分析表: 01#SS0S0S S1S1S S 因為表中出現(xiàn)多重定義， 所以該文法不是 LL(1) 文法。 48第5章 自頂向下語法分析 例3: 左遞歸文法是LL（1）文法嗎？解：因為左遞歸文法意味著有隱含的左公共因子，所以左遞歸文法不是LL（1）文法。 例如： AAa | b 因為：First(Aa=b，F(xiàn)irst(b)=b， 所以 First(Aa First(b)495.3.2 LL(1)文法 關鍵：如何計算FOLLOW集 FOLLOW集的計算 (a) 設S為G中開始符號，則#FOLLOW(S)(b) 若A B是一產(chǎn)生式，則把

28、FIRST()的非空元素加入到FOLLOW(B)中。 如果 * ，則把FOLLOW(A)也加入到FOLLOW(B)中(c) 反復使用(b)，直到每個VN的FOLLOW集不再增大為止。50例4 判斷G是否是LL(1)文法，如果是，構造LL(1)分析表GS1. S AB2. S bC3. A 4. A b5. B 6. B aD7. C AD8. C b9. D aS10. D c(1)求VN的First集、 Follow集FIRSTFOLLOWSb,a, #Ab, #,a,cBa, #Cb,a, c#Da,c#(2) select(S AB)=b,a,# select(S bC)=b, 相交，不

29、是LL(1)文法同理：select(A )=#, a, c select(B )=# select(C AD)=b,a,c select(C b)=b相交教材P7951第5章 自頂向下語法分析 5.3.3 文法的變換 預測分析法是一種確定的自頂向下的語法分析，它要求文法必須是LL（1）形式。 某些非LL（1）文法，經(jīng)過變換后，有可能改造成LL（1）文法。1.左遞歸文法的變換 左遞歸文法必然不是LL（1）文法。經(jīng)過消除左遞歸的變換后，新的文法不一定是LL（1）文法，需進一步利用LL（1）文法的條件進行判斷。 52第5章 自頂向下語法分析 5.3.3 文法的變換1.左遞歸文法的變換例：給定文法GS

30、： S i | (E) EE+S | E-S | S（1）求每一非終極符的First集和Follow集。（2）判斷該文法是否為LL（1）文法，為什么？能否進行文法變 換成為LL（1）文法？若能，給出LL（1）分析表。53 1.左遞歸文法的變換例：給定文法GS： S i|(E) EE+S|E-S|S（1）求每一非終極符的 First集和Follow集。FirstFollowSi, (#, ), +, -Ei, ( ), +, -(2)因為該文法是左遞歸文法，所以不是LL(1）文法。 變換左遞歸文法：EE（+S | -S）| SE SE E（+S | -S）E | GS :S i|(E) E SE

31、 E+SE|-SE|54（3）求文法GS的每一非終極符的First集和Follow集。(4)文法GS的LL（1）分析表 FirstFollowSi,(#, ), +, -Ei,( )E+,-, )i+-()#Si(E)ESESEE+SE-SE GS :S i|(E) E SE E+SE|-SE|因為LL（1）分析表無多重定義，所以變換后的文法GS是LL（1）文法。55第5章 自頂向下語法分析 5.3.3 文法的變換2.提取左公共因子變換 含有左公共因子的文法肯定不是LL（1）文法，經(jīng)過提取左公共因子變換后（可能這種變換需多次進行），新文法也不一定是LL（1）文法，還需進一步由LL（1）條件判定

32、。56 2.提取左公共因子變換 例：變換下列文法GS：S aSb|aSc|，并判斷是否為LL(1)文法。解: 提取左公共因子變換: S aS（b|c）| 令: B b|c 變換后的文法: GS： S aSB| B b|c GS :Select(S aSB)=aSelect(S )=b,c,#Select(B b)=bSelect(B c)=c具有相同左部的產(chǎn)生式的Select集兩兩不相交，故GS 為LL（1）文法。 57 2.提取左公共因子變換 思考題：能否通過文法變換，將下面文法轉(zhuǎn)換為LL(1)文法。 S iBtSeS | iBtS | a B b解：S iBtSS | a S eS | B

33、 b因為 select(S )=#, e ，與e是相交的，不滿足LL（1）條件所以不是LL(1)文法itaeb#SiBtSSaSS eSS S 583. 角替換 角：一規(guī)則右部的最左出現(xiàn)，稱為規(guī)則的角。如： ScS | Ac 角替換：對一規(guī)則的非終極符的角，用其規(guī)則右部去替換它。 非終極符角的出現(xiàn)意味著左公共因子可能是隱式的。消除隱式左公共因子的辦法可采用角替換。角替換與提取左公共因子往往同時進行。 角替換是一種輔助手段,用于發(fā)現(xiàn)隱含的左遞歸、左公共因子。角替換本身不改變文法的LL（1）性質(zhì)。593. 角替換 例: 下列文法是否可變換為LL（1）文法？ 文法GS：ScS | Ac AaS |

34、b解：產(chǎn)生式S Ac 中含有角A，角替換為：SaSc | bc 由于GS中非終極符A變成不可達符號，所以產(chǎn)生式 AaS|b應予以刪除。 改造后的文法GS : ScS | aSc | bcSelect(ScS )=c Select(SaSc)=a Select(Sbc )=b 顯然, 具有相同左部的產(chǎn)生式的Select集兩兩相交為空， 故為LL（1）文法。 60例：S Ap | Bq, A aAp | d, B aBq | e解：角替換 S (aAp | d)p | (aBq | e)q即： S aApp | aBqq | dp | eq A aAp | d, B aBq | e對S變換，S a

35、S | dp | eq S App | Bqq對S角替換， S (aAp | d)pp | (aBq | e)qq再提取左因式，S aS | dpp | eqq S Appp | Bqqq繼續(xù)重復，仍然有左因式。61第5章 自頂向下語法分析 5.3.3 文法的變換 關于文法變換，有下面的結(jié)論： 存在某些文法，不能在有限步驟內(nèi)提取完左公共因子。 一個文法經(jīng)變換后，沒有空產(chǎn)生式，且無左遞歸時，則改寫后的文法是LL（1）文法，否則需進一步用LL(1)條件判斷。 LL（1）文法通過角替換后，保留LL（1）性質(zhì)。 文法變換可能會使某些產(chǎn)生式變成無用產(chǎn)生式，即伴隨著對文法的化簡。62第5章 自頂向下語法分

36、析 5.3.4 LL(1)分析器 LL（1）分析器是由一張LL（1）分析表，一個控制程序和一個分析棧組成。分析棧中存放文法符號。 LL（1）分析器模型如圖所示： #S分析棧a1a2aian輸入數(shù)據(jù)LL（1）分析器 LL（1）分析表輸出最左推導規(guī)則序列63第5章 自頂向下語法分析 5.3.4 LL(1)分析器 # S分析器初態(tài):如圖所示, 分析棧中壓入“#”和文法開始符號S，棧頂元素是S。待匹配指針指向輸入串的第一個待匹配符. a1a2aian64 5.3.4 LL(1)分析器 例: 以輸入串 i+i*i 為例,給出用LL(1)分析器識別符號串的過程.文法GE: ETE E+TE| TFT T*

37、FT| Fi|(E) 解:(1)求非終極符的First集和Follow集 FirstFollowEi, (#, )E+ , #, )Ti, (+, #, )T* , +, #, )Fi, (+, #, ), *65文法GE: ETE E+TE| TFT T*FT| Fi|(E) 解:(1)FirstFollowEi,(#, )E+,#, )Ti,(+, #, )T*,+, #, )Fi, (+, #, ), *(2) 求LL(1)分析表+*i（）#ETETEE+TETFTFTT*FTFi(E)66ETE E+TE| TFT T*FT| Fi|(E) 解:+*i（）#ETETEE+TETFTFT

38、T*FTFi(E)步驟分析棧余留輸入串產(chǎn)生式子12345678#E# ET# E TF# E T i# E T# E#ET+#ETi+i*i #i+i*i #i+i*i #i+i*i # +i*i # +i*i # +i*i # i*i #ETETFTFi匹配TE+TE匹配TFT剩余過程自己完成67第5章 自頂向下語法分析 5.4 遞歸子程序法 遞歸子程序法，又稱遞歸下降分析法。思想是：非終極符的文法規(guī)則可看成是識別該非終極符的過程定義，針對文法的每一非終極符，根據(jù)相應產(chǎn)生式各候選式的結(jié)構，為其編寫一個遞歸函數(shù)，用來識別該非終極符所表示的語法范疇。 遞歸下降分析法是一種確定的自頂向下的語法分析

39、方法，其分析過程是從文法開始符號出發(fā)，執(zhí)行一組遞歸過程，不斷向下推導，直到推出句子。 68第5章 自頂向下語法分析 為了構造遞歸子程序，有如下的約定和要注意的問題：(1)文法必須是LL（1）文法。 (2)待匹配符號串是要被分析的源程序，是用助記符或整數(shù)碼表示的單詞類別串。 例如待匹配符號串“ ID:=ID+NUM# ”，按從左向右掃描輸入串的順序，開始的時候，當前匹配指針指向的輸入符號是“ID”。 (3)設輔助函數(shù)getsym()的作用是讀取當前指針指向的待匹配符，并使待匹配指針向前移，指向下一個待匹配符。變量sym用來存儲當前匹配指針指向的輸入符號。 (4)進入子程序時已經(jīng)取到了當前的輸入符

40、號；從子程序返回時，也已經(jīng)取到了下一次準備匹配的輸入符號。 69第5章 自頂向下語法分析 為了構造遞歸子程序，有如下的約定和要注意的問題：(5) 如果遇到非終極符，則直接調(diào)用該非終極符對應的子程序。如果非終極符A的右部只有一個候選式，則按從左向右的順序依次構造A的識別過程。 如果遇到終極符，判斷是否與輸入的符號匹配。若匹配，則讀取下一個待匹配符號；如果匹配失敗，則意味著有語法錯誤。 (6)如果非終極符A的右部有多個候選式，則根據(jù)每個候選式的第一個符號確定識別非終極符A的流程控制轉(zhuǎn)向。70例：文法Z(U)| aUb ，U dZ|e，為其構造遞歸下降分析子程序。并對輸入串a(chǎn)eb進行語法分析 。第5

41、章 自頂向下語法分析 解： 文法中有兩個非終結(jié)符號Z和U，需要分別編兩個函數(shù)來完成Z和U規(guī)則的識別。 對于規(guī)則Z(U)|aUb，右部有兩個候選式，因此，U的識別過程有兩個分支，分別根據(jù)符號( 和 a 來判別。 同理對規(guī)則UdZ|e 設計的過程也分為兩個分支。見圖(a)和(b)所示。71Z (U)|aUb圖(a) 非終結(jié)符號Z的分析程序 過程Zsym= getsym()U出口語法錯誤：輸入串少) sym =aYNNNNYY語法錯誤：輸入串少(、a語法錯誤：輸入串少b sym =(sym =)sym =bsym= getsym()sym= getsym()UY對輸入串a(chǎn)eb進行語法分析72U dZ

42、|e過程Usym= getsym()Z出口sym =eYNNY語法錯誤：輸入串少d、esym= getsym()Y圖(b) 非終結(jié)符號U的分析程序 sym =d對輸入串a(chǎn)eb進行語法分析73U dZ|e 每個非終結(jié)符對應的函數(shù)設計好后，就可以對輸入串進行語法分析。 假設輸入串為aeb, 從Z函數(shù)開始識別，由于sym不等于(，等于a，所以選擇Z函數(shù)的右邊分支，表示選擇了ZaUb規(guī)則。讀下一個符號，使sym=e; 調(diào)U函數(shù)，因sym=e，表示使用Ue 規(guī)則, 讀下一個符號，使sym=b，并返回調(diào)用程序Z函數(shù)右邊分支U的下方，接著判斷sym=b，讀下一個符號，并退出Z. 在主函數(shù)中判斷:若sym=#

43、,則分析過程結(jié)束，從而判定輸入串a(chǎn)eb語法分析成功。 這個過程相當于構造了如下推導過程：Z=aUb=aeb Z (U)|aUb對輸入串a(chǎn)eb#進行語法分析74例：為下列文法的每個非終極符構造相應的遞歸函數(shù) 文法GZ： Z(U) | aUb UdZ | e解： main( ) sym=getsym( ); /讀取當前輸入串的第一個符號 Z(); /從文法開始符號對應的子程序開始識別 if (sym=#) OK; /”#”是程序結(jié)束的標志 else error (“error in main”); 對輸入串a(chǎn)eb#進行語法分析75 Z() / Z(U) | aUb if(sym=( ) sym=g

44、etsym(); U(); if (sym ) ) error ( “缺 )” ) ; exit(0); else sym=getsym( ); else if(sym=a) sym=getsym( ); U(); if (sym b ) error ( “缺b” ) ; exit(0); else sym=getsym(); else error ( “缺 ( 或 a” ) ; exit(0);對輸入串a(chǎn)eb#進行語法分析76 U() / UdZ | e if(sym=d) sym=getsym(); Z(); else if(sym=e) sym=getsym( ); else error

45、 ( “缺 d 或 e” ) ; exit(0);對輸入串a(chǎn)eb#進行語法分析77例： 為下列文法的每個非終極符構造相應的遞歸函數(shù).文法GE： ETE E+TE| TFT T*FT| F i |(E)解： main( ) sym=getsym( ); /*讀取當前輸入串的第一個符號。*/ E( ); if(sym= =# ) OK; else error (“in main”); 78 E( ) / ETE if (sym= =i| sym= =( ) /* if (sym first (T) */ T(); E(); else error (“非法符號”, sym); exit(0);79

46、E() / E+TE| if (sym= =+) sym=getsym( ); T(); E(); else if (sym # sym ) ) /* if (sym follow (E) */ error (“非法符號”, sym); exit(0); /意味著用 E 推導80 T() / TFT if (sym= =i| sym= =( ) /* if (sym first (F) */ F(); T(); else error (“非法符號”, sym); exit(0);81 T() / T*FT| if (sym= =*) sym=getsym( ); F(); T(); else

47、if (sym# sym+sym)/ if (sym follow (T) error (“非法符號”, sym); exit(0); /意味著用T 推導82 F() / F i | (E) if (sym= =i) sym=getsym(); else if (sym= =() sym=getsym( ); E( ); if (sym= =) ) sym=getsym( ); else error ( “缺)” ); exit(0); else error( “缺（或i ”); exit (0);83例： 文法GE：EE+T | T TT*F | F Fi | (E)設計遞歸子程序。解: 對文法G消除左遞歸為G(E): E+|-T+T /考慮表達式有形如+5或-5的情況 TF*F Fi|(E) 84 E() /E +|- T+T if (sym = + | sym= -) sym=getsym(); if(sym = i | sym = ( ) T(); else error; exit(0); else if (sym