編譯原理 第4章-自頂向下語法分析方法

1、Compiler Construction Principles 本本章討論程序語言的語法分析方章討論程序語言的語法分析方法，以及語法分析程序的設(shè)計(jì)原理法，以及語法分析程序的設(shè)計(jì)原理和實(shí)現(xiàn)技術(shù)。和實(shí)現(xiàn)技術(shù)。Compiler Construction Principlesu語法分析程序的功能和語法分析方法u 自頂向下語法分析法u 自底向上算符優(yōu)先分析法u LR分析法 Compiler Construction Principles語法分析程序的功能語法分析程序的功能 語法分析器語法分析器詞法分析后詞法分析后的單詞串的單詞串語法成分構(gòu)語法成分構(gòu)成的語法樹成的語法樹或錯(cuò)誤表或錯(cuò)誤表Compiler

2、Construction Principles語法分析的方法自頂向下語法分析法(自上而下語法分析法)自底向上語法分析法(自下而上語法分析法)Compiler Construction Principles1. 1. 自上而下的分析法自上而下的分析法 從文法的開始符號(hào)出發(fā)，根據(jù)文法規(guī)從文法的開始符號(hào)出發(fā)，根據(jù)文法規(guī)則正向推導(dǎo)出給定句子的一種方法；或者則正向推導(dǎo)出給定句子的一種方法；或者說，從樹根開始，往下構(gòu)造語法樹，直到說，從樹根開始，往下構(gòu)造語法樹，直到建立每個(gè)葉的分析方法。建立每個(gè)葉的分析方法。 Compiler Construction Principles2. 2. 自下而上的分析法自下

3、而上的分析法 從給定的輸入串開始，根據(jù)文法規(guī)從給定的輸入串開始，根據(jù)文法規(guī)則逐步進(jìn)行歸約，直至歸約到文法開始則逐步進(jìn)行歸約，直至歸約到文法開始符號(hào)的一種方法；或者說，從語法樹的符號(hào)的一種方法；或者說，從語法樹的未端開始，步步向上歸約，直至根結(jié)點(diǎn)未端開始，步步向上歸約，直至根結(jié)點(diǎn)的分析方法。的分析方法。 Compiler Construction Principles4.2 4.2 自上而下自上而下語法語法分析法分析法 非確定的自上而下分析法的基本思想是非確定的自上而下分析法的基本思想是： 對(duì)任何輸入串對(duì)任何輸入串W試圖用一切可能的試圖用一切可能的辦法，從文法的開始符號(hào)出發(fā)，自上而辦法，從文法的

4、開始符號(hào)出發(fā)，自上而下地為它建立一棵語法樹?；蛘哒f，為下地為它建立一棵語法樹?；蛘哒f，為輸入串尋找一個(gè)最左推導(dǎo)。如果試探成輸入串尋找一個(gè)最左推導(dǎo)。如果試探成功，則功，則W為相應(yīng)文法的一個(gè)句子，否則為相應(yīng)文法的一個(gè)句子，否則W就不是文法句子。就不是文法句子。Compiler Construction Principles4.2.1 4.2.1 非確定的自上而下分析法的非確定的自上而下分析法的思想思想 也就是說，這種分析過程本質(zhì)上是也就是說，這種分析過程本質(zhì)上是一種窮舉試探過程，是反復(fù)使用不同規(guī)一種窮舉試探過程，是反復(fù)使用不同規(guī)則，謀求匹配輸入串的過程。則，謀求匹配輸入串的過程。試探發(fā)生回溯。試探

5、發(fā)生回溯。 Compiler Construction Principles4.2.1 4.2.1 非確定的自上而下分析法的非確定的自上而下分析法的思想思想例例 設(shè)有文法設(shè)有文法GS：S aAbA de | d輸入串輸入串 W=adbS a A bd e匹配失敗、這時(shí)應(yīng)回匹配失敗、這時(shí)應(yīng)回溯溯, ,選擇選擇A A的其它可能的其它可能的規(guī)則重新匹配。的規(guī)則重新匹配。Compiler Construction Principles4.2.1 4.2.1 非確定的自上而下分析法的非確定的自上而下分析法的思想思想d匹配成功匹配成功 S aAbA de | dS a A b輸入串輸入串 W=adbCom

6、piler Construction Principles4.2.1 4.2.1 非確定的自上而下分析法的非確定的自上而下分析法的思想思想 上述自上而下為輸入串上述自上而下為輸入串W建立語法建立語法樹的過程，實(shí)際也是設(shè)法為輸入串建樹的過程，實(shí)際也是設(shè)法為輸入串建立一個(gè)最左推導(dǎo)序列：立一個(gè)最左推導(dǎo)序列：SaAbadb。 由于對(duì)輸入串從左向右進(jìn)行掃描，由于對(duì)輸入串從左向右進(jìn)行掃描，使用最左推導(dǎo)，才能保證按從左到右使用最左推導(dǎo)，才能保證按從左到右掃描順序匹配輸入串掃描順序匹配輸入串。Compiler Construction Principles4.2.1 4.2.1 非確定的自上而下分析法的非確定

7、的自上而下分析法的思想思想 根據(jù)以上分析，不難看出，非確定根據(jù)以上分析，不難看出，非確定的自上而下分析法即是帶回溯的自上而的自上而下分析法即是帶回溯的自上而下分析法下分析法, , 實(shí)際上是一種窮舉的試探方實(shí)際上是一種窮舉的試探方法，其分析效率極低，代價(jià)很高，在實(shí)法，其分析效率極低，代價(jià)很高，在實(shí)用的編譯程序中是不常用的。我們通常用的編譯程序中是不常用的。我們通常使用確定的自上而下分析法進(jìn)行語法分使用確定的自上而下分析法進(jìn)行語法分析。析。 Compiler Construction Principles4.2.1 4.2.1 非確定的自上而下分析法非確定的自上而下分析法的思想的思想 但確定的自上

8、而下分析法對(duì)語言但確定的自上而下分析法對(duì)語言的文法有一定的限制條件，那就是要的文法有一定的限制條件，那就是要求描述語言的文法是無左遞歸的和無求描述語言的文法是無左遞歸的和無回溯的?；厮莸?。 Compiler Construction Principles4.2.2 文法的左遞歸性和回溯的消除 文法左遞歸的消除 當(dāng)一個(gè)文法是左遞歸文法時(shí)，采用自上而下分析法會(huì)使分析過程進(jìn)入無窮循環(huán)之中。 文法左遞歸是指文法中的某個(gè)非終結(jié)符A存在推導(dǎo)A A+Compiler Construction Principles4.2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除消除 用非終結(jié)符用非終結(jié)

9、符A去匹配輸入串時(shí)去匹配輸入串時(shí),使當(dāng)前句使當(dāng)前句型的最左非終結(jié)符仍然為型的最左非終結(jié)符仍然為A。 也就是說，在沒有讀進(jìn)任何輸入符號(hào)的也就是說，在沒有讀進(jìn)任何輸入符號(hào)的情況下，又重新要求情況下，又重新要求A去進(jìn)行新的匹配。去進(jìn)行新的匹配。于是，造成無窮循環(huán)。于是，造成無窮循環(huán)。 Compiler Construction Principles4.2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除消除 對(duì)含直接左遞歸的規(guī)則進(jìn)行等價(jià)變換，對(duì)含直接左遞歸的規(guī)則進(jìn)行等價(jià)變換，消除左遞歸消除左遞歸(1) 引進(jìn)一個(gè)新的非終結(jié)符，把含左遞歸引進(jìn)一個(gè)新的非終結(jié)符，把含左遞歸 的規(guī)則改寫成右遞

10、歸。的規(guī)則改寫成右遞歸。 設(shè)關(guān)于非終結(jié)符設(shè)關(guān)于非終結(jié)符A的直接左遞歸的的直接左遞歸的規(guī)則為規(guī)則為Compiler Construction Principles4.2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除消除對(duì)對(duì)A的規(guī)則可改寫成如下右遞歸形式：的規(guī)則可改寫成如下右遞歸形式： A A | A AA A | 其中其中 、是任意的符號(hào)串是任意的符號(hào)串, 不等于不等于 , 不以不以A開頭開頭Compiler Construction Principles4.2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除消除 改寫以后的形式和原來形式是等價(jià)改寫以后的形式

11、和原來形式是等價(jià)的。也就是說，從的。也就是說，從A推出的符號(hào)串的集推出的符號(hào)串的集合是相同的。合是相同的。 Compiler Construction Principles4.2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除消除一般情況下，設(shè)文法中關(guān)于一般情況下，設(shè)文法中關(guān)于A的規(guī)則為的規(guī)則為A A1| A2| | Am| 1| 2| | n 其中每個(gè)其中每個(gè)都不等于都不等于，而每個(gè)，而每個(gè) 都不都不以以A開頭，消除直接左遞歸后改寫為開頭，消除直接左遞歸后改寫為:A 1A | 2A | mA | A 1A | 2A | nACompiler Construction Pri

12、nciples4.2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除消除例例1 設(shè)有文法設(shè)有文法GE： E E+T | ET | TT T* *F | T/F | FF (E) | id消去非終結(jié)符消去非終結(jié)符E, T的直接左遞歸后，的直接左遞歸后，文法文法GE改寫為：改寫為：F (E) | idETEE +TE | TE | T FTT * *FT | /FT | Compiler Construction Principles4.2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除消除例例2 設(shè)有文法設(shè)有文法GA: A Ac | Aad | bd | e消

13、去直接左接左遞歸后文法消去直接左接左遞歸后文法GA改寫為改寫為 A cA | adA | A bdA | eACompiler Construction Principles4.2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除消除2. 2. 回溯的消除回溯的消除 在自上而下分析過程中，由于回在自上而下分析過程中，由于回溯，需要推翻前面的分析，包括已做溯，需要推翻前面的分析，包括已做的一大堆語義工作，重新去進(jìn)行試探，的一大堆語義工作，重新去進(jìn)行試探，這樣大大降低了語法分析器的工作效這樣大大降低了語法分析器的工作效率，因此，需要消除回溯。率，因此，需要消除回溯。 Compile

14、r Construction Principles4.2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除消除 我們分析發(fā)現(xiàn)引起回溯的原因是我們分析發(fā)現(xiàn)引起回溯的原因是: 在在文法中文法中,當(dāng)某個(gè)非終結(jié)符當(dāng)某個(gè)非終結(jié)符A有多個(gè)候選式時(shí)有多個(gè)候選式時(shí):遇到用遇到用A去匹配當(dāng)前輸入符號(hào)去匹配當(dāng)前輸入符號(hào)a時(shí)，時(shí)，無法確定選用唯一的一個(gè)候選式，而只無法確定選用唯一的一個(gè)候選式，而只能逐一進(jìn)行試探，從而引起回溯。具體能逐一進(jìn)行試探，從而引起回溯。具體表現(xiàn)在下面兩種情況。表現(xiàn)在下面兩種情況。A 1 | 2 | 3 | nCompiler Construction Principles4.

15、2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除消除 第一種情況第一種情況: : 文法中相同左部的文法中相同左部的規(guī)則，其右部左端第一個(gè)符號(hào)相同而規(guī)則，其右部左端第一個(gè)符號(hào)相同而引起回溯。引起回溯。S aAbA de | d例例 設(shè)有文法設(shè)有文法GS： Compiler Construction Principles4.2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除消除 第二種情況第二種情況: 文法中相同左部的規(guī)文法中相同左部的規(guī)則，其中某一右部能推出則，其中某一右部能推出串，例如串，例如, 文法文法G： A BxB x | 其非終結(jié)符其非終結(jié)符B有兩

16、個(gè)右部，第二個(gè)右有兩個(gè)右部，第二個(gè)右部能推導(dǎo)出部能推導(dǎo)出串且兩個(gè)右部左端第一串且兩個(gè)右部左端第一個(gè)符號(hào)不相同，但在分析符號(hào)串個(gè)符號(hào)不相同，但在分析符號(hào)串Wx 時(shí)出現(xiàn)回溯。時(shí)出現(xiàn)回溯。 Compiler Construction Principles4.2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除消除試探分析過程如下圖所示：試探分析過程如下圖所示： A B xxA B xA BxB x | Wx匹配失敗匹配失敗匹配成功匹配成功 Compiler Construction Principles4.2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除消除 綜上

17、所述，在自上而下分析過程綜上所述，在自上而下分析過程中，為了避免回溯，中，為了避免回溯， 對(duì)描述語言的對(duì)描述語言的文法有一定的要求文法有一定的要求: :Compiler Construction Principles 對(duì)文法的某個(gè)非終結(jié)符對(duì)文法的某個(gè)非終結(jié)符A,當(dāng)它有多當(dāng)它有多個(gè)侯選式時(shí)個(gè)侯選式時(shí): 若用若用A匹配輸入串時(shí)匹配輸入串時(shí),能根據(jù)當(dāng)前讀到能根據(jù)當(dāng)前讀到的輸入符號(hào)的輸入符號(hào)a唯一地選擇一條規(guī)則去匹唯一地選擇一條規(guī)則去匹備輸入串?；蛘哒f，能唯一地選擇一條備輸入串。或者說，能唯一地選擇一條規(guī)則進(jìn)行推導(dǎo)。規(guī)則進(jìn)行推導(dǎo)。4.2.2 4.2.2 文法文法的左遞歸性和回溯的的左遞歸性和回溯的消除

18、消除A 1 | 2 | 3 | nCompiler Construction Principles 這也就是說，在自上而下分析過程中，為了避免回溯，要求描述語言的文法是LL(1)文法。4.2.2 文法的左遞歸性和回溯的消除Compiler Construction PrinciplesLL(1)文法的判斷條件文法的判斷條件 為了建立為了建立LL(1)文法的判斷條件，需引文法的判斷條件，需引進(jìn)三個(gè)相關(guān)集：進(jìn)三個(gè)相關(guān)集： FIRST集集 FOLLOW集集SELECT集集 Compiler Construction PrinciplesLL(1)文法的判斷條件文法的判斷條件(1) 設(shè)設(shè)是文法是文法G

19、的任一符號(hào)串，定義文的任一符號(hào)串，定義文 法符號(hào)串法符號(hào)串的首符號(hào)集合。的首符號(hào)集合。FIRST() = a | a且且 aVT *,則規(guī)定則規(guī)定 FIRST()若若 *Compiler Construction PrinciplesLL(1)文法的判斷條件文法的判斷條件例例 設(shè)有文法設(shè)有文法GS: S Ap | BqA cA | aB dB | bFIRST(Ap) = c, a AP cAp AP ap FIRST(Bq) =Bq bq b, d Bq dBq Compiler Construction Principles LL(1)文法的判斷條件文法的判斷條件(2) 設(shè)文法設(shè)文法G的開

20、始符號(hào)為的開始符號(hào)為S，對(duì)于，對(duì)于G的的任任 何非終結(jié)符何非終結(jié)符A，定義非終結(jié)符，定義非終結(jié)符A的后的后 繼符號(hào)的集合繼符號(hào)的集合 FOLLOW(A) = a | S Aa 且且aVT *若有若有S A ,*則規(guī)定則規(guī)定 # FOLLOW(A)。 Compiler Construction PrinciplesLL(1)文法的判斷條件文法的判斷條件 換句話說換句話說FOLLOW(A)是是G的所有句的所有句型中緊接在型中緊接在A之后出現(xiàn)的終結(jié)符或之后出現(xiàn)的終結(jié)符或#。 這里我們用這里我們用#作為輸入串的結(jié)束符，作為輸入串的結(jié)束符，例如，例如， # 輸入串輸入串 # 。 Compiler Con

21、struction PrinciplesLL(1)文法的判斷條件文法的判斷條件例例 設(shè)有文法設(shè)有文法GA: FOLLOW(B) =A aB A aB abBA abBd A aB abBA abBaB # , d, a AaB | dBbBA | Compiler Construction PrinciplesLL(1)文法的判斷條件文法的判斷條件(3) 定義規(guī)則的選擇集合定義規(guī)則的選擇集合SELECT，設(shè)，設(shè) A 是文法是文法G的任一條規(guī)則，其中的任一條規(guī)則，其中 AVN , (VNVT)* ，定義，定義 SELECT(A ) =FIRST() FIRST()FOLLOW (A) */若若

22、*若若 Compiler Construction PrinciplesLL(1)文法的判斷條件文法的判斷條件例例 設(shè)有文法設(shè)有文法GA: AaB | dBbBA | SELECT(AaB ) =FIRST(aB) = a SELECT(Ad ) = FIRST(d) = d Compiler Construction PrinciplesLL(1)文法的判斷條件文法的判斷條件 b SELECT(BbBA ) =FIRST(bBA) = = , #, d, a FOLLOW(B)SELECT(B) =FIRST() FOLLOW(B) = #, d, a AaB | dBbBA | Compi

23、ler Construction PrinciplesLL(1)文法的判斷條件文法的判斷條件LL(1)文法定義文法定義一個(gè)上下文無關(guān)文法一個(gè)上下文無關(guān)文法 G是是LL(1)文法文法, 當(dāng)當(dāng)且僅當(dāng)對(duì)且僅當(dāng)對(duì) G 中每個(gè)非終結(jié)符中每個(gè)非終結(jié)符A的任何兩的任何兩個(gè)不同的規(guī)則個(gè)不同的規(guī)則 A | ，滿足，滿足 SELECT(A )SELECT(A) = 其中其中 、中至多只有一個(gè)能推出中至多只有一個(gè)能推出串。串。 Compiler Construction PrinciplesLL(1)文法的判斷條件文法的判斷條件 LL(1)中的第一個(gè)中的第一個(gè)L表明自上而下的表明自上而下的分析是從左到右掃描輸入串，

24、第二個(gè)分析是從左到右掃描輸入串，第二個(gè)L表明分析過程中使用最左推導(dǎo)，表明分析過程中使用最左推導(dǎo)，1表示表示分析時(shí)每一步只需向前看一個(gè)符號(hào)即可分析時(shí)每一步只需向前看一個(gè)符號(hào)即可決定所選用的規(guī)則，而且這種選擇是準(zhǔn)決定所選用的規(guī)則，而且這種選擇是準(zhǔn)確無誤的。確無誤的。 Compiler Construction Principles 確定的自上而下分析法要求描述確定的自上而下分析法要求描述 語言的文法是語言的文法是 LL(1)LL(1)文法。文法。 (1) (1) 求文法每個(gè)產(chǎn)生式右部符號(hào)串的求文法每個(gè)產(chǎn)生式右部符號(hào)串的 FIRSTFIRST集。集。(2)(2)求文法各個(gè)非終結(jié)符的求文法各個(gè)非終結(jié)符

25、的FOLLOWFOLLOW集。集。LL(1)文法的判斷條件文法的判斷條件Compiler Construction Principles(3)(3)求文法每個(gè)產(chǎn)生式的求文法每個(gè)產(chǎn)生式的SELECTSELECT集。集。(4)(4)求相同左部產(chǎn)生式的求相同左部產(chǎn)生式的SELECTSELECT交集。交集。對(duì)對(duì)文法文法GG的每一個(gè)的每一個(gè)非終結(jié)符非終結(jié)符A A的的產(chǎn)生式產(chǎn)生式SELECT(A i)SELECT(A j)= (ij)則文法則文法G G是一個(gè)是一個(gè)LL(1)LL(1)文法文法A 1 | 2 | n下面條件成立下面條件成立: :LL(1)文法的判斷條件文法的判斷條件Compiler Cons

26、truction Principles例例 設(shè)有文法設(shè)有文法GSSaAbDe | dABSD | eBSAc | cD | DSe | 1. 計(jì)算文法計(jì)算文法GS每個(gè)非終結(jié)符的每個(gè)非終結(jié)符的FIRST集集 和和FOLLOW集集 。2. 判斷文法判斷文法GS 是否是否LL(1)文法。文法。 Compiler Construction Principles對(duì)每一文法符號(hào)對(duì)每一文法符號(hào)XV, 求求FIRST(X)的規(guī)則的規(guī)則: FIRST() = a | a且且 aVT *,則規(guī)定則規(guī)定 FIRST()若若 *1. 若若 XVT , 則則FIRST(X) =X2. 若若 XVN 且有且有 X a,

27、則把則把 a 加入加入 FIRST(X)中中 ,若若 X , 則把則把 加入加入FIRST(X)中中 3. 若若 XY1Y2Yn, YiVN ,則把則把 FIRST(Y1)中所有非中所有非 元素加入元素加入FIRST(X)中中 ,若若Y1 ,則把則把 FIRST(Y1)中所有非中所有非 元素加入元素加入FIRST(X)中中 , Y1 y2Yn ,則把則把 加入加入FIRST(X)中中 Compiler Construction Principles FIRST(S)=FIRST(aAbDe)FIRST(d)= a,d FIRST(A)=FIRST(B)FIRST(e) FIRST(S)e= a

28、,d,c,e SaAbDe | dABSD | eBSAc | cD | DSe | 問問: 能否能否 因?yàn)閺囊驗(yàn)閺?A */ , 所以所以 FIRST(A) FIRST(B)=FIRST(S)FIRST(cD)= a,d,c, FIRST(D)=FIRST(Se)= a, d, Compiler Construction PrinciplesFOLLOW(A) = a | S Aa 且且aVT *若有若有S A ,*則規(guī)定則規(guī)定 #FOLLOW(A)。 求求FOLLOW(A)的規(guī)則的規(guī)則:1. 對(duì)文法的開始符號(hào)對(duì)文法的開始符號(hào)S , 令令#FOLLOW(S)2.若若 AB是一條規(guī)則是一條規(guī)則

29、, 則把則把FOLLOW(A)加到加到FOLLOW(B)中中3.若若 AB是一條規(guī)則是一條規(guī)則, 則將則將FIRST() 加到加到FOLLOW(B)中中,若若 , 則把則把FOLLOW(A)加到加到FOLLOW(B)中中*Compiler Construction Principles 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 Compil

30、er Construction Principles根據(jù)LL(1)文法的定義有:SELECT(SaAbDe)SELECT(Sd)=FIRST(aAbDe)FIRST(d)=SELECT(ABSD)SELECT(Ae)=FIRST(BSD)FIRST(e)=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)文法Compiler Construction Princ

31、iplesE TEE +TE | T FTT *FT | F (E) | id練習(xí)練習(xí) 設(shè)有文法設(shè)有文法GE：1. 計(jì)算文法計(jì)算文法GS每個(gè)非終結(jié)符的每個(gè)非終結(jié)符的FIRST集和集和FOLLOW集集 。2. 判斷文法判斷文法GS 是否是否LL(1)文法。文法。 Compiler Construction Principles例例1 設(shè)有文法設(shè)有文法GS:S aAbA de | dSELECT(Ade)= FIRST(de)=dSELECT(Ad)= FIRST(d)=dSELECT(Ade)SELECT(Ad) 由由LL(1)文法定義可知，該文法不是文法定義可知，該文法不是LL(1)文法，因此

32、對(duì)輸入串不能進(jìn)行確文法，因此對(duì)輸入串不能進(jìn)行確定的自上而下分析。定的自上而下分析。 Compiler Construction Principles例例2 設(shè)有文法設(shè)有文法GA A aB | dB bBA | 則則 SELECT(AaB)=FIRST(aB)=a SELECT(Ad)=FIRST(d)=d SELECT(BbBA)=FIRST(bBA)=b SELECT(B) =(FIRST()- )FOLLOW(B)=a, d, #Compiler Construction Principles所以所以 SELECT(AaB)SELECT(Ad)=SELECT(BbBA)SELECT(B)=

33、由定義可知，由定義可知，GA是是LL(1)文法，對(duì)任文法，對(duì)任何輸入串何輸入串W可進(jìn)行確定的分析?？蛇M(jìn)行確定的分析。 Compiler Construction Principles例例3 設(shè)有文法設(shè)有文法GS:S aABA bB | dA | B a | e SELECT(AbB)=FIRST(bB)= b SELECT(AdA)=FIRST(dA)= d SELECT(A) =(FIRST()- ) FOLLOW(A) = a, e 試判斷該文法是否試判斷該文法是否LL(1)文法。文法。Compiler Construction Principles SELECT(Ba)=FIRST(a)

34、= a SELECT(Be)=FIRST(e)= e SELECT(AbB)SELECT(AdA)=SELECT(AbB)SELECT(A)=SELECT(AdA)SELECT(A)=SELECT(Ba)SELECT(Be)=S aABA bB | dA | B a | e 該文法為該文法為L(zhǎng)L(1)文法文法Compiler Construction Principles例例4 設(shè)有文法設(shè)有文法GS:S AB | bCA b | B aD | C AD | D aS | c 試判斷該文法是否試判斷該文法是否LL(1)文法文法 分析分析 對(duì)文法某個(gè)非終結(jié)符對(duì)文法某個(gè)非終結(jié)符,當(dāng)有多個(gè)候當(dāng)有多個(gè)候

35、選式時(shí)選式時(shí), 求規(guī)則的求規(guī)則的SELECT集合集合Compiler Construction PrinciplesSELECT(SAB) =FIRST(AB)FOLLOW(S) = a, b, # SELECT(SbC)=FIRST(bC)= b SELECT(SAB)SELECT(S bC) S AB | bCA b | B aD | C AD | D aS | cFIRST(AB)=FIRST(A)FIRST(B)=a, b, FOLLOW(S)=# 該文法不為該文法不為L(zhǎng)L(1)文法文法Compiler Construction PrinciplesLL(1)LL(1)文法文法的判斷條

36、件的判斷條件 由定義可知由定義可知, 文法文法GS是是LL(1)文法，文法，對(duì)任何的輸入串可進(jìn)行確定的自上而下對(duì)任何的輸入串可進(jìn)行確定的自上而下分析。分析。Compiler Construction PrinciplesLL(1)文法的判斷條件文法的判斷條件綜合上面的討論，我們可知對(duì)綜合上面的討論，我們可知對(duì)LL(1)文法，若當(dāng)前非終結(jié)符文法，若當(dāng)前非終結(jié)符A面臨輸入符號(hào)面臨輸入符號(hào)a時(shí)，可根據(jù)時(shí)，可根據(jù)a屬于哪一個(gè)屬于哪一個(gè)SELECT集，唯集，唯一地選擇一條相應(yīng)規(guī)則去準(zhǔn)確地匹配輸一地選擇一條相應(yīng)規(guī)則去準(zhǔn)確地匹配輸入符號(hào)入符號(hào)a。也就是說，當(dāng)描述語言的文法。也就是說，當(dāng)描述語言的文法是是LL

37、(1)文法時(shí)，可對(duì)其進(jìn)行確定的自上文法時(shí)，可對(duì)其進(jìn)行確定的自上而下的分析。而下的分析。 Compiler Construction Principles4.2.3 某些非某些非LL(1)文法到文法到LL(1)文法的改文法的改寫寫 前面已經(jīng)指出，構(gòu)造確定的自上前面已經(jīng)指出，構(gòu)造確定的自上而下分析程序要求對(duì)給定語言的文法而下分析程序要求對(duì)給定語言的文法必須是必須是LL(1)文法，但是，并不是每文法，但是，并不是每個(gè)語言都有個(gè)語言都有LL(1)文法。文法。 Compiler Construction Principles 由由 LL(1)文法定義可知文法定義可知, 若文法中含若文法中含有左遞歸或含有

38、公共左因子，則該文有左遞歸或含有公共左因子，則該文法不是法不是 LL(1) 文法，因此，對(duì)某些非文法，因此，對(duì)某些非LL(1)文法而言文法而言, 可通過消除左遞歸和可通過消除左遞歸和反復(fù)提取公共左因子對(duì)文法進(jìn)行等價(jià)反復(fù)提取公共左因子對(duì)文法進(jìn)行等價(jià)變換，可能將其改造為變換，可能將其改造為 LL(1)文法。文法。消除文法左遞歸的方法見消除文法左遞歸的方法見4.2.2。 Compiler Construction Principles提取公共左因子提取公共左因子當(dāng)文法中含有形如當(dāng)文法中含有形如A 1 | 2 | | n 的規(guī)則的規(guī)則 不滿足不滿足LL(1)文法條件。文法條件。則其右部的則其右部的FI

39、RST集交不空，即集交不空，即 SELECT(A i)SELECT(A j)Compiler Construction Principles提取公共左因子將文法改寫成提取公共左因子將文法改寫成: : A A 若在若在 1 1, , 2 23 3中仍含有公共左因子，中仍含有公共左因子，這時(shí)可再次提取這時(shí)可再次提取, , 這樣反復(fù)進(jìn)行提取，直這樣反復(fù)進(jìn)行提取，直到引進(jìn)新非終結(jié)符的有關(guān)規(guī)則再無公共左到引進(jìn)新非終結(jié)符的有關(guān)規(guī)則再無公共左因子為止。因子為止。 A 1 | 2 | | n 的規(guī)則的規(guī)則 A 1| 2| | nCompiler Construction Principles例例1 設(shè)有文法設(shè)

40、有文法GS: 該文法是非該文法是非LL(1)文法，該文法有公共文法，該文法有公共左因子，利用提取公共左因子的方法對(duì)左因子，利用提取公共左因子的方法對(duì)其進(jìn)行改寫，我們得到其進(jìn)行改寫，我們得到 S aAbA de | dCompiler Construction Principles不難驗(yàn)證改寫后的文法為不難驗(yàn)證改寫后的文法為L(zhǎng)L(1)文法。文法。 因?yàn)橐驗(yàn)?SELECT(A e)SELECT(A ) =e, b= S aAbA dAA e | Compiler Construction Principles例例2 2 設(shè)有文法設(shè)有文法GS:GS:S ad | AeA aS | bA將將A的兩條規(guī)

41、則代入非終結(jié)符的兩條規(guī)則代入非終結(jié)符S的規(guī)則中的規(guī)則中A aS | bAS ad | aSe | bAeCompiler Construction Principles對(duì)對(duì)S提取公共左因子得提取公共左因子得 S bAe | aS改寫后的文法是改寫后的文法是LL(1)文法。文法。S d | SeA aS | bAA aS | bAS ad | aSe | bAeCompiler Construction Principles應(yīng)當(dāng)指出的是并非一切非應(yīng)當(dāng)指出的是并非一切非LL(1)文法文法都能改寫為都能改寫為L(zhǎng)L(1)文法。文法。例如，對(duì)于文法例如，對(duì)于文法 S Ae | BdA aAe | bB

42、aBd | b 該文法不為該文法不為L(zhǎng)L(1)文法文法 SELECT(SAe)SELECT(SBd) = a, b a, b Compiler Construction Principles對(duì)對(duì)S提取公共左因子后，得提取公共左因子后，得對(duì)于對(duì)于S的兩條規(guī)則的兩條規(guī)則, 可先將非終結(jié)可先將非終結(jié)符符A、B用相應(yīng)規(guī)則右部進(jìn)行替換，我用相應(yīng)規(guī)則右部進(jìn)行替換，我們得到們得到S aAee | be | aBdd | bdA aAe | bB aBd | bCompiler Construction Principles顯然，它仍不是一個(gè)顯然，它仍不是一個(gè)LL(1)文法，且文法，且不難看出無論將上述步驟重

43、復(fù)多少次不難看出無論將上述步驟重復(fù)多少次, 都都無法將它改寫為無法將它改寫為L(zhǎng)L(1)文法。文法。S aS | bSS Aee | BddA aAe | bS e | dB aBd | bCompiler Construction Principles4.2.4 遞歸下降分析法遞歸下降分析法 遞歸下降分析法是確定的自遞歸下降分析法是確定的自上而下分析法，這種分析法要上而下分析法，這種分析法要求文法是求文法是LL(1)文法。文法。 Compiler Construction Principles基本思想基本思想 對(duì)文法中的每個(gè)非終結(jié)符編寫一個(gè)函對(duì)文法中的每個(gè)非終結(jié)符編寫一個(gè)函數(shù)數(shù) ( (或子程序

44、或子程序), ), 每個(gè)函數(shù)（或子程序）的每個(gè)函數(shù)（或子程序）的功能是識(shí)別由該非終結(jié)符所表示的語法成功能是識(shí)別由該非終結(jié)符所表示的語法成分。由于描述語言的文法常常是遞歸定義分。由于描述語言的文法常常是遞歸定義的，因此相應(yīng)的這組函數(shù)（或子程序）必的，因此相應(yīng)的這組函數(shù)（或子程序）必然以相互遞歸的方式進(jìn)行調(diào)用，所以將此然以相互遞歸的方式進(jìn)行調(diào)用，所以將此種分析法稱為遞歸下降分析法。種分析法稱為遞歸下降分析法。 Compiler Construction Principles構(gòu)造遞歸下降分析程序的方法構(gòu)造遞歸下降分析程序的方法: : 為每個(gè)非終結(jié)符編制一個(gè)遞歸下降為每個(gè)非終結(jié)符編制一個(gè)遞歸下降分析函

45、數(shù)，每個(gè)函數(shù)名是相應(yīng)的非終結(jié)分析函數(shù)，每個(gè)函數(shù)名是相應(yīng)的非終結(jié)符，函數(shù)體則是根據(jù)規(guī)則右部符號(hào)串的符，函數(shù)體則是根據(jù)規(guī)則右部符號(hào)串的結(jié)構(gòu)和順序編寫。結(jié)構(gòu)和順序編寫。A12niVTiVN 12n=Compiler Construction Principles(1) 當(dāng)遇到終結(jié)符當(dāng)遇到終結(jié)符a時(shí)，則編寫語句時(shí)，則編寫語句 if (當(dāng)前讀來的輸入符號(hào)當(dāng)前讀來的輸入符號(hào)=a) 讀下一個(gè)輸入符號(hào)；讀下一個(gè)輸入符號(hào)； (2) 當(dāng)遇到非終結(jié)符當(dāng)遇到非終結(jié)符A時(shí)，則編寫語句調(diào)時(shí)，則編寫語句調(diào) 用用 A( )； Compiler Construction Principles(4) 當(dāng)某個(gè)非終結(jié)符的規(guī)則有多個(gè)候

46、選式當(dāng)某個(gè)非終結(jié)符的規(guī)則有多個(gè)候選式 時(shí)，按時(shí)，按LL(1)文法的條件能唯一地選文法的條件能唯一地選 擇一個(gè)候選式進(jìn)行推導(dǎo)。擇一個(gè)候選式進(jìn)行推導(dǎo)。 (3) 當(dāng)遇到規(guī)則當(dāng)遇到規(guī)則A 時(shí)，則編寫語句時(shí)，則編寫語句 if (當(dāng)前讀來的輸入符號(hào)當(dāng)前讀來的輸入符號(hào) FOLLOW(A) error( )；Compiler Construction PrinciplesE E + T | TT T * * F | FF (E) | id 例例 設(shè)有文法設(shè)有文法GE：試構(gòu)造一個(gè)識(shí)別該文法句子的遞歸下試構(gòu)造一個(gè)識(shí)別該文法句子的遞歸下降分析程序。降分析程序。 Compiler Construction Princ

47、iples分析分析 首先消去文法左遞歸，得到文法首先消去文法左遞歸，得到文法 GEE TEE +TE | T FTT * *FT | F (E) | idEE + T |TTT * * F |FF(E) | id Compiler Construction Principles 無左遞歸的文法不一定是無左遞歸的文法不一定是LL(1)文法，文法，根據(jù)根據(jù)LL(1)文法的判斷條件，對(duì)非終結(jié)符文法的判斷條件，對(duì)非終結(jié)符 E, T, F有：有： E TEE +TE | T FTT * *FT | F (E) | idCompiler Construction Principles SELECT(E +

48、TE)SELECT(E ) =FIRST(+TE)FOLLOW(E) = + ), # = SELECT(T * *FT)SELECT(T ) =FIRST(* *FT)FOLLOW(T) = * * ), #, + = Compiler Construction Principles SELECT(Fid )SELECT(F(E) = FIRST(id)FIRST(E)=id(=所以文法所以文法GE是是LL(1)文法。文法。 Compiler Construction Principles分析程序中定義兩個(gè)函數(shù)：分析程序中定義兩個(gè)函數(shù)：(1) 函數(shù)函數(shù) Scaner( ) 功能功能: 讀進(jìn)源

49、程序的下一個(gè)單詞符號(hào)讀進(jìn)源程序的下一個(gè)單詞符號(hào) 并將它放在全程變量并將它放在全程變量sym。(2) 函數(shù)函數(shù) error( ) 功能功能: 出錯(cuò)處理程序。出錯(cuò)處理程序。 Compiler Construction Principles 對(duì)文法對(duì)文法GE可寫出相應(yīng)的遞歸下降分可寫出相應(yīng)的遞歸下降分析程序如下：析程序如下： E TEE +TE | T FTT * *FT | F (E) | idmain( ) Scaner ( ); E ( ); if (sym= =#) printf (“success”); else printf (“fail”); Compiler Construction

50、 PrinciplesE ( ) T( ); E( ); E( ) if (sym = =+) Scaner( ); T ( ) ; E ( ); else if (sym!=)&(sym!=#) error( ); E TEE +TE | T FT T * *FT | F (E) | idCompiler Construction PrinciplesT ( ) F ( ) ; T ( ); E TEE +TE | T FT T * *FT | F (E) | idT ( ) if (sym = =* *) Scaner( ); F ( ) ; T ( ); else if (sym fol

51、low(T) error( ); Compiler Construction PrinciplesF ( ) if (sym= = id) Scaner ( ); else if (sym= = () Scaner( ) ; E ( ); if (sym = = ) ) Scaner ( ); else error ( ); else error ( ); E TE E +TE | T FT T * *FT | F (E) | idCompiler Construction Principlesmain( ) Scaner ( ); E ( ); if (sym= =#) printf (“s

52、uccess”); else printf (“fail”); id + id #E ( ) T( ); E ( ); T ( ) F ( ) ; T ( ); 見見F見見E見見T返回下一頁返回下一頁Compiler Construction PrinciplesF ( ) if (sym= = id) Scaner ( ); else if (sym= = () Scaner( ) ; E ( ); if (sym = = ) ) Scaner ( ); else error ( ); else error ( ); 返回返回TCompiler Construction Principles

53、T ( ) if (sym = =* *) Scaner( ); F ( ) ; T ( ); else if (sym follow(T) error( ); follow(T)=+, ), # 返回返回TCompiler Construction PrinciplesE ( ) if (sym = =+) Scaner( ); T ( ) ; E ( ); else if (sym!=)&(sym!=#) error( ); 返回返回E見見T返回返回ECompiler Construction Principles 對(duì)這個(gè)例子，若采用擴(kuò)充的對(duì)這個(gè)例子，若采用擴(kuò)充的BNF表示表示法改寫文法，

54、得到法改寫文法，得到GE：E T +T T F * *F F (E) | idEE + T |TTT * * F |FF(E) | id Compiler Construction Principles 該文法是該文法是LL(1)文法，其遞歸下降分文法，其遞歸下降分析程序中主函數(shù)和函數(shù)析程序中主函數(shù)和函數(shù)F( )同上，對(duì)函同上，對(duì)函數(shù)數(shù)E( )和函數(shù)和函數(shù)T( )用用while語句描述如下：語句描述如下： Compiler Construction PrinciplesE ( ) T ( ); while ( sym = =+) Scanner ( ); T ( ); T ( ) F ( );

55、 while ( sym = =*) Scanner ( ); F ( ); E T +T T F * *F F (E) | idCompiler Construction Principles缺點(diǎn)缺點(diǎn): : 對(duì)文法要求高，必須是對(duì)文法要求高，必須是LL(1)LL(1)文文 法，同時(shí)由于遞歸調(diào)用較多，影法，同時(shí)由于遞歸調(diào)用較多，影 響分析器的效率。響分析器的效率。 優(yōu)點(diǎn)優(yōu)點(diǎn): : 遞歸下降分析法簡(jiǎn)單、直觀，易遞歸下降分析法簡(jiǎn)單、直觀，易 于構(gòu)造分析程序。于構(gòu)造分析程序。 Compiler Construction Principles 預(yù)測(cè)分析法預(yù)測(cè)分析法(LL(1)分析法分析法)是確是確定的

56、自上而下分析的另一種方法，定的自上而下分析的另一種方法，采用這種方法進(jìn)行語法分析要求采用這種方法進(jìn)行語法分析要求描述語言的文法是描述語言的文法是LL(1)文法。文法。 Compiler Construction Principles預(yù)測(cè)分析器的邏輯結(jié)構(gòu)預(yù)測(cè)分析器的邏輯結(jié)構(gòu)預(yù)測(cè)分析表預(yù)測(cè)分析表總控程序總控程序 a1 a2 ai an #T j 輸入串輸入串 X #輸出輸出分分析析棧棧Compiler Construction Principles 輸入緩沖區(qū)輸入緩沖區(qū)Tj中存放待分析的輸入符中存放待分析的輸入符號(hào)串，它以右界符號(hào)串，它以右界符 # 或或#作為結(jié)束。作為結(jié)束。 分析棧分析棧SK中存

57、放替換當(dāng)前非終結(jié)符的中存放替換當(dāng)前非終結(jié)符的某規(guī)則右部符號(hào)串，句子左界符某規(guī)則右部符號(hào)串，句子左界符#或或#存入棧底。存入棧底。 預(yù)測(cè)分析表是一個(gè)二維形式的矩陣，預(yù)測(cè)分析表是一個(gè)二維形式的矩陣，其中矩陣的行為文法非終結(jié)符，矩陣的其中矩陣的行為文法非終結(jié)符，矩陣的列為文法終結(jié)符或列為文法終結(jié)符或#或或# 。見表見表Compiler Construction Principles id + * * ( ) # E E T T FETEETEE +TEEETFTTFTTT TT* *FTFidF(E) 預(yù)測(cè)分析器的總控程序在任何時(shí)候都是根據(jù)棧預(yù)測(cè)分析器的總控程序在任何時(shí)候都是根據(jù)棧頂符號(hào)和當(dāng)前輸入符

58、號(hào)頂符號(hào)和當(dāng)前輸入符號(hào)a來決定分析器的動(dòng)作。來決定分析器的動(dòng)作。Compiler Construction Principles#和文法開始符號(hào)進(jìn)和文法開始符號(hào)進(jìn)S棧棧第一個(gè)輸入符號(hào)讀進(jìn)第一個(gè)輸入符號(hào)讀進(jìn)aS棧頂符號(hào)上托出去放棧頂符號(hào)上托出去放 X中中 XVT?X=a ?Y將下一個(gè)輸將下一個(gè)輸入符號(hào)讀入入符號(hào)讀入aY出錯(cuò)出錯(cuò)NNX=# ?X=a ?YSTOPYN查查MX,a=Xy1y2yn ?N將將y1y2yn逆序放逆序放入入S棧中，若右部棧中，若右部符號(hào)串為符號(hào)串為，則，則不進(jìn)不進(jìn)S棧棧Y出錯(cuò)出錯(cuò)NCompiler Construction Principles 預(yù)測(cè)分析器的總控程序?qū)τ诓煌?/p>

59、的預(yù)測(cè)分析器的總控程序?qū)τ诓煌腖L(1)文法都是相同的，而預(yù)測(cè)分析表對(duì)文法都是相同的，而預(yù)測(cè)分析表對(duì)于不同的于不同的LL(1)文法是不相同的。文法是不相同的。 構(gòu)造預(yù)測(cè)分析表的方法：構(gòu)造預(yù)測(cè)分析表的方法：輸入輸入: 文法文法G輸出輸出: 預(yù)測(cè)分析表預(yù)測(cè)分析表M Compiler Construction Principles方法：方法： 1 1. .計(jì)算文法計(jì)算文法GG的每一非終結(jié)符的的每一非終結(jié)符的FIRSTFIRST集集 和和FOLLOWFOLLOW集。集。 2.對(duì)文法的每個(gè)規(guī)則對(duì)文法的每個(gè)規(guī)則A, 若若aFIRST() , 則置則置MA, a= A 。 3.若若FIRST(), 則對(duì)則

60、對(duì) 任任bFOLLOW(A), 則置則置MA, b= A Compiler Construction Principles 4. 4.把分析表中每個(gè)未定義的元素標(biāo)上出把分析表中每個(gè)未定義的元素標(biāo)上出 錯(cuò)標(biāo)志錯(cuò)標(biāo)志errorerror（表中用空白格表示）（表中用空白格表示）例例 設(shè)有文法設(shè)有文法GEGE： 試構(gòu)造該文法的預(yù)測(cè)分析表。試構(gòu)造該文法的預(yù)測(cè)分析表。 E TEE +TE | T FTT * *FT | F (E) | idCompiler Construction Principles E E T T F (, id ), # (, id + +, ), # (, id +, ), #,