...wd......wd......wd...一、單項(xiàng)選擇題概述局部1．構(gòu)造編譯程序應(yīng)掌握。DA.源程序B.目標(biāo)語言C.編譯方法D.以上三項(xiàng)都是2．編譯程序絕大多數(shù)時(shí)間花在上。DA.出錯(cuò)處理B.詞法分析C.目標(biāo)代碼生成D.表格管理3．編譯程序是對(duì)。DA.匯編程序的翻譯B.高級(jí)語言程序的解釋執(zhí)行C.機(jī)器語言的執(zhí)行D.高級(jí)語言的翻譯4.將編譯程序分成假設(shè)干“遍〞，是為了。BA.提高程序的執(zhí)行效率B.使程序的構(gòu)造更為清晰C利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率D.利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率詞法分析局部1．DFAM(見圖1-1)承受的字集為。D圖1-1圖1-1XY0011B.以0結(jié)尾的二進(jìn)制數(shù)組成的集合C.含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合D.含偶數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合2．詞法分析器的輸出結(jié)果是。CA.單詞的種別編碼B.單詞在符號(hào)表中的位置C.單詞的種別編碼和自身值D.單詞自身值3．正規(guī)式M1和M2等價(jià)是指。CA.M1和M2的狀態(tài)數(shù)相等B.M1和M2的有向邊條數(shù)相等C.M1和M2所識(shí)別的語言集相等D.M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等4．詞法分析器的加工對(duì)象是。CA．中間代碼 B．單詞 C．源程序 D．元程序5．同正規(guī)式〔a|b〕*等價(jià)的正規(guī)式為。DA．(a|b)+ B．a(chǎn)*|b* C．(ab)* D．(a*|b*)+6.兩個(gè)DFA等價(jià)是指：。DA.這兩個(gè)DFA的狀態(tài)數(shù)一樣B.這兩個(gè)DFA的狀態(tài)數(shù)和有向弧條數(shù)都相等C.這兩個(gè)DFA的有向弧條數(shù)相等D.這兩個(gè)DFA承受的語言一樣7.以下符號(hào)串不可以由符號(hào)集S＝{a,b}上的正閉包運(yùn)算產(chǎn)生的是：〔A〕A.εB.aC.aaD.ab8．稱有限自動(dòng)機(jī)A1和A2等價(jià)是指________。DA．A1和A2都是定義在一個(gè)字母表上的有限自動(dòng)機(jī)B．A1和A2狀態(tài)數(shù)和有向邊數(shù)相等C．A1和A2狀態(tài)數(shù)或有向邊數(shù)相等D．A1和A2所能識(shí)別的字符串集合相等9．同正規(guī)式〔a|b〕+等價(jià)的正規(guī)式是_______。BA．〔a|b〕*B．〔a|b〕〔a|b〕*C．〔ab〕*〔ab〕D．〔a|b〕|〔a|b〕*語法分析1．在標(biāo)準(zhǔn)歸約中，用來刻畫可歸約串。BA.直接短語B.句柄C.最左素短語D.素短語2．假設(shè)B為非終結(jié)符，則A→α·Bβ為工程。DA.歸約 B.移進(jìn)C.承受 D.待約3．如果文法G是無二義的，則它的任何句子α。AA.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定一樣B.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同C.最左推導(dǎo)和最右推導(dǎo)必定一樣D.可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹一樣4．以下動(dòng)作中，不是自下而上分析動(dòng)作的是：。BA.移進(jìn) B.展開C.承受D.報(bào)錯(cuò)6．假設(shè)a為終結(jié)符，則A→α·aβ為工程。BA.歸約B.移進(jìn)C.承受 D.待約7．語法分析時(shí)所依據(jù)的是。AA.語法規(guī)則B.詞法規(guī)則C.語義規(guī)則D.等價(jià)變換規(guī)則8．文法G：S→xSx|y所識(shí)別的語言是。CA.xyxB.(xyx)* C.xnyxn(n≥0)D.x*yx*9．以下動(dòng)作中，不是自上而下分析動(dòng)作的是：。CA.匹配 B.展開C.移進(jìn)D.報(bào)錯(cuò)10．假設(shè)A為非終結(jié)符，則A→α·為工程。AA.歸約 B.移進(jìn)C.承受 D.待約11．文法G：S→xSx|xS|y所識(shí)別的語言是。AA.xmyxn(m≥n≥0)B.(xyx)* C.xnyxn(n≥0)D.x*yx*13．由文法的開場(chǎng)符號(hào)出發(fā)經(jīng)過假設(shè)干步〔包括0步〕推導(dǎo)產(chǎn)生的文法符號(hào)序列稱為______。BA．語言B．句型C．句子D．句柄14．在自上而下的語法分析中，應(yīng)從開場(chǎng)分析。CA．句型 B．句子 C．文法開場(chǎng)符號(hào) D．句柄15．一個(gè)文法G，假設(shè)________，則稱它是LL〔1〕文法。CA．G中不含左遞歸B．G無二義性C．G的LL〔1〕分析表中不含多重定義的條目D．G中產(chǎn)生式不含左公因子16．工程S’→S.為。DA.歸約工程B.移進(jìn)工程C.待約工程D.承受工程17.語法分析器的輸入是：。AA.Token序列B.源程序C.目標(biāo)程序D.符號(hào)表18.在LR〔0〕的Action表中，如果某行中存在標(biāo)記為“rj〞的欄，則：。AA.該行必定填滿“rj〞B.該行未必填滿“rj〞C.其他行可能也有“rj〞D.goto表中也可能有“rj〞19.LR分析過程中棧內(nèi)存儲(chǔ)的是。AA.活前綴B.前綴C.歸約活前綴D.工程20.文法G：S→xxS|y所識(shí)別的語言是。DA．xxynB．(xxy)nC．xxnyxD．(xx)ny21.假設(shè)狀態(tài)k含有工程“A→α.〞，對(duì)任意非終結(jié)符a，都用規(guī)則“A→α〞歸約的語法分析方法是。BA．LALR分析法 B．LR(0)分析法C．LR(1)分析法 D．SLR(1)分析法22.在SLR〔1〕的Action表中，如果某行中存在標(biāo)記為“rj〞的欄，則：。BA.該行必定填滿“rj〞B.該行未必填滿“rj〞C.其他行可能也有“rj〞D.goto表中也可能有“rj〞23.一個(gè)指明了在LR分析過程中的某個(gè)時(shí)刻所能看到產(chǎn)生式多大一局部。DA.活前綴B.前綴C.歸約活前綴D.工程24.假設(shè)狀態(tài)k含有工程“A→α.〞，且僅當(dāng)輸入符號(hào)a∈FOLLOW(A)時(shí)，才用規(guī)則“A→α〞歸約的語法分析方法是。DA．LALR分析法 B．LR(0)分析法C．LR(1)分析法 D．SLR(1)分析法25．設(shè)有文法G[T]:T→T*F|FF→F↑P|PP→(T)|a該文法句型T*P↑(T*F)的句柄是以下符號(hào)串。CA.〔T*F〕B.T*FC.PD.P↑(T*F)26．LR分析表中的轉(zhuǎn)移表〔goto〕是以作為列標(biāo)題的。BA．終結(jié)符B．非終結(jié)符C．終結(jié)符或非終結(jié)符D．表示狀態(tài)的整形數(shù)27．編譯程序的語法分析器必須輸出的信息是。AA．語法錯(cuò)誤信息 B．語法規(guī)則信息C．語法分析過程 D．語句序列28．以下工程中為可移進(jìn)工程的是。CA．E′→E.B．L→.C．L→.-LD．F→L*F.29．LR分析表中的動(dòng)作表〔action〕是以作為列標(biāo)題的。DA．終結(jié)符B．非終結(jié)符C．終結(jié)符或非終結(jié)符D．終結(jié)符和完畢符#30．以下工程中為可歸約工程的是。BA．E′→.EB．L→.C．L→-.LD．F→L*.F33．LR分析器的核心局部是一張分析表，該表由_________組成。DA．ACTION表B．GOTO表C．預(yù)測(cè)分析表D．ACTION表和GOTO表34．在遞歸下降子程序方法中，假設(shè)文法存在左遞歸，則會(huì)使分析過程產(chǎn)生_______。DA．回溯B．非法調(diào)用C．有限次調(diào)用D．無限循環(huán)35．最左簡單子樹的葉結(jié)點(diǎn)，自左至右排列組成句型的________。CA．短語B．句型C．句柄D．間接短語36．由文法的開場(chǎng)符號(hào)出發(fā)經(jīng)過假設(shè)干步〔包括0步〕推導(dǎo)產(chǎn)生的文法符號(hào)序列中，如果只含有終結(jié)符，則文法符號(hào)序列稱為________。CA．語言B．句型C．句子D．句柄37．LL〔1〕分析法中“1〞的含義是在輸入串中查看一個(gè)輸入符號(hào)，其目的是________。CA．確定最左推導(dǎo)B．確定句柄C．確定使用哪一個(gè)產(chǎn)生式進(jìn)展展開D．確定是否推導(dǎo)語義分析1.表達(dá)式〔┐a∨b〕∧〔e∨f〕的逆波蘭表示為。BA．┐ab∨∧ef∨ B．a(chǎn)┐b∨ef∨∧C．a(chǎn)b∨┐ef∨∧D．a(chǎn)┐b∨∧ef∨2．中間代碼生成時(shí)所依據(jù)的是。CA．詞法規(guī)則B．語法規(guī)則C．語義規(guī)則D．等價(jià)變換規(guī)則3．-a-(b*c/(c-d)+(-b)*a)的逆波蘭表示是。(@代表后綴式中的求負(fù)運(yùn)算符)CA.abc*cd-b@a*+/-@B.a@bc*cd-b@a*+/-C.a@bc*cd-/b@a*+-D.a@bc*/cd-b@a*+-4．有文法G及其語法制導(dǎo)翻譯如下所示〔語義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運(yùn)算符〕：E→E(1)∧T{E.val=E(1).val*T.val}E→T{E.val=T.val}T→T(1)#n{T.val=T(1).val+n.val}T→n{T.val=n.val}則分析句子1∧2∧3#4其值為。CA.10B.34C.14D.545．有文法G及其語法制導(dǎo)翻譯如下所示〔語義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運(yùn)算符〕：E→E(1)∧T{E.val=E(1).val*T.val}E→T{E.val=T.val}T→T(1)#n{T.val=T(1).val+n.val}T→n{T.val=n.val}則分析句子2∧3#4其值為。CA.10B.21C.14D.246．間接三元式表示法的優(yōu)點(diǎn)為。AA.采用間接碼表，便于優(yōu)化處理 B.節(jié)省存儲(chǔ)空間，不便于表的修改C.便于優(yōu)化處理，節(jié)省存儲(chǔ)空間D.節(jié)省存儲(chǔ)空間，不便于優(yōu)化處理7．文法G[S]及其語法制導(dǎo)翻譯定義如下：產(chǎn)生式 語義動(dòng)作S’→S print(S.num)S→(L) S.num=L.num+1S→a S.num=0L→L(1),S L.num=L(1).num+S.numL→S L.num=S.num假設(shè)輸入為(a,(a))，且采用自底向上的分析方法，則輸出為。CA．0 B．1 C．2 D．48．四元式之間的聯(lián)系是通過____________實(shí)現(xiàn)的。BA．指示器B．臨時(shí)變量C．符號(hào)表D．程序變量9．表達(dá)式〔┐a∨b〕∧〔c∨d〕的逆波蘭表示為。BA．┐ab∨∧cd∨ B．a(chǎn)┐b∨cd∨∧C．a(chǎn)b∨┐cd∨∧ D．a(chǎn)┐b∨∧cd∨10．表達(dá)式a+b+c+d的逆波蘭表示為。BA．a(chǎn)+bc+d+ B．a(chǎn)b+c+d+C．a(chǎn)b+cd++ D．a(chǎn)bc+d++11.有文法G及其語法制導(dǎo)翻譯如下所示〔語義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運(yùn)算符〕：E→E(1)∧T{E.val=E(1).val*T.val}E→T{E.val=T.val}T→T(1)#n{T.val=T(1).val+n.val}T→n{T.val=n.val}則分析句子3∧3#4其值為。BA.10B.21C.14D.2412．表達(dá)式a+b+c的逆波蘭表示為。BA．a(chǎn)+bc+ B．a(chǎn)b+c+C．+abc+ D．a(chǎn)bc++13.文法G[S]及其語法制導(dǎo)翻譯定義如下：產(chǎn)生式 語義動(dòng)作S’→S print(S.num)S→(L) S.num=L.num+1S→a S.num=0L→L(1),S L.num=L(1).num+S.numL→S L.num=S.num假設(shè)輸入為(a,a)，且采用自底向上的分析方法，則輸出為。BA．0 B．1 C．2 D．414．有一語法制導(dǎo)翻譯定義如下：S→bAbprint“1〞A→〔Bprint“2〞A→aprint“3〞B→aA)print“4〞假設(shè)輸入序列為b〔a〔a〔aa〕〕〕b，且采用自底向上的分析方法，則輸出序列為。BA．32224441 B．34242421C．12424243 D．3444221215．賦值語句X:=-(a+b)/(c-d)-(a+b*c)的逆波蘭表示是。CXab+cd-/-bc*a+-:=Xab+/cd-bc*a+--:=Xab+-cd-/abc*+-:=Xab+cd-/abc*+--:=16．有一語法制導(dǎo)翻譯定義如下，其中+表示符號(hào)連接運(yùn)算：S→B printB.versB→a B.vers=aB→b B.vers=bB→Ba B.vers=a+B.versB→Bb B.vers=b+B.vers假設(shè)輸入序列為abab，且采用自底向上的分析方法，則輸出序列為。DA．a(chǎn)abb B．a(chǎn)bab C．bbaa D．baba17．編譯程序不能檢查、處理的錯(cuò)誤是程序中的________。BA．靜態(tài)語義檢查B．動(dòng)態(tài)語義檢查C．語法錯(cuò)誤D．詞法錯(cuò)誤〔優(yōu)化、存儲(chǔ)、錯(cuò)誤管理〕1.在編譯過程中，如果遇到錯(cuò)誤應(yīng)該。CA.把錯(cuò)誤理解成局部的錯(cuò)誤B.對(duì)錯(cuò)誤在局部范圍內(nèi)進(jìn)展糾正，繼續(xù)向下分析C.當(dāng)發(fā)現(xiàn)錯(cuò)誤時(shí)，跳過錯(cuò)誤所在的語法單位繼續(xù)分析下去D.當(dāng)發(fā)現(xiàn)錯(cuò)誤時(shí)立即停頓編譯，待用戶改正錯(cuò)誤后再繼續(xù)編譯二、填空題概述局部：1．編譯程序的開發(fā)常常采用自編譯、穿插編譯、自展和移植等技術(shù)實(shí)現(xiàn)。2．解釋程序和編譯程序的區(qū)別在于是否生成目標(biāo)程序。3．如果編譯程序生成的目標(biāo)程序是匯編語言程序，則源程序的執(zhí)行分為3個(gè)階段：編譯階段、匯編階段和運(yùn)行階段。4．編譯程序工作過程中，第一階段輸入是源程序，最后階段的輸出為目標(biāo)程序。5．編譯過程通常可分為5個(gè)階段詞法分析階段、語法分析階段、語義分析和中間代碼生成階段、優(yōu)化階段和目標(biāo)代碼生成階段。6．如果編譯階段生成的目標(biāo)程序是某特定計(jì)算機(jī)系統(tǒng)的機(jī)器代碼程序，則源程序的執(zhí)行分為兩大階段：編譯階段和運(yùn)行階段。7．對(duì)編譯程序而言，輸入數(shù)據(jù)是源程序，輸出結(jié)果是目標(biāo)程序。8．貫穿于編譯程始終的工作有符號(hào)表處理和出錯(cuò)處理。詞法分析局部：1．詞法分析的工作是將源程序中的字符串變換成單詞符號(hào)流的過程，所遵循的是語言的構(gòu)詞規(guī)則。2．假設(shè)兩個(gè)正規(guī)式所表示的正規(guī)集一樣，則認(rèn)為二者是等價(jià)的。3．假設(shè)兩個(gè)正規(guī)式所表示的正規(guī)集一樣，則認(rèn)為二者是等價(jià)的。4．正規(guī)式R1和R2等價(jià)是指_______表示一樣的正規(guī)集。5．詞法分析器的輸入是源程序字符串，輸出構(gòu)造是二元式〔單詞種別，單詞自身的值〕。詞法分析所遵循的是語言的構(gòu)詞規(guī)則。6．確定的有限自動(dòng)機(jī)是一個(gè)五元組，包含的五個(gè)元分別是：狀態(tài)集合、字母表、初態(tài)、終態(tài)集、狀態(tài)轉(zhuǎn)換函數(shù)集合。7．有限自動(dòng)機(jī)是更一般化的狀態(tài)轉(zhuǎn)換圖，它分為確定的有限自動(dòng)機(jī)DFA和非確定的有限自動(dòng)機(jī)NFA兩種。8．NFA和DFA的區(qū)別主要有兩點(diǎn)：其一是NFA可以有假設(shè)干個(gè)初始狀態(tài)，而DFA僅有一個(gè)初始狀態(tài)；其二是NFA的狀態(tài)轉(zhuǎn)換函數(shù)f不是單值函數(shù)，而是一個(gè)多值函數(shù)。語法分析局部：〔基本概念、LL〔1〕、LR〔0〕、SLR〔1〕、遞歸下降子程序〕語法分析的方法通常分為兩類：自上而下分析方法和自下而上分析方法。2．文法中的終結(jié)符集和非終結(jié)符集的交集是空集。3．一個(gè)句型的最左直接短語稱為該句型的___句柄________________。4．標(biāo)準(zhǔn)歸約是最右推導(dǎo)的逆過程。5．自下而上語法分析中分析器的動(dòng)作有_移進(jìn)、____歸約、__承受_、__報(bào)錯(cuò)__。6．自上而下語法分析中分析器的動(dòng)作有___匹配終結(jié)符____、__展開非終結(jié)符_、__分析成功、報(bào)錯(cuò)__。7．常用的自上而下語法分析方法有遞歸下降子程序方法和預(yù)測(cè)分析表方法〔LL〔1〕方法〕。8．常用的自下而上語法分析方法有算符優(yōu)先分析法和LR分析法。9．一個(gè)LL(1)分析器由一張LL(1)分析表〔預(yù)測(cè)分析表〕、一個(gè)先進(jìn)后出分析棧和一個(gè)控制程序〔表驅(qū)動(dòng)程序〕組成。10．一個(gè)LR分析器由分析棧、分析表和總控程序三個(gè)局部組成。11．LR(0)分析法的名字中，“L〞表示自左至右分析輸入串，“R〞表示采用最右推導(dǎo)的逆過程即最左歸約。“0〞表示向右查看0個(gè)字符。12．LL(1)分析法中，第一個(gè)L的含義是從左到右掃描輸入串；第二個(gè)L的含義是分析過程中采用最左推導(dǎo)；“1〞的含義是只需向右查看一個(gè)符號(hào)就可以決定若何推導(dǎo)。13．LR(1)文法的含義是：L說明_____自左至右掃描輸入串__，R說明___采用最右推導(dǎo)的逆過程〔最左歸約〕方法進(jìn)展分析__。14．一個(gè)上下文無關(guān)文法是LL(1)文法的充分必要條件是：對(duì)每一個(gè)非終結(jié)符A的任何兩個(gè)不同產(chǎn)生式A→α|β，有下面的條件成立：〔1〕FIRST(α)∩FIRST(β)=?；〔2〕假假設(shè)，則有FIRST(α)∩FOLLOW(A)=?。15．對(duì)于LL〔1〕文法中的任何產(chǎn)生式A→α|β，則需要滿足__First(_α)∩First(β)=Φ、_假設(shè)_β=>*ε,則_First(_α)∩__Follow(A)=_Φ_。16．LR分析器的核心局部是一張分析表，該表包括動(dòng)作〔ACTION〕表和狀態(tài)轉(zhuǎn)換〔GOTO〕表等兩個(gè)子表。17．關(guān)于非終結(jié)符A的直接左遞歸產(chǎn)生式：A→Aα|β，其中α、β是任意的符號(hào)串且β不以A開頭，則可以將A的產(chǎn)生式改寫為右遞歸的形式為：A→βA’,A’→αA’|ε。18．在消除回溯，提取公共左因子時(shí)，關(guān)于A的產(chǎn)生式A→δβ1|δβ2|…|δβi|βi+1|…|βj，可以改寫為：A→δA’|βi+1|…|βj，A’→β1|…|βi。19．設(shè)G[S]是一文法，如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來的，即有x，則稱x是文法G[S]的____句型__，假設(shè)x僅由終結(jié)符號(hào)組成，即，則稱x為文法G[S]的__句子。20．文法G[S]:S→eT|RTT→DR|εR→dR|εD→a|bd求FIRST(S)={e，d，a，b，ε}______；FOLLOW(D)=_{d，#}。語義處理局部：1．文法符號(hào)的屬性有兩種，一種稱為繼承屬性，另一種稱為綜合屬性。2．編譯過程中，常見的中間語言形式有逆波蘭表示法、抽象語法樹、三元式、四元式。3．語法制導(dǎo)翻譯的方法就是為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序〔語義動(dòng)作或語義子程序〕，并在語法分析的同時(shí)執(zhí)行它們。4．編譯過程中，常見的中間語言形式有逆波蘭表示法、抽象語法樹、三元式、四元式。6．文法符號(hào)的屬性有兩種，一種稱為繼承屬性，另一種稱為綜合屬性。7．四元式之間的聯(lián)系是通過臨時(shí)變量實(shí)現(xiàn)的。8．在屬性文法中，終結(jié)符只有____綜合屬性。10．語法制導(dǎo)翻譯的方法就是為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序〔語義動(dòng)作或語義子程序〕，并在語法分析的同時(shí)執(zhí)行它們。11．目前較常見的語言語義的描述形式是__屬性文法______，并使用__語法制導(dǎo)翻譯方法完成對(duì)語法成分的翻譯。〔優(yōu)化、存儲(chǔ)、錯(cuò)誤管理〕1.代碼優(yōu)化的含義是：對(duì)代碼進(jìn)展等價(jià)變換，使得變換后的代碼具有更高的時(shí)間效率和空間效率。2.按照優(yōu)化對(duì)象所涉及的程序范圍，優(yōu)化分為局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。3.基本塊，是指程序中—順序執(zhí)行的語句序列，其中只有一個(gè)入口和一個(gè)出口。4.從編譯角度看，分配目標(biāo)程序數(shù)據(jù)空間的基本策略有：靜態(tài)分配策略、棧式動(dòng)態(tài)分配策略和堆式動(dòng)態(tài)分配策略。三、判斷題1．設(shè)r和s分別為正規(guī)式，則有L(r|s)=L(r)|L(s).。(×)2．一個(gè)文法的所有句型的集合形成該文法所能承受的語言。(×)3．語法分析之所以采用上下文無關(guān)文法是因?yàn)樗拿枋瞿芰ψ顝?qiáng)。(×)4．由于LR(0)分析表構(gòu)造簡單，所以它的描述能力強(qiáng)，適用面寬；LR(1)分析表因構(gòu)造復(fù)雜而描述能力弱，適用面窄。(×)5．逆波蘭表示法表示表達(dá)式時(shí)無需使用括號(hào)。(√)6．自動(dòng)機(jī)M和M’的狀態(tài)個(gè)數(shù)不同，則二者必不等價(jià)。(×)7．LL(1)文法一定不含左遞歸和二義性。(√)8．所有LR分析器的總控程序都是一樣的，只是分析表各有不同。(√)9．無論是三元式表示還是間接三元式表示的中間代碼，其三元式在三元式表中的位置一旦確定就很難改變。(√)10．三地址語句類似于匯編語言代碼，可以看成中間代碼的一種抽象形式。(√)11．最左推導(dǎo)也被稱為標(biāo)準(zhǔn)推導(dǎo)。〔×〕12．運(yùn)算對(duì)象排列的先后順序在后綴式和中綴式中不同。〔×〕13．出現(xiàn)在移進(jìn)-歸約分析器棧中的內(nèi)容被稱為文法G的活前綴。〔√〕14．LR方法可以分析含有左遞歸的文法。〔√〕15．三元式的編號(hào)具有雙重含義，既代表此三元式，又代表三元式存放的結(jié)果。〔√〕16．語義規(guī)則中的屬性有兩種：綜合屬性與繼承屬性。〔√〕17．移進(jìn)-歸約分析器的格局中棧的內(nèi)容一般是文法符號(hào)與狀態(tài)。〔√〕18．由于遞歸下降子程序方法較LL〔1〕方法簡單，因此它要求文法不必是LL〔1〕文法。〔×〕19．四元式的編號(hào)具有雙重含義，既代表此四元式，又代表四元式存放的結(jié)果。〔×〕20．用高級(jí)語言編寫的源程序必須經(jīng)過編譯，產(chǎn)生目標(biāo)程序后才能運(yùn)行。〔×〕21．源程序到目標(biāo)程序的變換是等價(jià)變換，即兩者構(gòu)造不同，但語義是一致的。〔√〕22．對(duì)于任何一個(gè)正規(guī)式e，都存在一個(gè)DFAA，使得L〔e〕=L〔A〕。〔√〕23．最小化的DFA，它的狀態(tài)數(shù)最小。〔√〕24．NFA確實(shí)定化算法具有消除ε邊的功能。〔√〕25．每個(gè)非終結(jié)符產(chǎn)生的終結(jié)符號(hào)串都是該語言的子集。〔×〕26．一個(gè)語言的文法是不唯一的。〔√〕27．語法錯(cuò)誤校正的目的是為了把錯(cuò)誤改正過來。〔×〕28．源程序和目標(biāo)程序是等價(jià)關(guān)系。〔√〕29．編譯程序中錯(cuò)誤處理的任務(wù)是對(duì)檢查出的錯(cuò)誤進(jìn)展修改。〔×〕30．使用有限自動(dòng)機(jī)可以實(shí)現(xiàn)單詞的識(shí)別。〔√〕31．一個(gè)非確定的有限自動(dòng)機(jī)NFA可以通過多條路徑識(shí)別同一個(gè)符號(hào)串。〔√〕32．最小化的DFA所識(shí)別承受的正規(guī)集最小。〔×〕33．一個(gè)語言〔如C語言〕的句子是有窮的。〔×〕34．LL〔1〕方法又稱為預(yù)測(cè)分析方法。〔√〕35．一個(gè)LL〔1〕文法是無二義和無回溯方法。〔√〕36．語法分析器可以檢查出程序中的所有錯(cuò)誤。〔×〕37．LR分析法是自上而下的語法分析方法。〔×〕三、多項(xiàng)選擇題1.編譯器的各個(gè)階段的工作都涉及到〔AE〕A.表格處理B.詞法分析C.語法分析D.語義分析E.出錯(cuò)處理2.令＝{a,b}，則上的符號(hào)串的全體可用下面的正規(guī)式表示。〔ABE〕A.(a|b)*B.(a*|b*)*C.(a|b)+D.(ab)*E.(a*b*)*3.自上而下的分析方法有：〔AD〕A.遞歸下降分析法B.LR〔0〕分析法C.LALR〔1〕分析法D.LL〔1〕分析法E.SLR〔1〕分析法4.文法G：G[S]：S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD是〔A〕。A.0型文法B.1型文法C.2型文法D.3型文法E.上下文有關(guān)文法5.對(duì)LR分析表的構(gòu)造，有可能存在的動(dòng)作沖突有：〔AD〕A.移進(jìn)/歸約沖突B.移進(jìn)/移進(jìn)沖突C.歸約沖突D.歸約/歸約沖突E.移進(jìn)沖突6.一個(gè)編譯器可能有的階段為〔ABCDE〕A.詞法分析B.語法分析C.語義分析D.中間代碼生成E.目標(biāo)代碼生成7令＝{a,b}，則上的所有以b開頭，后跟假設(shè)干個(gè)〔可為0個(gè)〕ab的符號(hào)串的全體可用下面的正規(guī)式表示。〔AB〕A.b(ab)*B.(ba)*bC.b(a|b)+D.(ba)+bE.b(a|b)*8.自下而上的分析方法有：〔BCE〕A.遞歸下降分析法B.LR〔0〕分析法C.LALR〔1〕分析法D.LL〔1〕分析法E.SLR〔1〕分析法9.一般來說，編譯器可分為前端和后端，以下編譯階段可被劃分為編譯的前端的有：〔ABCDE〕A.詞法分析B.語法分析C.語義分析D.中間代碼生成E.中間代碼優(yōu)化10．令＝{a,b}，則上的符號(hào)串的全體可用下面的正規(guī)式表示。〔ABE〕A.(a|b)*B.(a*|b*)*C.(a|b)+D.(ab)*E.(a*b*)*11．以下符號(hào)串是符號(hào)集＝{a,b}上的正規(guī)式的有：〔ABCDE〕A.εB.aC.abD.(ab｜a)(ab｜a)E.ab｜ab12．正規(guī)式服從的代數(shù)規(guī)律有：〔ABDE〕A.“或〞運(yùn)算服從交換律B.“或〞運(yùn)算服從結(jié)合律C.“連接〞運(yùn)算服從交換律D.“連接〞運(yùn)算服從結(jié)合律E.“連接〞運(yùn)算可對(duì)“或〞運(yùn)算進(jìn)展分配13．令＝{a,b}，則上的所有以b開頭，后跟假設(shè)干個(gè)〔可為0個(gè)〕ab的符號(hào)串的全體可用下面的正規(guī)式表示。〔AB〕A.b(ab)*B.(ba)*bC.b(a|b)+D.(ba)+bE.b(a|b)*14．一個(gè)LR分析器包括：〔ADE〕A.一個(gè)總控程序B.一個(gè)工程集C.一個(gè)活前綴D.一個(gè)分析棧E.一張分析表15．LR分析器的核心局部是一張分析表，該表包括〔DE〕等子表。A.LL〔1〕分析表B.LR〔1〕分析表C.SLR〔1〕分析表D.Action表E.goto表16．Action表中的每一項(xiàng)Action[S,a]所表示的動(dòng)作可能為：〔ABCD〕A.移進(jìn)B.承受C.歸約D.出錯(cuò)E.待約五．簡答題1．構(gòu)造正規(guī)表達(dá)式((a|b)*|aa)*b的NFA。解：2．設(shè)M=({x,y},{a,b},f,x,{y})為一非確定的有限自動(dòng)機(jī)，其中f定義如下：f(x,a)={x,y} f{x,b}={y}f(y,a)=Φ f{y,b}={x,y} 試構(gòu)造相應(yīng)確實(shí)定有限自動(dòng)機(jī)M′。解：對(duì)照自動(dòng)機(jī)的定義M=(S,Σ,f,So,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，因此M是一非確定有限自動(dòng)機(jī)。 先畫出NFAM相應(yīng)的狀態(tài)圖，如以以以下圖所示。用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣，如下表所示。將轉(zhuǎn)換矩陣中的所有子集重新命名，形成下表所示的狀態(tài)轉(zhuǎn)換矩陣，即得到 M′=({0,1,2},{a,b},f,0,{1,2})，M′狀態(tài)轉(zhuǎn)換圖如以以以下圖所示。〔注意：此題由于集合的命名和先后順序不同，可能最終結(jié)果不同。〕3．畫出編譯程序的總體構(gòu)造圖，簡述各局部的主要功能。解：編譯程序的總體框圖如下所示：〔1〕詞法分析器，又稱掃描器，它承受輸入的源程序，對(duì)源程序進(jìn)展詞法分析，識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是二元式(單詞種別，單詞自身的值)流。〔2〕語法分析器，對(duì)單詞符號(hào)串進(jìn)展語法分析〔根據(jù)語法規(guī)則進(jìn)展推導(dǎo)或歸約〕，識(shí)別出程序中的各類語法單位，最終判斷輸入串是否構(gòu)成語法上正確的句子。〔3〕語義分析及中間代碼生成器，按照語義規(guī)則對(duì)語法分析器歸約出〔或推導(dǎo)出〕的語法單位進(jìn)展語義分析并把它們翻譯成一定形式的中間代碼。編譯程序可以根據(jù)不同的需要選擇不同的中間代碼形式，有的編譯程序甚至沒有中間代碼形式，而直接生成目標(biāo)代碼。〔4〕優(yōu)化器對(duì)中間代碼進(jìn)展優(yōu)化處理。一般最初生成的中間代碼執(zhí)行效率都對(duì)比低，因此要做中間代碼的優(yōu)化，其過程實(shí)際上是對(duì)中間代碼進(jìn)展等價(jià)替換，使程序在執(zhí)行時(shí)能更快，并占用更小的空間。〔5〕目標(biāo)代碼生成器，把中間代碼翻譯成目標(biāo)程序。中間代碼一般是一種與機(jī)器無關(guān)的表示形式，只有把它再翻譯成與機(jī)器硬件直接相關(guān)的機(jī)器能識(shí)別的語言，即目標(biāo)程序，才能在機(jī)器上運(yùn)行。〔6〕表格管理模塊保持一系列的表格，登記源程序的各類信息和編譯各階段的進(jìn)展?fàn)顩r。編譯程序各個(gè)階段所產(chǎn)生的中間結(jié)果都記錄在表格中，所需要的信息也大多從表格中獲取，整個(gè)編譯過程都在不斷和表格打交道。〔7〕出錯(cuò)處理程序?qū)Τ霈F(xiàn)在源程序中的錯(cuò)誤進(jìn)展處理。如果源程序有錯(cuò)誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)告給用戶。編譯程序的各個(gè)階段都有可能發(fā)現(xiàn)錯(cuò)誤，出錯(cuò)處理程序要對(duì)發(fā)現(xiàn)的錯(cuò)誤進(jìn)展處理、記錄，并反映給用戶。4．構(gòu)造一個(gè)DFA，它承受Σ={0,1}上所有滿足如下條件的字符串：每個(gè)1后面都有0直接跟在右邊。解：〔1〕0*(0|10)*0*或者(0|10)*〔2〕=1\*GB3①NFA〔2分〕XX0εY0ε10201ε03ε=2\*GB3②子集法確定化II0I1{X,0,1,3,Y}{0,1,3,Y}{2}{0,1,3,Y}{0,1,3,Y}{2}{2}{1,3,Y}-{1,3,Y}{1,3,Y}{2}重新命名狀態(tài)，即得：S0112322334-443=3\*GB3③最小化首先分為終態(tài)集和非終態(tài)集{3}{1,2,4}因?yàn)?0=220=240=4狀態(tài)均屬于集合{1,2,4}，所以對(duì)于輸入符號(hào)0不能區(qū)分開1，2，4三個(gè)狀態(tài)；11=321=341=3狀態(tài)均屬于集合{3}，所以對(duì)于輸入符號(hào)1也不能區(qū)分開1，2，4三個(gè)狀態(tài)；因此最終的狀態(tài)劃分即為:{3}{1,2,4}，其對(duì)應(yīng)的DFA如以以以下圖所示：0001105．寫出C語言標(biāo)識(shí)符集〔字母或下劃線開頭的由字母、數(shù)字、下劃線構(gòu)成的串〕的正規(guī)式。解答：用D表示數(shù)字0-9，用L表示字母a-z|A-Z，則C語言標(biāo)識(shí)符的正規(guī)式為：〔L|_〕〔L|D|_〕*語法分析局部：6．構(gòu)造一文法，使其描述的語言L={ω|ω∈(a,b)*，且ω中含有一樣個(gè)數(shù)的a和b}。解：S→ε|aA|bBA→b|bS|aAAB→a|aS|bBB7．對(duì)于文法G(S)：S→(L)|aS|aL→L,S|S(1)畫出句型(S,(a))的語法樹。(2)寫出上述句型的所有短語、直接短語和句柄。解：(1)句型(S,(a))的語法樹如以以以下圖所示：(2)從語法樹中可以找到〔3分〕短語：a;(a);S;S,(a);(S,(a))直接短語：a;S句柄：S8．令文法G[N]為G[N]:N→D|NDD→0|1|2|3|4|5|6|7|8|9給出句子568的最左、最右推導(dǎo)。解：最左推導(dǎo)：NNDNDDDDD5DD56D568最右推導(dǎo)：NNDN8ND8N68D685688．文法G[A]:A→aABl|aB→Bb|d 試給出與G[A]等價(jià)的LL(1)文法G[A′]；解：G[A′]：A→aA′A′→ABl|εB→dB′B′→bB′|ε9．試構(gòu)造下述文法的SLR(1)分析表。G[A]:A→aABl|aB→Bb|d解：拓廣文法〔0〕S→A〔1〕A→aABl〔2〕A→a〔3〕B→Bb〔4〕B→dFirst〔A〕={a}follow〔A〕={#，d}First〔B〕=2b141xcfollow〔B〕={l}SLR〔1〕分析表如下：abdl#AB0S211ACC2S2R2R233S454R45S7S66R1R17R310.試構(gòu)造下述文法的LL(1)分析表。G[S]:S→〔L〕|aL→L，S|S解：消除左遞歸：G(S):S(L)|a LSL’ L’,SL’|ε構(gòu)造FIRST集，如下： 〔1〕FIRST(S)={(,a} 〔2〕FIRST(L)={(,a}〔3〕FIRST(L’)={,,ε}構(gòu)造FOLLOW集如下：〔1〕FOLLOW(S)={#,,,)}〔2〕FOLLOW(L)={)}〔3〕FOLLOW(L’)={)}LL(1)分析表()a,#SS(L)SaLLSL’LSL’L’L’εL’,SL’11．文法G[S]:S→aSbS|bSaS|ε 試證明G[S]是二義文法證明：該文法產(chǎn)生的語言是a的個(gè)數(shù)和b的個(gè)數(shù)相等的串的集合。該文法二義，例如句子abab有兩種不同的最左推導(dǎo)。SaSbSabSabaSbSababSababSaSbSabSaSbSabaSbSababSabab12．文法Ｇ：

S→(L|a

L→S,L|)判斷是不是LL〔1〕文法，如果是請(qǐng)構(gòu)造文法Ｇ的預(yù)測(cè)分析表，如果不是請(qǐng)說明理由。【解】1〕求各非終結(jié)符的FISRT集和FOLLOW集： First〔S〕={(,a} FIRST(L)={〕}FIRST(S)={(,),a} FOLLOW(S)={,#} FOLLOW(L)=FOLLOW(S)={,#}FIRST((L)∩{a}=ΦFIRST(S,L)∩{)}=Φ所以是LL〔1〕文法2〕預(yù)測(cè)分析表：(a,}#SS→(LS→aLL→S,LL→S,LL→)13．文法 SAa|bAc|dc|bdaAd構(gòu)造識(shí)別活前綴的DFA。請(qǐng)根據(jù)這個(gè)DFA來判斷該文法是不是SLR(1)文法并說明理由。【解】S’S’.SS.AaS.bAcS.dcS.bdaA.dI0Sb.AcSb.daA.dI3daSd.cAd.I4AS’S.I1SSA.aI2ASAa.I5bSbA.cI6dSdc.I8Sbd.aAd.I7cSbAc.I9Sbda.I10caFollow(S)={#}Follow(A)={a,c}I4存在沖突且Follow(A)∩{c}={c}I7存在沖突且Follow(A)∩{a}={a}所以不是SLR(1)文法14．設(shè)有文法G[S]:S→S*S|S+S|(S)|i該文法是否為二義文法,并說明理由【解】該文法是二義文法，因?yàn)樵撐姆ù嬖诰渥觟*i+i,該句子有兩棵不同的語法樹如以以下圖。15.構(gòu)造下面文法的LL〔1〕分析表。G[D]:DTLTint|realLidRR,idR|【解】FIRST(T)={intreal}FOLLOW(T)={id}FIRST(L)={id}FOLLOW(L)={#}FIRST(R)={,}FOLLOW(R)={#}FIRST(D)={intreal}FOLLOW(D)={#}因?yàn)镕IRST(int)∩FIRST(real)=ΦFIRST(,idR)∩FOLLOW(R)=Φ所以是LL〔1〕文法，LL〔1〕分析表如下：intrealid,#DDTLDTLTTintTrealLLidRRR,idRR16．給定文法S→aS|bS|a，下面是拓廣文法和識(shí)別該文法所產(chǎn)生的活前綴的DFA。判斷該文法是否是SLR(1)文法：如果是構(gòu)造其SLR(1)分析表，如果不是請(qǐng)說明理由。 (1)將文法G(S)拓廣為G(S’)：(0)S’→S(1)S→aS(2)S→bS(3)S→a(2)識(shí)別該文法所產(chǎn)生的活前綴的DFA如圖1所示。【解】注意到狀態(tài)I1存在“移進(jìn)-歸納〞沖突，計(jì)算S的FOLLOW集合：FOLLOW(S)={#}{a}∩{b}∩FOLLOW(R)=Φ可以采用SLR沖突消解法，得到如下的SLR分析表。從分析表可以看出，表中沒有沖突項(xiàng)，所以該文法是SLR(1)文法。表1SLR分析表ACTIONGOTO狀態(tài)ab#S0S1S231S1S2r342S1S253acc4r15r217．證明下面文法S→AaAb|BbBaA→εB→ε，是LL〔1〕文法，但不是SLR〔1〕文法。證明：〔1〕first〔AaAb〕={a}first〔BbBb〕={b}，有first〔AaAb〕∩first〔BbBb〕=Φ所以根據(jù)LL〔1〕文法的定義，該文法是LL〔1〕文法。〔2〕為了構(gòu)造識(shí)別活前綴的DFA，初態(tài)集包含如下四個(gè)工程：S→.AaAbS→.BbBaA→.B→.但該工程中有兩個(gè)可歸約工程：A→.B→.，產(chǎn)生歸約-歸約沖突，而follow〔A〕={a，b}，follow〔B〕={a，b}，有follow〔A〕∩follow〔B〕≠Φ，所以使用向前看一個(gè)終結(jié)符的方法不能解決此沖突，所以該文法不是SLR〔1〕文法。18．文法G(S)：S→S*aP|aP|*aPP→+aP|+a(1)將文法G(S)改寫為LL(1)文法G’(S)；(2)寫出文法G’(S)的預(yù)測(cè)分析表。解：〔1〕消除左遞歸，文法變?yōu)椋篠→aPS’|*aPS’S’→*aPS’|εP→+aP|+a提取公共左因子，文法變?yōu)镚’(S)：S→aPS’|*aPS’S’→*aPS’|εP→+aP’P’→P|ε〔2〕計(jì)算每個(gè)非終結(jié)符的FIRST集和FOLLOW集：FIRST(S)={a,*} FOLLOW(S)={#}FIRST(S’)={*,ε} FOLLOW(S’)={#}FIRST(P)={+} FOLLOW(P)={*,#}FIRST(P’)={+,ε} FOLLOW(P’)={*,#}構(gòu)造該文法的預(yù)測(cè)分析表如下：*+a#SS→*aPS’S→aPS’S’S’→*aPS’→εPP→+aP’P’P’→εP’→PP’→ε19．文法G(S)：S→aS|bS|a(1)構(gòu)造識(shí)別該文法所產(chǎn)生的活前綴的DFA；(2)判斷該文法是LR(0)還是SLR(1)，并構(gòu)造所屬文法的LR分析表。解：〔1〕將文法G(S)拓廣為G’(S’)：(0)S’→S(1)S→aS(2)S→bS(3)S→a識(shí)別該文法所產(chǎn)生的活前綴的DFA：〔2〕在狀態(tài)I2存在“移近-歸約〞沖突，因此該文法不是LR(0)文法。計(jì)算S的FOLLOW集合：FOLLOW(S)={#}I2中的沖突用FOLLOW集合可以解決，所以該文法是SLR(1)文法。構(gòu)造SLR(1)分析表如下：狀態(tài)ACTIONGOTOab#S0s2s311acc2s2s3r343s2s354r15r220．構(gòu)造文法S→AaAb|BbBaA→εB→ε，的預(yù)測(cè)分析表。答：first〔S〕={a，b},First〔AaAb〕={a}，F(xiàn)irst〔BbBa〕={b}Follow〔A〕={a，b}Follow〔B〕={a，b}ab$SS→AaAbS→BbBaAA→εA→εBB→εB→ε21．設(shè)有如下文法：G[E]：E→EWT|TT→T/F|FF→〔E〕|a|b|cW→+|-證明符號(hào)串a(chǎn)/(b-c)是句子。解答：有推導(dǎo)ETT/FF/Fa/Fa/(E)a/(EWT)a/(TWT)a/(FWT)a/(bWT)a/(b-T)a/(b-c)，即從文法開場(chǎng)符號(hào)E能夠推導(dǎo)出a/(b-c)，所以a/(b-c)是文法G[E]的句子。55．對(duì)于以下文法G[S]：S→Sb|bAA→aA|a〔1〕構(gòu)造一個(gè)與G等價(jià)的LL〔1〕文法G′。〔2〕對(duì)于文法G′,構(gòu)造相應(yīng)的LL〔1〕分析表。解：〔1〕G′：S→bAS′S′→bS′|εA→aA′A′→A|ε〔2〕FIRST〔S〕={b}FIRST〔S′〕={b，ε}FIRST〔A〕={a}FIRST〔A′〕={a，ε}FOLLOW〔S〕={#}FOLLOW〔S′〕={#}FOLLOW〔A〕={b，#}FOLLOW〔A′〕=〔b，#〕LL〔1〕分析表：ab#SS→bAS′S′S′→bS′S′→εAA→aA′A′A′→AA′→εA′→ε22．文法G[S]如下：構(gòu)造該文法的LR〔0〕分析表。G[S]：S→BBB→aB|b解：拓廣文法：〔0〕S→S〔1〕S→BB〔2〕B→aB〔3〕B→b識(shí)別活前綴的DFA如下：LR(0)分析表如下：狀態(tài)ActionGotoab#SB0S3S4121acc2S3S453S3S464R3R3R35R1R1R16R2R2R2語義分析與中間代碼生成：23．給定文法：S→(L)|aL→L,S|S請(qǐng)書寫語義規(guī)則，求輸出句子中每一個(gè)a的括號(hào)嵌套深度。解：用繼承屬性depth表示嵌套深度，則 S’→S S.depth=0 S→(L) L.depth=S.depth+1 S→a print(S.depth) L→L(1),S L(1).depth=L.depth;S.depth=L.depth L→S S.dep