編譯原理：第5章 自頂向下語(yǔ)法分析方法-2013

1、5.1 語(yǔ)法分析概述5.2 自頂向下語(yǔ)法分析概述5.3 LL分析法（預(yù)測(cè)分析法）5.4 遞歸子程序法 p413、p429第五章 自頂向下語(yǔ)法分析方法15.1 語(yǔ)法分析概述1.語(yǔ)法分析器的作用 詞法分析器語(yǔ)法分析器前端的其余部分源程序單詞取下一個(gè)單詞分析樹(shù)中間表示符號(hào)表2（1）根據(jù)詞法分析器提供的單詞流，為語(yǔ)法正確的輸入構(gòu)造分析樹(shù)（或語(yǔ)法樹(shù)）。（2）檢查輸入中的語(yǔ)法（可能包括詞法）錯(cuò)誤，并調(diào)用出錯(cuò)處理器進(jìn)行適當(dāng)處理。 例如，對(duì)于C程序語(yǔ)句“IF (a10) b=5；”，詞法分析識(shí)別出了IF、(、標(biāo)識(shí)符、等單詞符號(hào)，而語(yǔ)法分析則要檢查這些單詞之間的搭配、結(jié)構(gòu)是否正確。IF后面是否為(，(后面是否為

2、正確的表達(dá)式等等。 5.1 語(yǔ)法分析概述1.語(yǔ)法分析器的作用 3 語(yǔ)法分析是編譯過(guò)程的核心部分，它的主要任務(wù)是按照程序語(yǔ)言的語(yǔ)法規(guī)則，在詞法分析輸出的單詞符號(hào)串中識(shí)別出各類語(yǔ)法成分，同時(shí)進(jìn)行語(yǔ)法檢查，為語(yǔ)義分析和代碼生成作準(zhǔn)備。 執(zhí)行語(yǔ)法分析任務(wù)的程序叫語(yǔ)法分析程序或語(yǔ)法分析器。語(yǔ) 法分析器wS w * l 語(yǔ) 法分析器w自頂向下分析自底向上分析S w * r 5.1 語(yǔ)法分析概述1.語(yǔ)法分析器的作用 42. 兩類語(yǔ)法分析方法（1）自頂向下分析方法 語(yǔ)法分析從頂部(樹(shù)根、文法的開(kāi)始符號(hào))到底部(葉子、語(yǔ)言的終結(jié)符號(hào))為輸入的符號(hào)串建立分析樹(shù)。 確定的自頂向下分析方法對(duì)文法要求比較嚴(yán)格，必須無(wú)二

3、義性、且消除左遞歸和回溯。典型的方法是遞歸下降分析方法和LL分析方法。遞歸下降分析方法便于手工構(gòu)造語(yǔ)法分析器。LL分析法便于用語(yǔ)法分析器的自動(dòng)構(gòu)造工具，自動(dòng)構(gòu)造語(yǔ)法分析器。5.1 語(yǔ)法分析概述52. 兩類語(yǔ)法分析方法（2）自底向上分析方法 語(yǔ)法分析從底部到頂部為輸入的符號(hào)串建立分析樹(shù)。最常見(jiàn)的LR分析方法采用的就是自底向上分析方法。 LR分析法能適應(yīng)一大類文法，幾乎所有能用上下文無(wú)關(guān)文法描述的程序設(shè)計(jì)語(yǔ)言的語(yǔ)法分析，都可以用LR分析法進(jìn)行語(yǔ)法分析，LR分析法在實(shí)際中有較強(qiáng)的適用性和廣泛的應(yīng)用。 LR分析法便于用語(yǔ)法分析器的自動(dòng)構(gòu)造工具，自動(dòng)構(gòu)造語(yǔ)法分析器。當(dāng)前應(yīng)用最廣泛的工具之一是YACC系列

4、。 無(wú)論采用哪種分析方法，語(yǔ)法分析都是自左向右地讀入符號(hào)。 5.1 語(yǔ)法分析概述63. 語(yǔ)法分析要點(diǎn)（1）程序設(shè)計(jì)語(yǔ)言的絕大部分語(yǔ)法特性屬于上下文無(wú)關(guān)的， 因此語(yǔ)法分析是以上下文無(wú)關(guān)文法（CFG）作為程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析的基礎(chǔ)。 屬于上下文有關(guān)的語(yǔ)法特性在語(yǔ)義分析階段檢查。5.1 語(yǔ)法分析概述73. 語(yǔ)法分析要點(diǎn) （2）任何一個(gè)歧義文法不存在與其對(duì)應(yīng)的語(yǔ)法分析器，因此需要為程序設(shè)計(jì)語(yǔ)言選擇能進(jìn)行確定語(yǔ)法分析的非歧義文法。 對(duì)于自頂向下的語(yǔ)法分析而言，需要改造文法，使其無(wú)二義性、無(wú)左遞歸和回溯，以便能進(jìn)行確定的語(yǔ)法分析。 對(duì)于自底向上的LR語(yǔ)法分析方法，對(duì)某些二義性文法，可以人為地給出運(yùn)算符的優(yōu)

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

6、分析預(yù)測(cè)分析法（ LL (1) ）非確定的自頂向下語(yǔ)法分析 （帶回溯）105.2 自頂向下語(yǔ)法分析概述 遞歸下降分析方法實(shí)用性強(qiáng)，便于手工編寫(xiě)語(yǔ)法分析器。LL (1)分析法在實(shí)際中不常用，但給出了一些重要、形式化的定義，用于指導(dǎo)歧義文法的改造、文法左遞歸和回溯的消除。為學(xué)習(xí)更強(qiáng)大和復(fù)雜的LR分析法做準(zhǔn)備。11構(gòu)造推導(dǎo)的關(guān)鍵問(wèn)題 在構(gòu)造最左推導(dǎo)的過(guò)程中，面對(duì)當(dāng)前讀入的單詞符號(hào)a和當(dāng)前被替換的非終極符A，應(yīng)該選擇A的哪條候選式去替換它(推導(dǎo))。 主要找出選擇一個(gè)非終極符號(hào)的候選式的方法。 在構(gòu)造最右推導(dǎo)的過(guò)程中，面對(duì)當(dāng)前讀入的單詞符號(hào)a，已分析過(guò)的符號(hào)串中是否已構(gòu)成一個(gè)產(chǎn)生式的右部，即句柄（可歸約

7、） 。如果已構(gòu)成句柄，即用相應(yīng)的產(chǎn)生式左部(非終結(jié)符號(hào))去替換它(歸約)。 關(guān)鍵：尋找句柄的方法。12構(gòu)造最左推導(dǎo)（aabbaa) (1.自頂向下） SaASa A SbA SS baASaSbSAaaba aSbAS aabAS aabbaS aabbaa aAS S135.2.1 帶回溯的自頂向下語(yǔ)法分析 1.帶回溯的自頂向下語(yǔ)法分析實(shí)質(zhì) 帶回溯的自頂向下語(yǔ)法分析實(shí)質(zhì), 是一個(gè)反復(fù)使用不同的產(chǎn)生式, 進(jìn)行試探以謀求匹配輸入串的過(guò)程。 該方法分析效率低, 在實(shí)際中并不適用, 但給出了自頂向下語(yǔ)法分析的思想。145.2.1 帶回溯的自頂向下語(yǔ)法分析 1.帶回溯的自頂向下語(yǔ)法分析實(shí)質(zhì)例如： 文法

8、GS S aAb A * | *利用自頂向下語(yǔ)法分析思想, 分析 a*b 是否是合法的句子。SaAb*(b) 試探失敗SaAb(a)SaAb*(c) 試探成功155.2.1 帶回溯的自頂向下語(yǔ)法分析 2.帶回溯的自頂向下語(yǔ)法分析面臨的問(wèn)題問(wèn)題(1): 出現(xiàn)回溯 由于文法中同一非終極符的各候選式有公共的左因子或隱含有公共的左因子，使得推導(dǎo)無(wú)法選擇唯一的候選式，導(dǎo)致盲目試探。問(wèn)題(2):左遞歸問(wèn)題 無(wú)論是直接左遞歸的， 還是間接左遞歸的，都會(huì)使分析過(guò)程無(wú)法終止。例如 U U 用于最左推導(dǎo):U U U U 16 一、上下文無(wú)關(guān)文法的特性自嵌入性：一個(gè)文法G是自嵌入的，若存在一個(gè)非終極符A，有A *

9、A ， 、V+非空判斷：自嵌入文法描述的語(yǔ)言一定不是正則語(yǔ)言。 （錯(cuò)）思考： 1、自上而下分析能否分析所有的上下文無(wú)關(guān)文法？2、為何選用CFG描述編程語(yǔ)言的語(yǔ)法規(guī)則？172、為何選用CFG描述編程語(yǔ)言的語(yǔ)法規(guī)則？ CFG作為語(yǔ)言的語(yǔ)法描述有明顯的優(yōu)點(diǎn):1.CFG對(duì)程序可給出精確易懂的描述2.從描述語(yǔ)言的文法，可自動(dòng)構(gòu)造出可用的分析程序3.在語(yǔ)言的語(yǔ)法描述之中，可方便地插入相關(guān)的語(yǔ)義描述，進(jìn)行語(yǔ)法制導(dǎo)的語(yǔ)義翻譯18二、上下文無(wú)關(guān)語(yǔ)言的識(shí)別裝置：Push Down Automata1 定義：下推自動(dòng)機(jī) PDA（等價(jià)于帶有下推棧的FA）PDA是一個(gè)六元組（K, , , f, S, Z0） 其中：K：

10、狀態(tài)的有窮非空集 ：有窮輸入字母表 ：下推字母表，即棧符號(hào)的有窮集 f：K 到K的一個(gè)映射 SK是開(kāi)始狀態(tài) Z0：棧中初始下推符號(hào)（可標(biāo)記何時(shí)終止）19二、上下文無(wú)關(guān)語(yǔ)言的識(shí)別裝置：Push Down Automata例1. PDA識(shí)別成對(duì)的括號(hào)串,可由 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 ( A,0,”)” ) =(A, )(4) f ( A, I, ) =(A, )20二、上下文無(wú)關(guān)語(yǔ)言

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

12、0)(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對(duì)應(yīng)讀串的前一半，狀態(tài)B對(duì)應(yīng)讀串的后一半。讀前一半時(shí)，將所讀符號(hào)置于棧頂；讀后一半時(shí)，邊讀邊與棧頂符號(hào)比較，相等則移掉棧頂符號(hào)，否則出錯(cuò)。22二、上下文無(wú)關(guān)語(yǔ)言的識(shí)別裝置：Push Down Automata 2.定理（1）每一個(gè)CFG，都對(duì)應(yīng)一個(gè)PDA M，使L(M)=L(G)（2）存在一個(gè)PDA，它識(shí)別的

13、語(yǔ)言不能被任何確定的PDA識(shí)別。 歸納：對(duì)上下文無(wú)關(guān)語(yǔ)言的分析，并不總是能以確定的方式進(jìn)行，需要回溯。23二、上下文無(wú)關(guān)語(yǔ)言的識(shí)別裝置：Push Down Automata 小 結(jié) 1.能夠進(jìn)行確定分析的語(yǔ)言稱為確定語(yǔ)言。大多數(shù)的編程語(yǔ)言是確定的語(yǔ)法分析的任務(wù)：有效地模擬PDA2.固有歧義的語(yǔ)言：就是根本不存在非歧義文法的語(yǔ)言。文法的非歧義性是不可判定的只有文法是非歧義的，語(yǔ)法分析才可唯一進(jìn)行雖然不存在算法能在有窮步內(nèi)確定任意文法是否歧義，但對(duì)某些具體文法存在判定算法如：LL文法和LR文法，可證是非歧義文法，并且存在算法，能檢查一文法是否是LL或LR文法24三、自上而下的分析方法1.主旨：從文

14、法的S出發(fā)，反復(fù)使用各種產(chǎn)生式，尋找”匹配”于輸入符號(hào)串的推導(dǎo)（從S（根）出發(fā)，向下逐步建立語(yǔ)法樹(shù)，最終：為輸入串尋找一個(gè)最左推導(dǎo)）例1 GS: (1)ScAd | dBa (2) Aab (3) Aa (4) Bcd | c, 則cad是否為文法的句子SdScAScdAabScdAadcda dcdc 是不是分析過(guò)程是一個(gè)試探過(guò)程，必須一一試探所有候選式，直至與輸入串匹配成功，或者判定輸入串不是正確句子。25三、自上而下的分析方法2. 自上而下分析面臨的主要問(wèn)題 1） 如何選擇候選式如果對(duì)文法不做任何限制，對(duì)候選式的選擇成為無(wú)根據(jù)的，只好一一試探所有候選式，直至成功或失敗。致命弱點(diǎn)：不斷地回

15、溯，大大影響速度。2）左遞歸文法將使自上而下分析陷入無(wú)限循環(huán)例、S Sa | b，若推導(dǎo)baaSSaSaSa263. 自上而下分析法的問(wèn)題及解決Q1: 回溯低效、耗時(shí)，對(duì)高度遞歸的語(yǔ)言，無(wú)法接受。解決方案： 對(duì)文法加以一定的限制，使每次對(duì)候選式的選擇是唯一的，從而進(jìn)行確定的自上而下分析。 如：LL（1）文法。（詳見(jiàn)5.3節(jié)）273. 自上而下分析法的問(wèn)題及解決Q2：左遞歸文法將使自上而下分析陷入無(wú)限循環(huán) 1.重排規(guī)則順序 （解決方法1） 例：S Sa | b, 改為： S b | Sa ，若推導(dǎo)baaSb(不行)SSab（不行）SSabSa2.將左遞歸右遞歸（或迭代） （解決方法2） 如：上例

16、生成語(yǔ)言 L = ba* 右遞歸文法：S bA A aA | 281.消除直接左遞歸AA|, , (VNVT)*, A VN, 不以A開(kāi)頭則：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.消除直接左遞歸若關(guān)于A的全部規(guī)則為 A A1 | A2 | | Am | 1 | 2 | | n 其中， 每個(gè)i都不等于 ，每個(gè)i都不以A開(kāi)頭則消除左遞歸，得 A (1 | 2 | |

17、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 | 5.2.2 消除左遞歸315.3 LL分析法（預(yù)測(cè)分析法）5.3.1 概述5.3.2 LL(1)文

18、法5.3.3 文法的變換5.3.4 LL(1)分析器325.3.1 LL分析概述兩類確定的自頂向下分析方法（1）遞歸下降法 （2）LL (K)方法1. LL(K)含義 從左（L）到右（R）掃描輸入串，并建立它的最左推導(dǎo)。 K：在選擇同一非終極符的不同規(guī)則時(shí)，通過(guò)向前看K個(gè)符號(hào)決定。LL(K)文法： 是非歧義文法中能構(gòu)造出確定的自頂向下分析器的最大文法類。LL分析器又稱預(yù)測(cè)分析器，是PDA特例。332. 預(yù)測(cè)分析方法 自頂向下分析是從文法的開(kāi)始符號(hào)出發(fā)，試構(gòu)造出一個(gè)最左推導(dǎo)，從左至右匹配輸入的單詞符號(hào)串。 如果在每步推導(dǎo)中，面對(duì)被替換的非終結(jié)符號(hào)A和當(dāng)前從左至右讀入輸入串讀到的單詞符號(hào)a，如果A

19、的定義（無(wú)-產(chǎn)生式） A1 |2 | |n 中，只有i（1in)推導(dǎo)出的第一個(gè)終極符號(hào)是a，那么，就可以用產(chǎn)生式Ai構(gòu)造最左推導(dǎo)，即用i替換A。342. 預(yù)測(cè)分析方法一類簡(jiǎn)單文法的分析器工作過(guò)程：(1) 定義 G為S-文法，當(dāng)且僅當(dāng)它滿足： 每條規(guī)則的右部都以VT開(kāi)頭 如果一個(gè)VN有多條規(guī)則，那么它們都以不同的VT開(kāi)頭例1 S aS | bA, A d | ccA 叫做預(yù)測(cè)分析矩陣（表），LL分析表Mabcd#SaSbAAccAd352. 預(yù)測(cè)分析方法對(duì)于上例，在推導(dǎo)過(guò)程中，完全可以根據(jù)當(dāng)前的向前看符號(hào)決定選擇哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo)，因此，分析過(guò)程是完全確定的。這種分析稱為自頂向下的預(yù)測(cè)分析。 原

20、因在于，文法中，AVN, A12. n i,j (1i, j n ij)從 i推導(dǎo)出來(lái)的第一個(gè)終結(jié)符號(hào)集合（稱為FIRST( i) ）和從 j推導(dǎo)出來(lái)的第一個(gè)終結(jié)符號(hào)集合（稱為FIRST( j) ）是不相交的，即： FIRST( i) FIRST( j)=36（2）分析器（預(yù)測(cè)分析器PDA特例）分析器的動(dòng)作總是由 棧頂元素X 當(dāng)前輸入符號(hào)aabccd#決定的S#控制（總控程序）預(yù)測(cè)分析表1 2 4 3預(yù)測(cè)分析器預(yù)分析串輸入帶下推棧初始：# S其中，#棧底 S開(kāi)始符保存用過(guò)的文法規(guī)則（即：左分析）輸出帶37（2）分析器（預(yù)測(cè)分析器PDA特例）分析器的動(dòng)作有3種：1.若棧頂符號(hào)是一個(gè)非終極符，則去

21、查分析表MX, aMX, a是一文法規(guī)則X ，則用去替換棧頂?shù)腦（ 逆序推入棧中），并輸出文法規(guī)則編號(hào)MX, a無(wú)定義，則報(bào)錯(cuò)并轉(zhuǎn)錯(cuò)誤處理程序均不讀下一符號(hào)（相當(dāng)于進(jìn)行了一次最左推導(dǎo)）2.若棧頂符號(hào)X是一個(gè)終極符且X=a，則將棧頂符號(hào)彈出，并讀下一個(gè)符號(hào)，若XVT,且Xa，則err3.若X=“#”=a，則分析器停機(jī)，輸入串被接受385.3.2 LL(1)文法對(duì)于LL(k)文法，K=1最常見(jiàn)，只需根據(jù)棧頂符號(hào)X和當(dāng)前輸入符號(hào)a，即可確定用哪條規(guī)則進(jìn)行推導(dǎo)。（一）串(VNVT)*的FIRST集開(kāi)頭符號(hào)集 FIRST()=a| *a, a VT, , V* 若 *, 則 FIRST()定義1：設(shè)G是

22、不帶規(guī)則的文法，若對(duì)所有 A 1 | 2 | | n的規(guī)則，有FIRST(i) FIRST(j)=,ij，則G為L(zhǎng)L(1)文法。395.3.2 LL(1)文法下面討論有規(guī)則的文法。LL(1)條件？例2: (1) S aA (2) S d (3) A bAS (4) A 若對(duì)abd串，S aA abAS abSabd何時(shí)選用A 的空規(guī)則？SaASaAbASSaAbASSaAbASd參見(jiàn)語(yǔ)法樹(shù) 在分析時(shí)，只有見(jiàn)到它的后繼符號(hào)才能決定使用這條規(guī)則引進(jìn)跟隨集405.3.2 LL(1)文法(二)每個(gè)非終極符的Follow集規(guī)定 “#”屬于開(kāi)始符號(hào)S的Follow集，#是句子結(jié)束符。Follow集定義：若

23、G=(VN,VT,P,S)是CFG，A VN，F(xiàn)ollow(A)=a | S * A, aFirst(), V+，即: 句型中緊跟在A后面的那些終極符若 * ,則# Follow(A)；換句話說(shuō)：若S * A，則規(guī)定# Follow(A)。415.3.2 LL(1)文法(二)每個(gè)非終極符的FOLLOW集定義2：一個(gè)文法G是LL(1)文法，當(dāng)且僅當(dāng)對(duì)文法中形如A 1 | 2 | | n都滿足LL(1)條件，即(1) First(i) First(j)=, ij； 且如果i * ,則(2) First(j) Follow(A)=, ij為簡(jiǎn)化LL(1)條件，引進(jìn)選擇集 Select(A )42（

24、三）每條規(guī)則的select集 select( A)=First() , 當(dāng)不能推出Follow(A) (First() ) , 當(dāng)*利用select集判斷LL(1)文法:定義3：一個(gè)文法G是LL(1)文法，當(dāng)且僅當(dāng)對(duì)文法中的所有形如 A1| 2| n 的產(chǎn)生式, 其各候選式都滿足如下的條件： select( Ai) select( Aj) = (對(duì)所有ij)5.3.2 LL(1)文法435.3.2 LL(1)文法 LL(1)條件： 一個(gè)上下文無(wú)關(guān)文法G，對(duì)其所有形如A 1 | 2 | | n的規(guī)則： select(A i) select(A j) =, ij只要一個(gè)CFG滿足LL(1)條件，就

25、是LL(1)文法，能采用預(yù)測(cè)分析法進(jìn)行確定的自頂向下分析。對(duì)不同的LL(1)文法，其預(yù)測(cè)分析器的總控程序完全一樣。不同僅在于分析表不同。445.3.2 LL(1)文法 LL(1)文法的定義 LL(1)的含義： 按自左向右的順序掃描輸入符號(hào)串，并按最左推導(dǎo)的方式進(jìn)行推導(dǎo)。 “1”表示選擇同一非終極符的不同候選式時(shí)，是通過(guò)向前看一個(gè)輸入符號(hào)（即待匹配指針?biāo)赶虻漠?dāng)前符號(hào)）決定的。 455.3.2 LL(1)文法 怎樣判斷一個(gè)文法是否為L(zhǎng)L（1）文法？這類問(wèn)題可以直接根據(jù)LL(1)文法定義判斷，也可根據(jù)LL(1)分析表判斷。若LL(1)分析表中每一項(xiàng)沒(méi)有多重定義（即無(wú)二義性），就是LL(1) 文法。

26、利用select集構(gòu)造LL(1)分析表, 其元素MA,a按下述規(guī)則確定： (其中, AVN, aVT # ) 對(duì)于每個(gè)形如 A的產(chǎn)生式: 若 a select(A) , 則置 M A,a=“A” 否則置錯(cuò)，用空白表示。46例1： 給定文法 S0S| 1S |是否為 LL(1) 文法？解： 構(gòu)造LL(1)分析表: 01#SS0SS1SS 因?yàn)楸碇袩o(wú)多重定義， 所以該文法是 LL(1) 文法。 5.3.2 LL(1)文法47例2： 給定文法 S0S0| 1S1 |是否為 LL(1) 文法？解： 構(gòu)造LL(1)分析表: 01#SS0S0S S1S1S S 因?yàn)楸碇谐霈F(xiàn)多重定義， 所以該文法不是 LL

27、(1) 文法。 5.3.2 LL(1)文法48例3: 左遞歸文法是LL（1）文法嗎？解：因?yàn)樽筮f歸文法意味著有隱含的左公共因子，所以左遞歸文法不是LL（1）文法。 例如： AAa | b 因?yàn)椋篎irst(Aa=b，F(xiàn)irst(b)=b， 所以 First(Aa First(b)5.3.2 LL(1)文法49關(guān)鍵：如何計(jì)算FOLLOW集FOLLOW集的計(jì)算 (a) 設(shè)S為G中開(kāi)始符號(hào)，則#FOLLOW(S)(b) 若A B是一產(chǎn)生式，則把FIRST()的非空元素加入到FOLLOW(B)中。 如果 * ，則把FOLLOW(A)也加入到FOLLOW(B)中(c) 反復(fù)使用(b)，直到每個(gè)VN的FO

28、LLOW集不再增大為止。50例4 判斷G是否是LL(1)文法，如果是，構(gòu)造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, 相交，不是LL(1)文法同理：select(A )=#, a, c select(B )=# select(C AD)=b,a,c select(C b)=b相交教材

29、P79515.3.3 文法的變換 預(yù)測(cè)分析法是一種確定的自頂向下的語(yǔ)法分析，它要求文法必須是LL（1）形式。 某些非LL（1）文法，經(jīng)過(guò)變換后，有可能改造成LL（1）文法。1.左遞歸文法的變換 左遞歸文法必然不是LL（1）文法。經(jīng)過(guò)消除左遞歸的變換后，新的文法不一定是LL（1）文法，需進(jìn)一步利用LL（1）文法的條件進(jìn)行判斷。 521.左遞歸文法的變換例：給定文法GS： S i | (E) EE+S | E-S | S（1）求每一非終極符的First集和Follow集。（2）判斷該文法是否為L(zhǎng)L（1）文法，為什么？能否進(jìn)行文法變 換成為L(zhǎng)L（1）文法？若能，給出LL（1）分析表。5.3.3 文法

30、的變換53 1.左遞歸文法的變換例：給定文法GS： S i|(E) EE+S|E-S|S（1）求每一非終極符的 First集和Follow集。FirstFollowSi, (#, ), +, -Ei, ( ), +, -(2)因?yàn)樵撐姆ㄊ亲筮f歸文法，所以不是LL(1）文法。 變換左遞歸文法：EE（+S | -S）| SE SE E（+S | -S）E | GS :S i|(E) E SE E+SE|-SE|54（3）求文法GS的每一非終極符的First集和Follow集。(4)文法GS的LL（1）分析表 FirstFollowSi,(#, ), +, -Ei,( )E+,-, )i+-()#S

31、i(E)ESESEE+SE-SE GS :S i|(E) E SE E+SE|-SE|因?yàn)長(zhǎng)L（1）分析表無(wú)多重定義，所以變換后的文法GS是LL（1）文法。555.3.3 文法的變換2.提取左公共因子變換 含有左公共因子的文法肯定不是LL（1）文法，經(jīng)過(guò)提取左公共因子變換后（可能這種變換需多次進(jìn)行），新文法也不一定是LL（1）文法，還需進(jìn)一步由LL（1）條件判定。5.3.3 文法的變換56 2.提取左公共因子變換 例：變換下列文法GS：S aSb|aSc|，并判斷是否為L(zhǎng)L(1)文法。解: 提取左公共因子變換: S aS（b|c）| 令: B b|c 變換后的文法: GS： S aSB| B

32、b|c GS :Select(S aSB)=aSelect(S )=b,c,#Select(B b)=bSelect(B c)=c具有相同左部的產(chǎn)生式的Select集兩兩不相交，故GS 為L(zhǎng)L（1）文法。 57 2.提取左公共因子變換 思考題：能否通過(guò)文法變換，將下面文法轉(zhuǎn)換為L(zhǎng)L(1)文法。 S iBtSeS | iBtS | a B b解：S iBtSS | a S eS | B b因?yàn)?select(S )=#, e ，與e是相交的，不滿足LL（1）條件所以不是LL(1)文法itaeb#SiBtSSaSS eSS S 583. 角替換 角：一規(guī)則右部的最左出現(xiàn)，稱為規(guī)則的角。如： ScS

33、 | Ac 角替換：對(duì)一規(guī)則的非終極符的角，用其規(guī)則右部去替換它。 非終極符角的出現(xiàn)意味著左公共因子可能是隱式的。消除隱式左公共因子的辦法可采用角替換。角替換與提取左公共因子往往同時(shí)進(jìn)行。 角替換是一種輔助手段,用于發(fā)現(xiàn)隱含的左遞歸、左公共因子。角替換本身不改變文法的LL（1）性質(zhì)。593. 角替換 例: 下列文法是否可變換為L(zhǎng)L（1）文法？ 文法GS：ScS | Ac AaS | b解：產(chǎn)生式S Ac 中含有角A，角替換為：SaSc | bc 由于GS中非終極符A變成不可達(dá)符號(hào)，所以產(chǎn)生式 AaS|b應(yīng)予以刪除。 改造后的文法GS : ScS | aSc | bcSelect(ScS )=c

34、 Select(SaSc)=a Select(Sbc )=b 顯然, 具有相同左部的產(chǎn)生式的Select集兩兩相交為空， 故為L(zhǎng)L（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對(duì)S變換，S aS | dp | eq S App | Bqq對(duì)S角替換， S (aAp | d)pp | (aBq | e)qq再提取左因式，S aS | dpp | eqq S Appp | Bqqq繼續(xù)重復(fù)，仍然有左因式。6

35、1 關(guān)于文法變換，有下面的結(jié)論： 存在某些文法，不能在有限步驟內(nèi)提取完左公共因子。 一個(gè)文法經(jīng)變換后，沒(méi)有空產(chǎn)生式，且無(wú)左遞歸時(shí)，則改寫(xiě)后的文法是LL（1）文法，否則需進(jìn)一步用LL(1)條件判斷。 LL（1）文法通過(guò)角替換后，保留LL（1）性質(zhì)。 文法變換可能會(huì)使某些產(chǎn)生式變成無(wú)用產(chǎn)生式，即伴隨著對(duì)文法的化簡(jiǎn)。5.3.3 文法的變換62 LL（1）分析器是由一張LL（1）分析表，一個(gè)控制程序和一個(gè)分析棧組成。分析棧中存放文法符號(hào)。 LL（1）分析器模型如圖所示： #S分析棧a1a2aian輸入數(shù)據(jù)LL（1）分析器 LL（1）分析表輸出最左推導(dǎo)規(guī)則序列5.3.4 LL(1)分析器63# S分析器

36、初態(tài):如圖所示, 分析棧中壓入“#”和文法開(kāi)始符號(hào)S，棧頂元素是S。待匹配指針指向輸入串的第一個(gè)待匹配符. a1a2aian5.3.4 LL(1)分析器64預(yù)測(cè)分析總控程序偽代碼 設(shè) w是待匹配符號(hào)串，ip指向w#的第一個(gè)符號(hào) do 讓X等于棧頂符號(hào)，并且讓a是ip指向的符號(hào)； if (X是終極符或#) if (X= =a) 把X從棧頂彈出，并推進(jìn)ip；else Error; else if (MX , a= =“X y1y2yk”)從棧中彈出X； 把yk, yk-1, , y1壓入棧； /* y1 在棧頂 else Error; while X!=#65 例: 以輸入串 i+i*i 為例,給

37、出用LL(1)分析器識(shí)別符號(hào)串的過(guò)程.文法GE: ETE E+TE| TFT T*FT| Fi|(E) 解:(1)求非終極符的First集和Follow集 FirstFollowEi, (#, )E+ , #, )Ti, (+, #, )T* , +, #, )Fi, (+, #, ), *5.3.4 LL(1)分析器66文法GE: ETE E+TE| TFT T*FT| Fi|(E) 解:(1)FirstFollowEi,(#, )E+,#, )Ti,(+, #, )T*,+, #, )Fi, (+, #, ), *(2) 求LL(1)分析表+*i（）#ETETEE+TETFTFTT*FTF

38、i(E)67ETE E+TE| TFT T*FT| Fi|(E) 解:+*i（）#ETETEE+TETFTFTT*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剩余過(guò)程自己完成68 遞歸子程序法，又稱遞歸下降分析法。思想是：非終極符的文法規(guī)則可看成是識(shí)別該非終極符的過(guò)程定義，針對(duì)文法的每一非終極符，根據(jù)相應(yīng)產(chǎn)生式各候選式的結(jié)構(gòu)，為其編寫(xiě)一個(gè)遞歸函數(shù)，用來(lái)識(shí)別該非終極符

39、所表示的語(yǔ)法范疇。 遞歸下降分析法是一種確定的自頂向下的語(yǔ)法分析方法，其分析過(guò)程是從文法開(kāi)始符號(hào)出發(fā)，執(zhí)行一組遞歸過(guò)程，不斷向下推導(dǎo)，直到推出句子。 5.4 遞歸子程序法 69為了構(gòu)造遞歸子程序，有如下的約定和要注意的問(wèn)題：(1)文法必須是LL（1）文法。 (2)待匹配符號(hào)串是要被分析的源程序，是用助記符或整數(shù)碼表示的單詞類別串。 例如待匹配符號(hào)串“ ID:=ID+NUM# ”，按從左向右掃描輸入串的順序，開(kāi)始的時(shí)候，當(dāng)前匹配指針指向的輸入符號(hào)是“ID”。 (3)設(shè)輔助函數(shù)getsym()的作用是讀取當(dāng)前指針指向的待匹配符，并使待匹配指針向前移，指向下一個(gè)待匹配符。變量sym用來(lái)存儲(chǔ)當(dāng)前匹配指

40、針指向的輸入符號(hào)。 (4)進(jìn)入子程序時(shí)已經(jīng)取到了當(dāng)前的輸入符號(hào)；從子程序返回時(shí)，也已經(jīng)取到了下一次準(zhǔn)備匹配的輸入符號(hào)。 5.4 遞歸子程序法 70為了構(gòu)造遞歸子程序，有如下的約定和要注意的問(wèn)題：(5) 如果遇到非終極符，則直接調(diào)用該非終極符對(duì)應(yīng)的子程序。如果非終極符A的右部只有一個(gè)候選式，則按從左向右的順序依次構(gòu)造A的識(shí)別過(guò)程。 如果遇到終極符，判斷是否與輸入的符號(hào)匹配。若匹配，則讀取下一個(gè)待匹配符號(hào)；如果匹配失敗，則意味著有語(yǔ)法錯(cuò)誤。 (6)如果非終極符A的右部有多個(gè)候選式，則根據(jù)每個(gè)候選式的第一個(gè)符號(hào)確定識(shí)別非終極符A的流程控制轉(zhuǎn)向。5.4 遞歸子程序法 71例：文法Z(U)| aUb ，

41、U dZ|e，為其構(gòu)造遞歸下降分析子程序。并對(duì)輸入串a(chǎn)eb進(jìn)行語(yǔ)法分析 。解： 文法中有兩個(gè)非終結(jié)符號(hào)Z和U，需要分別編兩個(gè)函數(shù)來(lái)完成Z和U規(guī)則的識(shí)別。 對(duì)于規(guī)則Z(U)|aUb，右部有兩個(gè)候選式，因此，U的識(shí)別過(guò)程有兩個(gè)分支，分別根據(jù)符號(hào)( 和 a 來(lái)判別。 同理對(duì)規(guī)則UdZ|e 設(shè)計(jì)的過(guò)程也分為兩個(gè)分支。見(jiàn)圖(a)和(b)所示。5.4 遞歸子程序法 72Z (U)|aUb圖(a) 非終結(jié)符號(hào)Z的分析程序 過(guò)程Zsym= getsym()U出口語(yǔ)法錯(cuò)誤：輸入串少) sym =aYNNNNYY語(yǔ)法錯(cuò)誤：輸入串少(、a語(yǔ)法錯(cuò)誤：輸入串少b sym =(sym =)sym =bsym= getsy

42、m()sym= getsym()UY對(duì)輸入串a(chǎn)eb進(jìn)行語(yǔ)法分析73U dZ|e過(guò)程Usym= getsym()Z出口sym =eYNNY語(yǔ)法錯(cuò)誤：輸入串少d、esym= getsym()Y圖(b) 非終結(jié)符號(hào)U的分析程序 sym =d對(duì)輸入串a(chǎn)eb進(jìn)行語(yǔ)法分析74U dZ|e 每個(gè)非終結(jié)符對(duì)應(yīng)的函數(shù)設(shè)計(jì)好后，就可以對(duì)輸入串進(jìn)行語(yǔ)法分析。 假設(shè)輸入串為aeb, 從Z函數(shù)開(kāi)始識(shí)別，由于sym不等于(，等于a，所以選擇Z函數(shù)的右邊分支，表示選擇了ZaUb規(guī)則。讀下一個(gè)符號(hào)，使sym=e; 調(diào)U函數(shù)，因sym=e，表示使用Ue 規(guī)則, 讀下一個(gè)符號(hào)，使sym=b，并返回調(diào)用程序Z函數(shù)右邊分支U的下方，

43、接著判斷sym=b，讀下一個(gè)符號(hào)，并退出Z. 在主函數(shù)中判斷:若sym=#,則分析過(guò)程結(jié)束，從而判定輸入串a(chǎn)eb語(yǔ)法分析成功。 這個(gè)過(guò)程相當(dāng)于構(gòu)造了如下推導(dǎo)過(guò)程：Z=aUb=aeb Z (U)|aUb對(duì)輸入串a(chǎn)eb#進(jìn)行語(yǔ)法分析75例：為下列文法的每個(gè)非終極符構(gòu)造相應(yīng)的遞歸函數(shù) 文法GZ： Z(U) | aUb UdZ | e解： main( ) sym=getsym( ); /讀取當(dāng)前輸入串的第一個(gè)符號(hào) Z(); /從文法開(kāi)始符號(hào)對(duì)應(yīng)的子程序開(kāi)始識(shí)別 if (sym=#) OK; /”#”是程序結(jié)束的標(biāo)志 else error (“error in main”); 對(duì)輸入串a(chǎn)eb#進(jìn)行語(yǔ)法分

44、析76 Z() / Z(U) | aUb if(sym=( ) sym=getsym(); 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);對(duì)輸入串a(chǎn)eb#進(jìn)行語(yǔ)法分析77 U() / UdZ | e if(sym=d) sym=getsym(); Z(); els

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

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

47、m= =*) sym=getsym( ); F(); T(); else if (sym# sym+sym)/ if (sym follow (T) error (“非法符號(hào)”, sym); exit(0); /意味著用T 推導(dǎo)83 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);84例： 文法GE：EE+T | T TT*F | F Fi | (E)設(shè)計(jì)遞歸子程序。解: 對(duì)文法G消除左遞歸為G(E): E+|-T+T /考慮表達(dá)式有形如+5或-5的情況 TF*F Fi|(E) 85 E() /E +|- T+T if (sym = + | sym= -) sym=getsym(); if(sym = i | sym = ( ) T(); else error; exit(0); else if (