1、Compiler Construction Principles 本章討論程序語言的語法分析方本章討論程序語言的語法分析方法，以及語法分析程序的設計原理法，以及語法分析程序的設計原理和實現技術。和實現技術。Compiler Construction Principlesu語法分析程序的功能和語法分析方法u 自頂向下語法分析法u 自底向上算符優先分析法u LR分析法 Compiler Construction Principles語法分析程序的功能語法分析程序的功能 語法分析器語法分析器詞法分析后詞法分析后的單詞串的單詞串語法成分構語法成分構成的語法樹成的語法樹或錯誤表或錯誤表Compiler

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

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

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

5、發生回溯。 Compiler Construction Principles4.2.1 4.2.1 非確定的自上而下分析法的非確定的自上而下分析法的思想思想例例 設有文法設有文法GS：S aAbA de | d輸入串輸入串 W=adbS a A bd e匹配失敗、這時應回匹配失敗、這時應回溯溯, ,選擇選擇A A的其它可能的其它可能的規則重新匹配。的規則重新匹配。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建立語法建立語法樹的過程，實際也是設法為輸入串建樹的過程，實際也是設法為輸入串建立一個最左推導序列：立一個最左推導序列：SaAbadb。 由于對輸入串從左向右進行掃描，由于對輸入串從左向右進行掃描，使用最左推導，才能保證按從左到右使用最左推導，才能保證按從左到右掃描順序匹配輸入串。掃描順序匹配輸入串。Compiler Construction Principles4.2.1 4.2.1 非確定的自上而下分析法的非確

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

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

9、結符A去匹配輸入串時去匹配輸入串時,使當前句使當前句型的最左非終結符仍然為型的最左非終結符仍然為A。 也就是說，在沒有讀進任何輸入符號的也就是說，在沒有讀進任何輸入符號的情況下，又重新要求情況下，又重新要求A去進行新的匹配。去進行新的匹配。于是，造成無窮循環。于是，造成無窮循環。 Compiler Construction Principles4.2.2 4.2.2 文法的左遞歸性和回溯的文法的左遞歸性和回溯的消除消除 對含直接左遞歸的規則進行等價變換，對含直接左遞歸的規則進行等價變換，消除左遞歸消除左遞歸 引進一個新的非終結符，把含左遞歸引進一個新的非終結符，把含左遞歸 的規則改寫成右遞歸。

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

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

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

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

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

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

16、部，第二個右有兩個右部，第二個右部能推導出部能推導出串且兩個右部左端第一串且兩個右部左端第一個符號不相同，但在分析符號串個符號不相同，但在分析符號串Wx 時出現回溯。時出現回溯。 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、，在自上而下分析過程綜上所述，在自上而下分析過程中，為了避免回溯，中，為了避免回溯， 對描述語言的對描述語言的文法有一定的要求文法有一定的要求: :Compiler Construction Principles 對文法的某個非終結符對文法的某個非終結符A,當它有多當它有多個侯選式時個侯選式時: 若用若用A匹配輸入串時匹配輸入串時,能根據當前讀到能根據當前讀到的輸入符號的輸入符號a唯一地選擇一條規則去匹唯一地選擇一條規則去匹備輸入串?；蛘哒f，能唯一地選擇一條備輸入串?；蛘哒f，能唯一地選擇一條規則進行推導。規則進行推導。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)文法的判斷條件，需引文法的判斷條件，需引進三個相關集：進三個相關集： FIRST集集 FOLLOW集集SELECT集集 Compiler Construction PrinciplesLL(1)文法的判斷條件文法的判斷條件 設設是文法是文法G的任一符號

19、串，定義文的任一符號串，定義文 法符號串法符號串的首符號集合。的首符號集合。FIRST() = a | a且且 aVT *,則規定則規定 FIRST()若若 *Compiler Construction PrinciplesLL(1)文法的判斷條件文法的判斷條件例例 設有文法設有文法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) 設文法設文法G的開始符號為的

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

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

22、ompiler Construction PrinciplesLL(1)文法的判斷條件文法的判斷條件例例 設有文法設有文法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 | Compiler C

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

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

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

26、ion Principles例例 設有文法設有文法GSSaAbDe | dABSD | eBSAc | cD | DSe | 1. 計算文法計算文法GS每個非終結符的每個非終結符的FIRST集集 和和FOLLOW集集 。2. 判斷文法判斷文法GS 是否是否LL(1)文法。文法。 Compiler Construction Principles對每一文法符號對每一文法符號XV, 求求FIRST(X)的規則的規則: FIRST() = a | a且且 aVT *,則規定則規定 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,d,c,

28、e SaAbDe | dABSD | eBSAc | cD | DSe | 問問: 能否能否 因為從因為從 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 ,*則規定則規定 #FOLLOW(A)。 求求FOLLOW(A)的規則的規則:1. 對文法的開始符號對文法的開始符號S , 令令#FOLLOW(S)2.若若 AB是一條規則是一條規則, 則把則

29、把FOLLOW(A)加到加到FOLLOW(B)中中3.若若 AB是一條規則是一條規則, 則將則將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 Compiler Co

30、nstruction Principles根據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 Principles

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

32、能進行確文法，因此對輸入串不能進行確定的自上而下分析。定的自上而下分析。 Compiler Construction Principles例例2 設有文法設有文法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)文法，對任文法，對任何輸入串何輸入串W可進行確定的分析。可進行確定的分析。 Compiler Construction Principles例例3 設有文法設有文法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)= a S

34、ELECT(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 該文法為該文法為LL(1)文法文法Compiler Construction Principles例例4 設有文法設有文法GS:S AB | bCA b | B aD | C AD | D aS | c 試判斷該文法是否試判斷該文法是否LL(1)文法文法 分析分析 對文法某個非終結符對文法某個非終結符,當有多個候當有多個候選式時選式

35、時, 求規則的求規則的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)=# 該文法不為該文法不為LL(1)文法文法Compiler Construction PrinciplesLL(1)LL(1)文法的判斷條件文法的判斷條

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

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

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

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

40、: 該文法是非該文法是非LL(1)文法，該文法有公共文法，該文法有公共左因子，利用提取公共左因子的方法對左因子，利用提取公共左因子的方法對其進行改寫，我們得到其進行改寫，我們得到 S aAbA de | dCompiler Construction Principles不難驗證改寫后的文法為不難驗證改寫后的文法為LL(1)文法。文法。 因為因為 SELECT(A e)SELECT(A ) =e, b= S aAbA dAA e | Compiler Construction Principles例例2 2 設有文法設有文法GS:GS:S ad | AeA aS | bA將將A的兩條規則代入非終

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

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

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

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

45、數名是相應的非終結分析函數，每個函數名是相應的非終結符，函數體則是根據規則右部符號串的符，函數體則是根據規則右部符號串的結構和順序編寫。結構和順序編寫。A12niVTiVN 12n=Compiler Construction Principles(1) 當遇到終結符當遇到終結符a時，則編寫語句時，則編寫語句 if (當前讀來的輸入符號當前讀來的輸入符號=a) 讀下一個輸入符號；讀下一個輸入符號； (2) 當遇到非終結符當遇到非終結符A時，則編寫語句調時，則編寫語句調 用用 A( )； Compiler Construction Principles(4) 當某個非終結符的規則有多個候選式當某個

46、非終結符的規則有多個候選式 時，按時，按LL(1)文法的條件能唯一地選文法的條件能唯一地選 擇一個候選式進行推導。擇一個候選式進行推導。 (3) 當遇到規則當遇到規則A 時，則編寫語句時，則編寫語句 if (當前讀來的輸入符號當前讀來的輸入符號 FOLLOW(A) error( )；Compiler Construction PrinciplesE E + T | TT T * * F | FF (E) | id 例例 設有文法設有文法GE：試構造一個識別該文法句子的遞歸下試構造一個識別該文法句子的遞歸下降分析程序。降分析程序。 Compiler Construction Principles

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

48、LECT(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分析程序中定義兩個函數：分析程序中定義兩個函數：(1) 函數函數 Scaner( ) 功能功能: 讀進源程序的下一

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

50、ciplesE ( ) 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 foll

51、ow(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 (“su

52、ccess”); 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 PrinciplesT

53、 ( ) 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 對這個例子，若采用擴充的對這個例子，若采用擴充的BNF表示表示法改寫

54、文法，得到法改寫文法，得到GE：E T +T T F * *F F (E) | idEE + T |TTT * * F |FF(E) | id Compiler Construction Principles 該文法是該文法是LL(1)文法，其遞歸下降分文法，其遞歸下降分析程序中主函數和函數析程序中主函數和函數F( )同上，對函同上，對函數數E( )和函數和函數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缺點缺點: : 對文法要求高，必須是對文法要求高，必須是LL(1)LL(1)文文 法，同時由于遞歸調用較多，影法，同時由于遞歸調用較多，影 響分析器的效率。響分析器的效率。 優點優點: : 遞歸下降分析法簡單、直觀，易遞歸下降分析法簡單、直觀，易 于構造分析程序。于構造分析程序。 Compiler Construction Principles 預測分析法預測分析法(LL(1)分析法分析法)是確是

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

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

58、輸入符號頂符號和當前輸入符號a來決定分析器的動作。來決定分析器的動作。Compiler Construction Principles#和文法開始符號進和文法開始符號進S棧棧第一個輸入符號讀進第一個輸入符號讀進aS棧頂符號上托出去放棧頂符號上托出去放 X中中 XVT?X=a ?Y將下一個輸將下一個輸入符號讀入入符號讀入aY出錯出錯NNX=# ?X=a ?YSTOPYN查查MX,a=Xy1y2yn ?N將將y1y2yn逆序放逆序放入入S棧中，若右部棧中，若右部符號串為符號串為，則，則不進不進S棧棧Y出錯出錯NCompiler Construction Principles 預測分析器的總控程序對

59、于不同的預測分析器的總控程序對于不同的LL(1)文法都是相同的，而預測分析表對文法都是相同的，而預測分析表對于不同的于不同的LL(1)文法是不相同的。文法是不相同的。 構造預測分析表的方法：構造預測分析表的方法：輸入輸入: 文法文法G輸出輸出: 預測分析表預測分析表M Compiler Construction Principles方法：方法： 1. 1.計算文法計算文法GG的每一非終結符的的每一非終結符的FIRSTFIRST集集 和和FOLLOWFOLLOW集。集。 2.對文法的每個規則對文法的每個規則A, 若若aFIRST() , 則置則置MA, a= A 。 3.若若FIRST(), 則

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