語法分析-自上而下分析

1、第四章語法分析自上而下分析知識結(jié)構(gòu)：帶回溯分析法回溯自上而下分析面臨的問題左遞歸問題的解決語法分析求 FIRST 、FOLLOW 集合的算法自上而下分析LL(1) 分析法證明 LL(1) 文法構(gòu)造 LL(1) 分析表遞歸子程序的構(gòu)造思想遞歸子程序法遞歸子程序的特點遞歸子程序的設(shè)計第一節(jié)語法分析綜述一、語法分析的任務(wù)按照語言即定的語法規(guī)則，對字符串形式的源程序進(jìn)行語法檢查，并識別出相應(yīng)的語法成分。即語法結(jié)構(gòu)是否符合語法規(guī)則。二、語法分析器在編譯程序中的地位（一遍掃描）源程序單詞符號分析樹詞法分析器語法分析器語義分析中間代碼生成取下一個單詞符號表三、語法分析方法通常把語法分析方法分為兩大類，既自上

2、而下分析與自下而上分析。1、自上而下分析方法實際上是一種產(chǎn)生的方法，分析過程是一個推導(dǎo)過程。自上而下分析過程從文法 G 的開始符號S 出發(fā)，通過反復(fù)使用產(chǎn)生式，逐步推導(dǎo)出與輸入的符號串完全相匹配的句子。采用最左推導(dǎo)，以文法開始符號為根結(jié)點，逐步為輸入串自上而下地構(gòu)造一棵語法樹。面臨的輸入符號為a，A 所有的產(chǎn)生式：A12n若 aFISRT(i)，則指派去執(zhí)行匹配任務(wù)。若 a 不屬于任何一個候選首字符集，則：a、若屬于某個 FISRT(i)且 aFOLLOW(A) ，則讓 A與自動匹配；b、否則， a 的出現(xiàn)是一種錯誤。例：設(shè)有文法G 和輸入符號串W ： a*a+aG： SaAaABaAB+-*

3、/推導(dǎo)過程：SaAaBaAa*aAa*aBaAa*a+aAa*a+a=W構(gòu)造語法樹：SaABaA*BaA+自上而下分析法自上而下分析法又可分為確定和不確定的兩種。不確定的分析法（帶回溯）是一種窮舉的試探方法，效率低、代價高，極少使用。確定的分析法（不帶回溯）實現(xiàn)方法簡單、直觀，便于手工構(gòu)造或自動生成語法分析器，是目前常用的方法之一。但是對文法有一定的限制。2、自下而上分析法自下而上分析過程分析過程是歸約過程。從給定的輸入串W 開始，不斷尋找與文法 G 中某個產(chǎn)生式P 的侯選式（右部）進(jìn)行匹配，并用P 代替也稱為歸約。自下而上分析法算符優(yōu)先分析法定義算符（廣義講是文法的終結(jié)符號）之間的某種優(yōu)先和

4、結(jié)合關(guān)系，借助這種關(guān)系來尋找并確定可歸約字符串，并進(jìn)行歸約。 LR 分析法是一類自左向右對輸入串進(jìn)行掃描的自下而上分析方法，分析過程是規(guī)范歸約的序列。適用于語法分析器的自動構(gòu)造。第二節(jié) 自上而下分析面臨的問題一、不確定的自上而下分析方法是從文法的開始 S 出發(fā)，試圖用一切可能的方法向下推導(dǎo)，產(chǎn)生句子，這種分析過程的本質(zhì)是一種試探推導(dǎo)過程。例：文法 G SaAd Aaba構(gòu)造 W=aad 的最左推導(dǎo)： SaAdaad 。構(gòu)造語法樹：產(chǎn)生樹的根結(jié)點，即文法的開始符號。選用文法G 的文法規(guī)則去延伸樹。判斷當(dāng)前延伸的子結(jié)與輸入串掃描到的字符是否匹配。若不匹配注銷掉當(dāng)前延伸的子樹，選用文法規(guī)則的另一個產(chǎn)

5、生式延伸分析樹。直到輸入串與語法樹末端結(jié)點相匹配，分析結(jié)束。SSSaAdaAdaAdaba這種試探識別句子的過程，只會使分析的過程不確定。二、不確定性的原因由于分析過程中選擇的侯選式不確定，造成輸入串匹配的假象，甚至?xí)?dǎo)致算法實現(xiàn)的失敗。1、左遞歸問題由于采用最左推導(dǎo)，左遞歸將使得輸入串的分析過程陷入無限循環(huán)之中。2、回溯問題采用試探的方法， 如匹配不成功回溯到前面分析的某一步?？赡艹霈F(xiàn)假匹配，造成對輸入串識別的失敗。不能準(zhǔn)確報告輸入串的出錯位置。三、確定的自上而下分析方法1、確定的自上而下分析方法的必要條件消除文法中的左遞歸；消除文法中的回溯問題。2、消除文法的左遞歸文法的左遞歸可以通過對文

6、法產(chǎn)生式進(jìn)行改寫，使之不含有左遞歸的非終結(jié)符號。左遞歸一般有兩種情況，直接左遞歸和間接左遞歸。直接左遞歸如果文法中任意一個非終結(jié)符P，若 PP（VNUVT），并且在最左推導(dǎo)中有PP形式，稱為直接左遞歸。間接左遞歸+在最左推導(dǎo)中有P=> P形式，稱為間接左遞歸。消除直接左遞歸PP|改寫為： PPPP例：表達(dá)式文法EE+TT改寫為： ETEE+TETT*FF改寫為： TFTT*FTF(E)i消除文法的左遞歸一般規(guī)則PP1P2 Pm12ni改寫為：P1P2Pn PP1P2Pm P消除間接左遞歸ABBC間接左遞歸 : ABC ACA例：文法 GSQc|cQRb|bRSa|a最左推導(dǎo)： SQcRb

7、cSabc （間接左遞歸）清除間接左遞歸非終結(jié)符排序為R，Q，S 。R 不存在直接左遞歸，把R 代入Q 的規(guī)則：QSab | ab | b再把 Q代入 S：SSabc | abc | bc | c消除 S 的左遞歸：SabcS| bcS| cSSabcS|Q 和 R 的產(chǎn)生式不再被引用，將Q 和 R 刪除。非終結(jié)符排序為 S，Q， R。S 不存在直接左遞歸， Q 的產(chǎn)生式不包含 S，再把 S 代入得到 R:RRbca | bca | ca | a消除 S 的左遞歸：RbcaR| caR| aRRbcaR|改寫為：SQc|c不能刪除QRb|b不能刪除RbcaR|caR|aRRbcaR|3、消除回

8、溯，提取左因子消除回朔文法 G 不包含左遞歸， 則 G 中非終結(jié)符號的每個候選式首字符集 FIRST （ ）為：FIRST （）=a*（ VNUVT） *=> a,aVT ，若*，則FIRST （）。=>提取最左公共因子采用提取最左公共因子的方法改寫文法，使得所有侯選式的首字符集兩兩不相交。A12n12m提取公因子 :A(12n)12m改寫后為 :A A12A12n4、確定的自上而下分析方法預(yù)測分析法（ LL（ 1）分析法）。m遞歸子程序法。第三節(jié)預(yù)測分析法（ LL （ 1）分析法）一、 LL （ 1）分析方法1、是按自左（第一個“ L）” 向右的順序掃描輸入字符串；2、在分析過程

9、中產(chǎn)生句子的最左（第二個“L”）推導(dǎo)；3、 “1”表示在分析過程中，每一步推導(dǎo)，最多只能向前查看（向右掃描）一個字符。二、 LL （ K）分析方法如果分析過程的每一步推導(dǎo)，要向前查看K 個輸入字符，則稱為 LL （K）分析法。三、 LL （ 1）文法的定義該文法是上下文無關(guān)的一個子集，是自上而下分析技術(shù)的一類文法。四、 LL （ 1）分析法的必要條件1、文法中的非終結(jié)符號不包含左遞歸；2、對于文法中的每一個非終結(jié)符A 的各個產(chǎn)生式的侯選首字符集兩兩不相交。對于產(chǎn)生式A:若，證明侯選式，的首字符集是否相交。FIRST （）FIRST （）= 若，證明 FIRST （ A）和 FOLLOW （A）

10、是否相交。FIRST （ A）FOLLOW （ A） =五、構(gòu)造 FIRST 集合的算法對每一文法符號X（VNUVT）*1、若 XVT ，則 FIRST （X）=X 。2、若 XVN ，且有產(chǎn)生式Xa，aVT，則 aFIRST（X）。3、若 XVN ，X，則FIRST （ X）4、若 XVN ，且 Y1， Y2，Y iVN，*而有產(chǎn)生式XY1，Y n。當(dāng) Y1，Y2，Yi-1 都 =>時，（其中 1in），則 FIRST （Y1，） -，F(xiàn)IRST （Yi-1 ）-，F(xiàn)IRST （ Yi）都包含在 FIRST （X）中。若 FIRST （ Yj）包含把加到 FIRST （X ）中。例文法

11、GE TEE +TE| T FTT *FT| F（ E）|iFIRST （ E）=FIRST （T）=FIRST （F）= （， i ）FIRST （ E） = + ，F(xiàn)IRST （ T）= * ，六、構(gòu)造 FOLLOW 集合的算法FOLLOW (A)=a | S*=> .Aa . , aVT *則 # FOLLOW (A)若 S=>A,FOLLOW (A) 為所有句型中緊跟在非終結(jié)符A 后面的所有終結(jié)符集合。構(gòu)造算法：1、對文法開始符號S，將“#”置于FOLLOW(S) 中。即 FOLLOW(S) =#。2、若 A B是一個產(chǎn)生式，則把FIRST （）-加至FOLLOW(B) 中

12、。3、若 A B 是一個產(chǎn)生式，或A B是一個產(chǎn)生式，而（即FIRST （）；則把 FOLLOW(A) 加至 FOLLOW(B)中。例文法GE TEE +TE| T FTT *FT| F（E）|i求 FOLLOW （E）：因為F（E），所以FIRST（）加入FOLLOW(E)中，F(xiàn)OLLOW(E) =)；又因為ETE,E 是文法的開始符號，則#加至 FOLLOW(E)中，所以FOLLOW(E)=#U FOLLOW(E)=#,)。求 FOLLOW （ E）：因為 ETE, 滿足算法 (3) 若 A B 是一個產(chǎn)生式，則把 FOLLOW(A) 加至 FOLLOW(B) 中，所以FOLLOW(E)=

13、 FOLLOW(E)U FOLLOW(E)= #， )求 FOLLOW （T）：因為 ETE , 滿足算法若A B是一個產(chǎn)生式，則把FIRST （）加至 FOLLOW(B) 中，所以 FOLLOW(T) = FOLLOW(T) U FIRST （ E） = +又因為E，滿足算法(3)若AB是一個產(chǎn)生式，而，則把FOLLOW(A)加至FOLLOW(B)中。所以FOLLOW(T) = FOLLOW(E)U FOLLOW(T)=#， )U+= #， )，+求 FOLLOW （T ）：因為 TFT,滿足算法 (3) 若 A B 是一個產(chǎn)生式，則把 FOLLOW(A) 加至 FOLLOW(B) 中，所以

14、FOLLOW(T) = FOLLOW(T)U FOLLOW(T)= #， )，+求 FOLLOW （F）：因為 TFT, 滿足算法若A B是一個產(chǎn)生式，則把FIRST （）加至 FOLLOW(B) 中，所以FOLLOW(F) = FOLLOW(F)U FIRST （ T） = *又因為T，滿足算法(3) 若A B是一個產(chǎn)生式，而，則把FOLLOW(A)加至FOLLOW(B)中。所以FOLLOW(F) = FOLLOW(T)U FOLLOW(F)=#，)，+U*=#， )，+，*連續(xù)使用上述三條規(guī)則，直到每個FOLLOW不再增大為止。FOLLOW(E)= FOLLOW(E)=#， )FOLLOW

15、(T)= FOLLOW(T)=#，)， +FOLLOW(F)=#，)， +，*七、證明上述文法是否為LL(1) 文法對于產(chǎn)生式A:1、若，證明侯選式，的首字符集是否相交。FIRST（）FIRST（）=例： F（ E）iFIRST （）FIRST （i）= 2、若，證明FIRST （A）和 FOLLOWFIRST （ A）FOLLOW （ A） =（ A）是否相交。例： EFIRST （ E）FOLLOW （ E）= +， ），# = 八、構(gòu)造分析表的算法1、對文法 G 的每個產(chǎn)生式A執(zhí)行第二步和第三步；2、對每個終結(jié)符aFIRST(),把A加至MA,a中；3、若FIRST（），則對任何bFOL

16、LOW(A)把 A（或A）加至 MA,b 中；4、把所有無定義的MA ，a標(biāo)上“出錯標(biāo)志”例：ETE ， E+TE |TFT ， T *FT |F（E） |i求其 FIRST 的集合 :FIRST （ E）=FIRST （T）=FIRST （F）= （， i ）FIRST （ E） = + ，F(xiàn)IRST （T）= * ，求其 FOLLOW 的集合 :FOLLOW(E)= FOLLOW(E)=#， )FOLLOW(T)= FOLLOW(T)=#， )， +FOLLOW(F)=#， )， +，*根據(jù)算法構(gòu)造LL （ 1）的分析表 :終結(jié)符非終結(jié)符i+*（）#ETETEE+TE九、 LL （ 1）分

17、析器的邏輯結(jié)構(gòu)與分析程序1、LL （ 1）分析器的邏輯結(jié)構(gòu)LL（ 1）分析法， 由總控程序控制輸入字符串，在一張 LL（1）分析表和一個分析工作棧上運行，而完成語法分析任務(wù)的。輸入字符串a(chǎn)1a2aian總控程序X分析表分析棧#其中：分析表，實現(xiàn)相應(yīng)的分析動作，即對Ai，aj，設(shè) A i表示當(dāng)前分析工作棧頂為Ai，輸入字符為aj 時，應(yīng)選用 Ai進(jìn)行推導(dǎo)。分析工作棧，用于存放分析過程中的文法符號。分析工作棧初始化時，在工作棧頂寫入一個“#”，再寫入文法開始符號?？偪爻绦颍罁?jù)分析工作棧和分析表聯(lián)合控制輸入串的識別和分析。2、分析程序的工作原理把“”和文法開始符號推入分析工作棧；設(shè)置指示器的初始值

18、，用第一個輸入符號（終結(jié)符號）與分析工作棧頂文法符號進(jìn)行匹配。設(shè)在某一步的分析工作棧與輸入串的當(dāng)前工作狀態(tài)：X1X2Xm-1 Xm 為分析工作棧中的當(dāng)前狀態(tài)；aiai+1#為輸入串的當(dāng)前狀態(tài)。若 XmVN，則以 Xm 及 ai 組成符號對（ Xm，ai）查分析表 MX m ，ai，設(shè) XmUVW ，將 Xm 從分析工作棧頂退出，并將 UVW 按反向?qū)懭敕治龉ぷ鳁Ｖ小Ｈ鬗X m， ai= “Error ”，則調(diào)用出錯處理程序。若 XmVT 并且 Xm=a i，則表明分析工作棧頂?shù)姆柵c當(dāng)前輸入符號相匹配，將工作棧頂?shù)姆朮m 退出，輸入符號指針向右移一位。若Xm =#，則表明輸入符號串已完全匹配

19、，分析成功結(jié)束分析工作。3、分析程序的算法（P77 ）例：對輸入串# i*i+i # 的預(yù)測分析過程P78第四節(jié)遞歸下降分析程序的構(gòu)造一、遞歸下降分析程序的構(gòu)造方法對文法的每個非終結(jié)符號，根據(jù)各侯選式的結(jié)構(gòu)，編寫一個對應(yīng)的子程序，完成非終結(jié)符相應(yīng)的語法成分的識別和分析任務(wù)。二、遞歸下降分析程序的功能對某個非終結(jié)符，用產(chǎn)生式規(guī)則的右部符號進(jìn)行匹配。三、遞歸下降分析程序的特點1、程序結(jié)構(gòu)清晰，易于手工操作。2、對語義處理靈活。四、遞歸下降分析法的必要條件必須是不包含左遞歸和回溯的上下文無關(guān)文法。五、遞歸下降分析程序的設(shè)計P74第五節(jié)預(yù)測分析法的錯誤處理一、出錯情況1、工作棧頂終結(jié)符與輸入符號不匹配

20、。2、對應(yīng) MA ， a中為空 (Error) 。二、出錯處理1、報告出錯（出錯位置，出錯性質(zhì)） 。2、處理出錯情況，使語法分析繼續(xù)下去：若 MA ， a中為空 (Error), 跳過輸入符號a，若該項為同步(synch) ，則退出工作棧頂?shù)姆墙K結(jié)符 A。工作棧頂?shù)慕K結(jié)符無法與輸入符號匹配，則彈出該符號。第六節(jié)學(xué)習(xí)與理解一、填空題自上而下語法分析方法的基本思想是：從文法的開始符號出發(fā)。不斷建立最左直接推導(dǎo) ，試圖構(gòu)造一個推導(dǎo)序列，最終由它推導(dǎo)出與輸入符號串相同的符號串 。自上而下分析方法會遇到的主要問題有回溯和左遞歸 。在語法分析中， 最常見的兩種方法一定是自上而下 分析法，另一種是 自下而上

21、 分析法。二、選擇題編譯過程中，語法分析器的任務(wù)是B，C，D。A 、分析單詞是怎樣構(gòu)成的B 、分析單詞串是如何構(gòu)成語句的C 、分析語句是如何構(gòu)成程序的D 、分析程序結(jié)構(gòu)高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于B 分析方法。A、自左至右C、自下而上B、自上而下D、自右至左三、解答題已知文法G：AaAa該文法是LL （1）文法嗎？為什么？若采用 LL （ 1）方法進(jìn)行分析，如何得到該文法的LL （1）分析表。若輸入串“aaaa ，” 請給出語法分析過程。解：因為FOLLOW （A） FOLLOW （A ）FIRST （A）=a ，#，造成 FOLLOW （ A）FIRST （A）

22、=a ， #a ，所以該文法不是LL（ 1）文法。若采用LL （1）方法進(jìn)行語法分析，必須修改該文法。因該文法產(chǎn)生偶數(shù)（可以為0）個 a，所以得到文法G ：AaaA。此時FOLLOW （ A）=# ，因此FOLLOW （ A） FIRST （ A）=# a ， = 所以文法 G 是 LL（ 1）文法。該文法的 LL（1）分析表：V Ta#V NAAaaAA對符號串“aaaa ”的分析過程：步驟分析棧輸入串產(chǎn)生式 / 動作1#Aaaaa#AaaA2#Aaaaaaa#匹配3#Aaaaa#匹配4#Aaa#AaaA5#Aaaaa#匹配6#Aaa#匹配7#A#A8#接受設(shè)文法 G(A) ：AaABcaA

23、BBbd試給出文法G(A) 等價的 LL （1）文法 G(A) 。構(gòu)造 G(A) 的 LL（1）分析表，給出輸入串a(chǎn)adc# 的分析過程。解答：由于該文法G(A)AaABca存在回溯BBbd存在左遞歸所以不是 LL(1) 文法。改寫文法G(A)AaABca提取最左公共因子使得：Aa（ABc），定義 AABc改寫后的產(chǎn)生式：A aA A ABc又因為： BBbd 存在左遞歸，消除左遞歸后的產(chǎn)生式：BdBBbB構(gòu)造文法每一個非終結(jié)符號FIRST 和 FOLLOW 的集合。a、構(gòu)造文法每一個非終結(jié)符號FIRST 的集合FIRST （A）=aFIRST （A）=a ，F(xiàn)IRST （B）=dFIRST

24、（B）=b,b、構(gòu)造文法每一個非終結(jié)符號FOLLOW 的集合因為 AaA 和 AABc，所以 :FOLLOW （A）=#FIRST （B ） =#,d因為 AaA ，所以 FOLLOW （A ）= FOLLOW （A）=#,d因為 AABc ，所以 FOLLOW （B）=c因為 BdB, 所以 FOLLOW （B）=FOLLOW （B），最終結(jié)果:FOLLOW （A） = FOLLOW （ A） =# ， d。FOLLOW （B） = FOLLOW （ B） =c證明該文法是否是LL （1）文法？因為文法G(A) 中只含有一個多候選式的定義式 AABc和 B bB。只需證明：FIRST （A）

25、FOLLOW （A） =a,# ，d=FIRST （B）FOLLOW （B） =b,# ，d=該文法是 LL （1）文法。構(gòu)造相應(yīng)的 LL （ 1）分析表因為 FIRST （A）=a ，所以 MA ，a= AaA ；因為 FIRST （S）=b ， ，所以 MS ，b= SbAS ，又因為FIRST （S ），則對 d ，#FOLLOW （ S），所以 MA ，d= A，MA ，#= A；因為 FIRST （B ）=d ，所以 MB ，d= BdB ；因為 FIRST （ B）=b ，所以 MB ， b= BBb ，又因為FIRST （B ），則對 cFOLLOW （ B），所以 MB ，c=

26、 B。LL(1) 分析表abcd#AAaAAAABcAABBdBBBBbB輸入串 aadc# 的分析過程。步驟符號棧輸入串所用產(chǎn)生式0Aaadc 1Aaaadc AaA2Aadc 匹配3cBAadc AABc4cBAadcAaA5cBAdc匹配6cBdcA7cBddc匹配8cBcB9cc匹配10結(jié)束作業(yè) :根據(jù) P76 表 4.1 寫出表達(dá)式(i+i)*i的預(yù)測分析過程。 P81 1, 2(1)(2)(3)作業(yè)解析一、 P76 的文法寫出表達(dá)式(i+i)*i的預(yù)測分析過程。解答：步驟符號棧輸入串所用的產(chǎn)生式0#E（i+i ）*i#1#ET（i+i）*i#ETE2#ETF（i+i ）*i#TFT

27、3#ET ）E （i+i）*i#F（E）4#ET ）Ei+i ）*i#5#ET ）ETi+i ）*i#ETE6#ET ）ETFi+i ）*i#TFT7#ET ）ETii+i）*i#Fi8#ET ）ET+i）*i#9#ET ）E+i）*i#T10#ET ）ET+i）*i#E+TE11#ET ）ETi）*i#12#ET ）ETFi）*i#TFT13#ET ）ETii） *i#Fi14#ET ）ET）*i#15#ET ）E）*i#T16#ET ）*i#E18#ET*i#19#ETF*i#T*FT20#ETFi#21#ETii#Fi22#ET#23#E#T24#E二、考慮下面文法GS a （T）T T

28、，S S消除文法的左遞歸。經(jīng)改寫后的文法是否是LL（1）的？給出它的預(yù)測分析表。解答：經(jīng)考察該文法Sa（T）的各侯選式的首字符都是終結(jié)符號，所以只有TT，SS 是直接左遞歸。根據(jù)改寫算法，改寫后的文法是：S a （T）T STT， ST證明改寫后的文法是否是LL（1）的 .證明a（ T）各侯選式的是否兩兩相交。FIRST（a）FIRST（）=FIRST（a）FIRST（） =FIRST（）FIRST（） =證明T，ST的FIRST（T）和FOLLOW（T）是否相交。求 FIRST （T ）= ， FOLLOW （T） =FIRST （ T）FOLLOW （T ）= ，=該文法是 LL （1）的。構(gòu)造預(yù)測分析表a，（）#SSaSS（T）TTSTTSTTSTTT，STT二、下面的文法GE TEE +ET FTT TF PF F *FP （E） a b計算這個文法的每個非終結(jié)符的FIRST 和 FOLLOW 。證明這個文法是LL（ 1）的構(gòu)造它的預(yù)測分析表。解答：求非終結(jié)符的FIRST 和 FOLLOW 。求非終結(jié)符的FIRST ：因為因為因為所以因為因為因為因為所以E+E，所以 FIRST （ E） =+ ，。F*F，所以 FIRST （ F ）=* ，。P（ E）ab，F(xiàn)IRST （ P）=（，