編譯原理作業(yè)集-第四章-修訂版

1、第四章 語(yǔ)法分析自上而下分析本章要點(diǎn)1. 語(yǔ)法分析器的功能；2. 自上而下分析方法，LL(1)文法3. 遞歸下降分析程序構(gòu)造；4. 預(yù)測(cè)分析表的構(gòu)造及預(yù)測(cè)分析過(guò)程；5. LL(1)分析中的錯(cuò)誤處理。本章目標(biāo)理解和掌握語(yǔ)法分析器的功能、自上而下分析所面臨的問(wèn)題、LL（1）分析法、遞歸下降分析的構(gòu)造過(guò)程、預(yù)測(cè)分析程序等內(nèi)容。本章重點(diǎn)1語(yǔ)法分析器的功能，自上而下的基本概念2LL（1）文法的條件及其判別，計(jì)算first集和follow集3遞歸下降分析方法、預(yù)測(cè)分析表的構(gòu)造及其預(yù)測(cè)過(guò)程。本章難點(diǎn)1. 非終結(jié)符的First集合，產(chǎn)生式候選的First集合，非終結(jié)符的follow集合的求解；2. 左遞歸消除

2、；3. 遞歸下降分析程序的編寫(xiě)；作業(yè)題一、單項(xiàng)選擇題：1. 高級(jí)語(yǔ)言編譯程序常用的語(yǔ)法分析方法中，遞歸下降分析法屬于 分析法。a. 自左至右 b. 自頂向下 c. 自底向上 d. 自右向左2. 上下文無(wú)關(guān)文法可以用 來(lái)描述。a. 正則表達(dá)式 b. 正規(guī)文法 c. 擴(kuò)展的BNF d. 翻譯模式3. 自上而下分析面臨的四個(gè)問(wèn)題中，不包括 a. 需消除左遞歸；b. 存在回朔；c. 虛假匹配；d. 尋找可歸約串4. 語(yǔ)法分析器接收以_為單位的輸入，并產(chǎn)生有關(guān)信息供以后各階段使用。a. 表達(dá)式；b. 產(chǎn)生式； c. 單詞；d. 語(yǔ)句；5. 自上而下分析的主旨是，對(duì)任何單詞符號(hào)串，試圖用一切可能的辦法，從

3、文法開(kāi)始符號(hào)（根結(jié)點(diǎn)）出發(fā)，_。a. 為輸入串尋找最右推導(dǎo)； b. 為輸入串尋找最左直接子樹(shù)；c. 為輸入串建立最右直接子樹(shù)；d. 為輸入串尋找最左推導(dǎo)；6. 把規(guī)則TF | T*F表示成擴(kuò)展的巴克斯范式以后，畫(huà)出它的語(yǔ)法圖應(yīng)該是 。7. 下列文法中，_是LL(1)文法。a. SaSb|abb. Sab|Sabc. SaS|bd. SaS|a8. 設(shè)有文法G：SAp|BqAa|cABb|dB則，F(xiàn)irst(Ap)=_a. a,c b. b,d c. p, q d. A, p一答案：1. b；2. c；3. d；4. c；5. d；6. 圖a；二、填空題：1. 語(yǔ)法分析器的工作本質(zhì)上就是按_，識(shí)

4、別輸入符號(hào)串是否為一個(gè)句子。這里所說(shuō)的輸入串是指由_組成的有限序列。2. 自頂向下分析會(huì)遇到的主要問(wèn)題是_和_。3. 自上而下地為輸入串建立一棵語(yǔ)法樹(shù)，就是為輸入串尋找一個(gè)_。4. 在擴(kuò)充的巴科斯范式中，用_表示符號(hào)或串的出現(xiàn)可有可無(wú)。5. 對(duì)于一個(gè)文法，當(dāng)給出一串符號(hào)時(shí)，怎么能知道它是不是該文法的一個(gè)句子呢？這就要判斷，看是否能 。6. 文法exp exp addop term | term 消除左遞歸的結(jié)果為 。7. 寫(xiě)出ET | E+T的EBNF范式為 。8. 擴(kuò)展的巴克斯范式描述語(yǔ)法的好處是，直觀易懂，便于表示 。 二答案：1. 文法的產(chǎn)生式，單詞符號(hào)（文法的終結(jié)符）2. 左遞歸，回溯

5、；3.最左推導(dǎo)；4. 方括號(hào)（或a）；5. 從文法的開(kāi)始符號(hào)出發(fā)推導(dǎo)出這個(gè)輸入串。（或：能否建立一棵與輸入串相匹配的語(yǔ)法分析樹(shù)。）6. exp term exp；exp addop term exp| e；7. ET+T；8. 左遞歸消去和左因子提取。三、判斷題：1. LL(k)文法都不是二義性的。（ ）2. 存在一種算法，能判定任何上下文無(wú)關(guān)文法是否是LL(1)的。 ( )3. 一個(gè)文法是含有左遞歸的，如果存在非終結(jié)符P，使得PÞ*aP。（ ）4. 提取公共左因子的副產(chǎn)品是引進(jìn)了大量的非終結(jié)符和產(chǎn)生式。( )5. 把一個(gè)文法改造成任何非終結(jié)符的所有后選終結(jié)首符集兩兩不相交的辦法是消

6、除左遞歸。( )6. 若XVT，則FIRST(X)= X 。 ( )7. 一個(gè)文法的預(yù)測(cè)分析表含有多重定義入口，說(shuō)明該文法是LL(1)的。（ ）8. 自上而下分析及自下而上分析中的“下”是指被分析的源程序串。（ ）三答案：1. Ö；2. Ö；3. ×；4. Ö；5. ×；6. Ö；7. ×；8. Ö；四、名詞解釋：1. 左遞歸；2. 遞歸下降分析器；3. LL(1)文法；4. 預(yù)測(cè)分析表5. 自上而下分析四答案：1.一個(gè)文法如果存在非終結(jié)符P，P=>+Pa，則稱該文法是左遞歸的。2. 當(dāng)一個(gè)文法滿足LL(1)

7、條件時(shí)，可以為它構(gòu)造一個(gè)不帶回溯的的自上而下分析程序，該程序是由一組遞歸過(guò)程組成的，每個(gè)過(guò)程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。這樣的分析程序稱為遞歸下降分析器。3. 一個(gè)文法G，如果滿足以下條件，則稱為L(zhǎng)L(1)文法：（1）文法不含左遞歸；（2）對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交；（3）對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包含e，則A的First集合和Follow集合的交集為空。4. 預(yù)測(cè)分析表是一個(gè)MA, a形式的矩陣。其中A為非終結(jié)符，a是終結(jié)符或“#”。矩陣元素MA, a中存放著一條關(guān)于A的產(chǎn)生式，指出當(dāng)A面臨輸入符號(hào)a時(shí)所應(yīng)采取的候選。MA, a中也可能存放

8、一個(gè)“出錯(cuò)標(biāo)志”，指出A根本不該面臨輸入符號(hào)a。5. 自上而下分析是，對(duì)任何輸入串，試圖用一切可能的辦法，從文法開(kāi)始符號(hào)（根結(jié)點(diǎn)）出發(fā)，自上而下地為輸入串建立一棵語(yǔ)法樹(shù)?；蛘哒f(shuō)，為輸入串尋找一個(gè)最左推導(dǎo)。五、簡(jiǎn)答題：1. 詞法分析和語(yǔ)法分析都是對(duì)字符串進(jìn)行識(shí)別的，二者有何區(qū)別？2. 試說(shuō)明沒(méi)有一個(gè)左遞歸文法是LL(1)的。3. 試說(shuō)明沒(méi)有一個(gè)LL(1)文法是二義性的。4. 為什么要消除回溯？5. 為什么要提取左因子？6. 下面文法是有左遞歸嗎？若有，提取左遞歸。 DeclistDeclist; Decl | Decl DeclidList:Type IdListIdlist, id | id

9、TypeScalarType | array (ScalarTypeList) of Type ScalarTypeid | Bound.Bound BoundSign IntLiteral | id Sign+ | - | e ScalarTypeListScalarTypeList, ScalarType | ScalarType五答案：1. 答：詞法分析的輸入符號(hào)串是一個(gè)單詞，而語(yǔ)法分析的輸入符號(hào)串是一個(gè)句子。詞法分析的一個(gè)輸入符號(hào)串是由單個(gè)符號(hào)組成的單詞；語(yǔ)法分析的輸入符號(hào)串是由詞法分析得來(lái)的單詞組成的句子。2. 對(duì)于任一個(gè)左遞歸文法來(lái)說(shuō)，存在一個(gè)AÎVN，有AA.，因此，在

10、文法中必有如下的規(guī)則序列：A A1.A1 A2. . An A|A。顯然，F(xiàn)IRST(A)FIRST()。因此，沒(méi)有一個(gè)左遞歸文法是LL(1)的。3. 解：設(shè)有一個(gè)LL(1)文法G是二義性的，那么，一定存在一個(gè)WL(G)，W=a1, a2., an，有兩棵不同的分析樹(shù)。如果按最左推導(dǎo)構(gòu)造這兩棵分析樹(shù)，按么，一定有兩個(gè)最左推導(dǎo)序列，這來(lái)年改革最左推導(dǎo)序列的不同在于，于對(duì)某一個(gè)AVN和當(dāng)前要匹配的ai(1in)，分別使用A的兩個(gè)不同的候選式A和A進(jìn)行推導(dǎo)以匹配ai(i) 若且，則必有aiFIRST()且aiFIRST()，F(xiàn)IRST()FIRST()(ii) 若和有一個(gè)能推導(dǎo)出，比如，則 

11、;   aiFIRST()且aiFOLLOW(A)顯然，F(xiàn)IRST()FOLLOW(A)無(wú)論(i)還是(ii)，都和G是LL(1)文法矛盾。4. 假定當(dāng)前輪到非終結(jié)符A去執(zhí)行匹配任務(wù)，A共有n個(gè)候選a1、a2、an，這時(shí)候該用哪一個(gè)候選去替換A，原始的辦法是采用對(duì)所有候選采取“試探”的方法。如果某個(gè)候選不成功就需要“回退”。這個(gè)回退的過(guò)程會(huì)導(dǎo)致前次匹配的許多工作推到重來(lái)，效率低。而且，最終匹配不成功的時(shí)候，難以直到輸入串中出錯(cuò)的確切位置。5. 假定當(dāng)前輪到非終結(jié)符A去執(zhí)行匹配任務(wù)，A共有n個(gè)候選a1、a2、an，即Aa1|a2|an。A面臨的第一個(gè)輸入符號(hào)為a，如

12、果a屬于某個(gè)First(ai)，則用該ai來(lái)匹配A。但是，若a既屬于某個(gè)First(ai)，又屬于某個(gè)First(aj)，則說(shuō)明ai和ai存在共同的左部，也就是說(shuō)，有共同的左因子。此時(shí)無(wú)法確定到底是用ai還是用aj來(lái)匹配A。所以要消除左因子。六、應(yīng)用題1. 已知文法GS：S (L) | aL L,S | S.消除左遞歸，若有左因子則提取之；.對(duì)（1）中得到的文法求First集合和Follow集合.對(duì)（1）中得到的文法構(gòu)造一個(gè)預(yù)測(cè)分析表；.給出對(duì)句子(a,(a,a)上的分析動(dòng)作1.答案：將所給文法消除左遞歸得G： S (L) | a L SL L ,SL |e實(shí)現(xiàn)預(yù)測(cè)分析器的不含遞歸調(diào)用的一種有

13、效方法是使用一張分析表和一個(gè)棧進(jìn)行聯(lián)合控制，下面構(gòu)造預(yù)測(cè)分析表：根據(jù)文法G有 FIRST(S) = ( , a FOLLOW(S) = #, ) , , FIRST(L) = ( , a FOLLOW(S) = ) FIRST(L) = , , eFOLLOW(L) = ) 按以上結(jié)果，構(gòu)造預(yù)測(cè)分析表M如下：非終結(jié)符號(hào)輸入符號(hào)(),a#SS ( L )S aLL SLL SLLL eL ,SL文法G是LL(1)的，因?yàn)樗姆治霰聿缓嘀囟x入口。預(yù)測(cè)分析器對(duì)輸入符號(hào)串(a, (a, a)做出的分析動(dòng)作如下：棧輸入輸出$S(a, (a, a)$)L(a, (a, a)$S (L)$)La, (a

14、, a)$)LSa, (a, a)$L SL$)Laa, (a, a)$S a$)L, (a, a)$)LS, (a, a)$L , SL$)LS(a, a)$)L)L(a, a)$S (L)$)L)La, a)$)L)LSa, a)$L SL$)L)Laa, a)$S a$)L)L, a)$)L)LS, a)$L ,SL$)L)LSa)$)L)Laa)$S a$)L)L)$)L)$L e$)L)$)$L e$2. 考查文法G(s): S( T ) | a + S | aTT, S | S. 消除文法的左遞歸，提取公共左因子. 改造后的文法是LL(1)的嗎？為什么？. 如果是LL(1)文法，對(duì)

15、每個(gè)非終結(jié)符，寫(xiě)出不帶回朔的遞歸子程序。2.答案：.消除文法的左遞歸G ( s )：S ( T ) | a + S | aT S T T , S T| e再提取公共左因子，最后得到改造后的文法GS:S( T ) | a SS + S | eT S TT, S T | e.First(S)=(，a ； Follow(S)=#，,；First(S)=，； Follow(S)= #，,；First(T)=(，a ； Follow(T)= ) ；First(T)=, ，; Follow(T) = ) ；產(chǎn)生式的兩個(gè)候選的First集合：Fist(（T）)=（，F(xiàn)irst(aS)=a不相交，滿足條件。產(chǎn)

16、生式，F(xiàn)irst(S) Follow(S)=F；產(chǎn)生式，F(xiàn)irst(T) Follow(T)=F；所以，改造后的文法是LL(1)的，.我們構(gòu)造不帶回溯的遞歸子程序如下：S( T ) | a SPROCEDURE S;DEGIN IF SYM=( THEN BEGIN ADVANCE T; IF SYM= ) THEN ADVANCE ELSE ERROR END ELSE IF SYM=a THEN BEGIN ADVANCE; END ELSE ERROREND;S + S | ePROCEDURE S;BEGIN IF SYM= + THEN BEGIN ADVANCE;S ENDEND;

17、T S TPROCEDURE T;BEGIIN S; T END;T, S T | ePROCEDURE T;BEGIN IF SYM= , THEN BEGIN ADVANCE; S; T ENDEND;3. 已知文法GS：S uBDzB Br | wD EFE y | eF x | e(a) 求每個(gè)非終結(jié)符的FIRST和Follow集。(b) 構(gòu)造這個(gè)文法的LL(1)分析表(c) 說(shuō)明這個(gè)文法不是LL(1)的;(d) 盡可能少地修改此文法,使其成為能產(chǎn)生相同語(yǔ)言的LL(1)文法.3. 答案： (a) FIRST(S) = u FOLLOW(S) = # FIRST(B) = w FOLLO

18、W(B) = r, z FIRST(D) = x, y, e FOLLOW(D) = z FIRST(E) = y, eFOLLOW(E) = x, z FIRST(F) = x, e FOLLOW(F) = z (b) 該文法的LL(1)分析表為：非終結(jié)符uzrwxy#SSuBDzBBBrBwDDEFDEFDEFDEFEEeEyEeFFeFx(c) 因?yàn)镸B, w有兩個(gè)產(chǎn)生式 BBv, Bw 且FIRST(Bv)=FIRST(w) = w 所以不是LL(1)的。(d) 消除左遞歸即可。 SuBDz BwB BrB | e D EF E = y | e F = x | e4. 已知文法如下：E

19、T | E+TTF | T*FFi | (E) 構(gòu)造預(yù)測(cè)分析表，并給出對(duì)輸入串i*i+i的分析過(guò)程。4.答案：首先消除左遞歸，得到新文法如下：ETEE+TE|TFTT*FT|F(E)|i對(duì)每個(gè)非終結(jié)符構(gòu)造First和Follow集合：FIRST(E) = FIRST(T) = FIRST(F) = ( , i ；FIRST(E) = + , ；FIRST(T) = * , FOLLOW(E) = FOLLOW(E) = ) , # ；FOLLOW(T) = FOLLOW(T) = + ，) ，# FOLLOW(F) = * , + , ) , # 再通過(guò)對(duì)文法的每個(gè)非終結(jié)符的任意候選都構(gòu)造出F

20、irst集合：FIRST(TE)= (,i； FIRST(+TE)=+ ；FIRST(FT)=(,i；FIRST(*FT)=*； FIRST(（E）)=(得到預(yù)測(cè)分析表如下： i + * ( ) #EETEETEEE+TEE eE eTTFTTFTTT eT*FTT eT eFFiF(E)對(duì)輸入串的分析過(guò)程如下：5. 文法G1：Sa|(T)TT,S|S(1) 證明文法G是LL(1)文法。(2) 構(gòu)造LL(1)分析表。(3) 寫(xiě)出句子（a,a）#的分析過(guò)程。5. 答案：（1）先消除左遞歸，得到文法G2： 0) Sa 1) S 2) S( T ) 3) TS N2 4) N2, S N2 5) N

21、2求非終結(jié)符的First和Follow集合：FIRSTFOLLOWS a，( #，,，) T a，( ) N2 ,， ) 對(duì)左部為N2的產(chǎn)生式可知：FIRST （, S N2）=，F(xiàn)IRST （）=FIRST(, S N2) FIRST()=Æ且：FIRST(N2) FOLLOW(N2)= Æ所以文法是LL(1)的。得到預(yù)測(cè)分析表 ：a(),#SSaSS( T )TTSN2TSN2TSN2N2N2N2,SN2也可由預(yù)測(cè)分析表中無(wú)多重入口判定文法是LL(1)的。對(duì)輸入串（a,a）#的分析過(guò)程為：分析棧輸入串所用產(chǎn)生式#Sa,a)#)T(a,a)#S(T)#)T,a)#)N2S

22、,a)#TSN2#)N2a,a)#Sa#)N2a)#)N2S,a)#N2,SN2#)N2S)#)N2a)#Sa#)N2#)#N2#可見(jiàn)輸入串（a,a）#是文法的句子。6. 設(shè)文法G(S)： S(L)|aS|a LL,S|S(1)消除左遞歸和提取左因子；(2)計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW；(3)構(gòu)造預(yù)測(cè)分析表。(4)已知輸入串(aa,a)a，該輸入串是否文法的句子？給出分析過(guò)程。7. 對(duì)于文法 bexpr bexpr or bterm | bterm bterm bterm and bfactor | bfactor bfactor not bfactor | (bexpr) |

23、true | false構(gòu)造一個(gè)預(yù)測(cè)分析器(表)。答案：消除左遞歸和提取左因子bexpr bterm bexpr bexpr or bterm bexpr | ebterm bfactor bterm bterm and bfactor bterm | ebfactor not bfactor | (bexpr) | true | falseFirst(bexpr)=First(bterm)=First(bfactor)= not, (, true,false First(bexpr)= or , e First(bterm)= and, e Follow(bexpr)=Follow(bexp

24、r)= ) , $ Follow(bterm)=Follow(bterm)=or , ) , $Follow(bfactor)=and , or, ) , $8. 已知GR的產(chǎn)生式如下:   R R | T | T    T TF | F    F F* | C   C (R) | a | b構(gòu)造它的LL(1)分析表，并寫(xiě)出對(duì)輸入串a(chǎn)|ba*的分析過(guò)程。答案：消除上面文法中的左遞歸R TRR | TR | T FTT FT | F CFF *F | C (R) | a | b

25、計(jì)算FIRST()和FOLLOW(A)構(gòu)造LL(1)分析表。9. 已知文法如下：SS*T | S/T | TTT+F | T-F | FF (S) | i | i e i 構(gòu)造預(yù)測(cè)分析表，并給出對(duì)輸入串i/i*i+i的分析過(guò)程。10. 已知文法：SAc|c ABb|b BSa|a構(gòu)造預(yù)測(cè)分析表，給出對(duì)輸入串cabc的分析過(guò)程。11. 已知文法G： S ( L | a L S , L | )（1）構(gòu)造文法 G 的預(yù)測(cè)分析表。（2）若輸入串為“（，）”，請(qǐng)給出語(yǔ)法分析過(guò)程。解（） 1）求各非終結(jié)符的 FISRT 集和 FOLLOW 集：FIRST(S) = (, a )FIRST(L) = a &

26、#200; FIRST(S) = (, ), a FOLLOW(S) = , # FOLLOW(L) = FOLLOW(S) = , # 2）預(yù)測(cè)分析表：(a,#SS ( LS aLL S , LL S , LL )（）對(duì)輸入串 “（，）”的分析處理過(guò)程如表1所示。表1 對(duì)輸入串 “（，）”的分析過(guò)程步驟分析棧輸入串所用產(chǎn)生式（，）L(（，）S ( LL，）L, S ，）L S , LL, a，）SaL, ，）L ） ）L )12. 給定文法 ( i，d，(，) ，)其中 ：E iAE EAA i A d A (E)(1)消除左遞歸；(2)計(jì)算改寫(xiě)后文法中各非終結(jié)符的 FIRST 集和 FOL

27、LOW 集；(3)構(gòu)造改寫(xiě)后文法的預(yù)測(cè)分析表；該文法是 LL(1) 文法嗎?。解(1)消除左遞歸后的文法為:E iAE e | AEA iA dA ( E )(2)各非終結(jié)符的 FISRT集和FOLLOW集FIRST( E ) =iFIRST(E) = i, d, (, e)FIRST( A ) =i, d, ()FOLLOW( E ) =), # FOLLOW(E) = , # FOLLOW( A ) =i, d, (, ), # (3)改寫(xiě)后文法的預(yù)測(cè)分析表：id()#EEiAEEEAEEAEEAEE eE eAAiAdA (E)預(yù)測(cè)分析表中無(wú)多重入口,因此該文法是 LL(1) 文法.13

28、. 已知文法： AaABe|a BBb|d.消除左遞歸，若有左因子則提取之；.對(duì)（1）中得到的文法求First集合和Follow集合.對(duì)（1）中得到的文法構(gòu)造一個(gè)預(yù)測(cè)分析表；.給出對(duì)句子aadb上的分析動(dòng)作答案： 改寫(xiě)文法為：0) Aa N3 1) N3A B e 2) N33) Bd N2 4) N2b N2 5) N2 FIRSTFOLLOWAa#,dBdeN2b,eN3,a#,dPredicting Analysis Tableaebd#AAa N3BBd N2N2N2N2b N2N3N3A B eN3N3由預(yù)測(cè)分析表中無(wú)多重入口判定文法是LL(1)的。14. 已知文法： SAa|b ASB Bab(1) 改寫(xiě)文法以消除左遞歸，若有左因子則提取之；(2)計(jì)算改寫(xiě)后文法中各非終結(jié)符的 FIRST 集和 FOLLOW 集；(3)構(gòu)造改寫(xiě)后文法的預(yù)測(cè)