編譯原理復(fù)習(xí)題一(含答案)

PAGE6PAGE實(shí)用文檔一、 單選題（每題2分，共20分）1.編譯器的（）階段可將源程序的字符流收集到若干記號(hào)中。A.語(yǔ)法分析 B.語(yǔ)義分析 C.代碼生成 D.詞法分析2.文法AaA|b屬于正則文法，正則文法在喬姆斯基層次中對(duì)應(yīng)于（ ）文法。A.1型 B.2型 C.3型 D.0型3.某C語(yǔ)言源代碼文件包含#include<stdio.h>，（）將對(duì)源代碼進(jìn)行處理，把文件stdio.h包含進(jìn)去。A.編譯器B.解釋器C.匯編器D.預(yù)處理器4.LL(1)文法的充要條件是（ ）。A.對(duì)于文法中的每條產(chǎn)生式Uα1|α2|…|αn，要求FIRST(αi)∩FIRST(αj)＝Φ（i≠j）B.該文法對(duì)應(yīng)的LL(1)分析表中每個(gè)項(xiàng)目最多只有一條產(chǎn)生式。C.A和BD.都不是5.以下說(shuō)法中正確的是（）。A.任何語(yǔ)言都可以描述為一個(gè)正則表達(dá)式。B.對(duì)于任何一個(gè)NFAM，都存在一個(gè)DFAM’，滿足L(M)=L(M’)。C.任何一個(gè)DFA只有一個(gè)終態(tài)。D.NFA的弧上標(biāo)記只含輸入字母表中的元素。6.合成屬性的計(jì)算可以通過(guò)對(duì)語(yǔ)法樹進(jìn)行（ ）遍歷進(jìn)行。A.前序 B.中序 C.后序 D.任意7.喬姆斯基的2型文法是這樣一種語(yǔ)言，其產(chǎn)生式限制為（ ）。A.α->β B.P->β C.P->a或P->aβ D.αPγ->αβγ 8.正則式的“*”讀作（ ）。A.并且 B.連接 C.正則閉包 D.閉包9.編譯程序中的語(yǔ)義分析器接受以（ ）為單位的輸入，并產(chǎn)生信息供以后各階段使用。A.語(yǔ)法樹 B.子程序 C.單詞 D.語(yǔ)句10.文法A->aAb|ab生成的語(yǔ)言是（ ）。A.{ab} B.{aAb} C.{anbn|n≥1} D.{anbn|n≥0}二、 判斷題（每題2分，共10分，對(duì)的打√，錯(cuò)的打×）1.一個(gè)LR(0)文法一定是SLR(1)文法。 （ ）2.在類型聲明文法中，類型屬性type是繼承屬性。 （ ）3.在構(gòu)造遞歸下降偽代碼時(shí)，將非終結(jié)符A翻譯為一個(gè)匹配過(guò)程match（A）。 （ ）4.三元式和四元式都是三地址碼的實(shí)現(xiàn)形式。 （ ）5.存在這樣的語(yǔ)言，它們能被確定的有窮自動(dòng)機(jī)識(shí)別，但不能用正則表達(dá)式表示。 （ ）三、 填空題（每空2分，共10分）1.若文法G的某個(gè)句子存在兩棵以上的語(yǔ)法樹，則稱該文法是文法。2.自上而下語(yǔ)法分析方法的基本思想是：從文法的出發(fā)，不斷進(jìn)行，最終得到輸入串。3.程序設(shè)計(jì)語(yǔ)言中名字的作用域一般遵循的原則，即若有多個(gè)同名定義，該名字的引用應(yīng)對(duì)應(yīng)于與其引用最近的那個(gè)聲明。4.表達(dá)式a－b*(c＋d)對(duì)應(yīng)的逆波蘭式是。四、 簡(jiǎn)答題（每題6分，共30分）1. 簡(jiǎn)述前端和后端，并說(shuō)明為什么要區(qū)分前端和后端。2. 設(shè)標(biāo)識(shí)符為以一個(gè)字母（letter）開頭、后跟任意字母或者數(shù)字（digit）的串，請(qǐng)畫出識(shí)別標(biāo)識(shí)符的DFA。3. 對(duì)下圖NFAM構(gòu)造其DFA。aaaabbbXY4．令文法G為： ND|ND D0|1|…|9(1)該文法的語(yǔ)言是什么？(2)給出句子456的最左推導(dǎo)。5.試將布爾表達(dá)式a<borc<d翻譯成四元式（設(shè)起始四元式標(biāo)號(hào)為100）。屬性文法如下：E?id1relopid2{E.place:=newtemp; emit(‘if’id1.placerelop.opid2.place‘goto’nextstat+3); emit(E.place‘:=’‘0’); emit(‘goto’nextstat+2); emit(E.place‘:=’‘1’)}E→id {E.place:=id.place}E→E1orE2{E.place:=newtemp; emit(E.place‘:=’E1.place‘or’E2.place)}E→E1andE2{E.place:=newtemp;emit(E.place‘:=’E1.place‘a(chǎn)nd’E2.place)}五、 綜合題(30分)1. (10分)計(jì)算文法G(E)的每個(gè)非終結(jié)符的FIRST和FOLLOW集合，并判斷該文法是否是LL(1)的，請(qǐng)說(shuō)明理由。G(E)：E→E+T|TT→T*F|FF→(E)|i2.(10分)考慮下面的屬性文法：文法規(guī)則語(yǔ)義規(guī)則①S－＞ABCB.u=S.uA.u=B.v+C.vS.v=A.v②A－＞aA.v=2*A.u③B－＞bB.v=B.u④C－＞cC.v=1(1) 畫字符串a(chǎn)bc的相關(guān)圖。(2) 假設(shè)在屬性等式開始前S.u賦值為3，等式完成時(shí)S.v的值為多少？3.(10分)已知文法E→(L)|aL→L,E|E1） 構(gòu)造該文法的LR(0)項(xiàng)目DFA;2） 構(gòu)造其SLR(1)分析表，并判斷該文法是否SLR(1)文法。參考答案單選題（每題2分，共20分）12345678910DCDBBCBDAC判斷題（每題2分，共10分，對(duì)的打√，錯(cuò)的打×）12345√√×√×填空題（每空2分，共10分）1.二義性 2.開始符號(hào)，推導(dǎo) 3.最近嵌套 4.abcd+*-。簡(jiǎn)答題（每題6分，共30分）簡(jiǎn)述前端和后端，并說(shuō)明為什么要區(qū)分前端和后端。答：編譯前端：與源語(yǔ)言有關(guān)，如詞法分析，語(yǔ)法分析，語(yǔ)義分析與中間代碼產(chǎn)生，與機(jī)器無(wú)關(guān)的優(yōu)化。編譯后端：與目標(biāo)機(jī)有關(guān)，與目標(biāo)機(jī)有關(guān)的優(yōu)化，目標(biāo)代碼產(chǎn)生。區(qū)分前端和后端的目的是為了減少對(duì)內(nèi)存容量的要求，使程序邏輯結(jié)構(gòu)清晰;優(yōu)化更充分，有利于移植。設(shè)標(biāo)識(shí)符為以一個(gè)字母（letter）開頭、后跟任意字母或者數(shù)字（digit）的串，請(qǐng)畫出識(shí)別標(biāo)識(shí)符的DFA。識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖1識(shí)別標(biāo)識(shí)符的狀態(tài)轉(zhuǎn)換圖123字母其他字母或數(shù)字*aabaabbbXY解：用子集法構(gòu)造轉(zhuǎn)換矩陣ba,bba,bab021DFAM’4．令文法G為： ND|ND D0|1|…|9(1)該文法的語(yǔ)言是什么？(2)給出句子456的最左推導(dǎo)。答：（1）該文法生成的語(yǔ)言是正整數(shù)。（2）N=>ND=>NDD=>DDD=>4DD=>45D=>4565.試將布爾表達(dá)式a<borc<d翻譯成四元式（設(shè)起始四元式標(biāo)號(hào)為100）。100: ifa<bgoto103101: T1:=0 102: goto104103: T1:=1104: ifc<dgoto107105: T2:=0 106: goto108107: T2:=1綜合題(30分)(10分)計(jì)算文法G(E)的每個(gè)非終結(jié)符的FIRST和FOLLOW集合，并判斷該文法是否是LL(1)的，請(qǐng)說(shuō)明理由。G(E)：E→E+T|TT→T*F|FF→(E)|iFIRST(E)=FIRST(T)=FIRST(F)={(,i}FOLLOW(E)={#,+,)}FOLLOW(T)={#,+,),*}FOLLOW(F)={#,+,),*}因?yàn)镕IRST(E+T)∩FIRST(E+T)={(,i}≠Φ，所以該文法不是LL(1)文法。(10分)考慮下面的屬性文法產(chǎn)生式語(yǔ)義規(guī)則S→ABCA→aB→bC→cB.u:=S.uA.u:=B.v+C.vS.v:=A.vA.v:=3*A.uB.v:=B.uC.v:=1畫出字符串a(chǎn)bc的相關(guān)依賴圖;假設(shè)S.u的初始值為5，屬性計(jì)算完成后，S.v的值為多少?答：a.語(yǔ)法樹與相關(guān)圖為：vAuvBuvCuvAuvBuvCuabcvSu屬性等式的序列為：①③④①②①b.等式完成后，S.v的值為183.(10分)已知文法E→(L)|aL→L,E|E構(gòu)造該文法的LR(0)項(xiàng)目DFA;構(gòu)造其SLR(1)分析表，并判斷該文法是否SLR(1)文法。解：（1）為這個(gè)文法構(gòu)造LR(0)項(xiàng)目的DFA.其擴(kuò)充文法為：E’→EE→(L)|aL→L,E|E改文法LR(0)項(xiàng)的DFA是：(2)構(gòu)造SLR(1)分析表First(E’)={(,a);Follow(E’)={$};First(E)={(,a);Foll