編譯原理試題答案

1、編譯原理期末測(cè)試題專(zhuān)業(yè)班級(jí)：學(xué)號(hào)：姓名：總分一、單項(xiàng)選擇題（共10小題，每小題2分）（題分20分）A句子的集合B產(chǎn)生式的集合C.符號(hào)串的集合D.句型的集合2編譯程序前三個(gè)階段完成的工作是A詞法分析、語(yǔ)法分析和代碼優(yōu)化B代碼生成、代碼優(yōu)化和詞法分析C詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成D詞法分析、語(yǔ)法分析和代碼優(yōu)化3個(gè)句型中稱(chēng)為句柄的是該句型的最左A非終結(jié)符號(hào)B.短語(yǔ)C.句子D.直接短語(yǔ)4下推自動(dòng)機(jī)識(shí)別的語(yǔ)言是A0型語(yǔ)言B1型語(yǔ)言C2型語(yǔ)言D3型語(yǔ)言5掃描器所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立含義的最小語(yǔ)法單位即A字符B單詞C句子D句型6對(duì)應(yīng)Chomsky四種文法的四種

2、語(yǔ)言之間的關(guān)系是ALuLuLuL0123CL=LuLuL32107詞法分析的任務(wù)是A識(shí)別單詞C識(shí)別句子8常用的中間代碼形式不含A三元式B四元式DLuLuL=LB分析句子的含義D.生成目標(biāo)代碼C逆波蘭式D語(yǔ)法樹(shù)9 代碼優(yōu)化的目的是A節(jié)省時(shí)間C節(jié)省時(shí)間和空間10 代碼生成階段的主要任務(wù)是B節(jié)省空間D把編譯程序進(jìn)行等價(jià)交換A把高級(jí)語(yǔ)言翻譯成匯編語(yǔ)言B把高級(jí)語(yǔ)言翻譯成機(jī)器語(yǔ)言C把中間代碼變換成依賴(lài)具體機(jī)器的目標(biāo)代碼D把匯編語(yǔ)言翻譯成機(jī)器語(yǔ)言二、填空題（本大題共5小題，每小題2分）（題分10分）I得分1編譯程序首先要識(shí)別出源程序中每個(gè)（），然后再分析每個(gè)（）并翻譯|得其意義。2 編譯器常用的語(yǔ)法分析方法

3、有（）和（）兩種。3通常把編譯過(guò)程分為分析前端與綜合后端兩大階段。詞法、語(yǔ)法和語(yǔ)義分析是對(duì)源程序的（），中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對(duì)源程序的（）。4程序設(shè)計(jì)語(yǔ)言的發(fā)展帶來(lái)了日漸多變的運(yùn)行時(shí)存儲(chǔ)管理方案，主要分為兩大類(lèi)，即：（）方案和（）方案。5對(duì)編譯程序而言，輸入數(shù)據(jù)是（），輸出結(jié)果是（）。三、名詞解釋題（共5小題，每小題4分）（題分20分）|得分1詞法分析2 LL（1）文法3 語(yǔ)法樹(shù)4 LR（0）分析器5語(yǔ)言和文法四、簡(jiǎn)答題（共4小題，每小題5分）（題分20分）|得分1編譯程序和高級(jí)語(yǔ)言有什么區(qū)別？2編譯程序的工作分為那幾個(gè)階段？3簡(jiǎn)述自下而上的分析方法。4簡(jiǎn)述代碼優(yōu)化的目的

4、和意義。五、綜合應(yīng)用題（共3小題，每小題10分）（題分30分）1 證明下述文法G:SaSbS|aS|d是二義性文法。2 對(duì)于文法GS:StAB,ATAa|bB,Ba|Sb求句型baSb的全部短語(yǔ)、直接短語(yǔ)和句柄？a圖五(2)句型baSb的的語(yǔ)法樹(shù)句型baSb的語(yǔ)法樹(shù)如圖五(2)所示。3 設(shè)有非確定的有自限動(dòng)機(jī)NFAM=(A,B，C,0,1，5,A,C)，其中:5 (A,0)=C5(A,1)=A,B5(B,1)=C5(C,1)=C。請(qǐng)畫(huà)出狀態(tài)轉(zhuǎn)換距陣和狀態(tài)轉(zhuǎn)換圖。參考答案一、單項(xiàng)選擇題（共10小題，每小題2分，共20分）A句子的集合B產(chǎn)生式的集合C.符號(hào)串的集合D.句型的集合2編譯程序前三個(gè)階段

5、完成的工作是A詞法分析、語(yǔ)法分析和代碼優(yōu)化B代碼生成、代碼優(yōu)化和詞法分析C.詞法分析、語(yǔ)法分析、語(yǔ)義分析和中間代碼生成D詞法分析、語(yǔ)法分析和代碼優(yōu)化3個(gè)句型中稱(chēng)為句柄的是該句型的最左A非終結(jié)符號(hào)B.短語(yǔ)C.句子D直接短語(yǔ)4下推自動(dòng)機(jī)識(shí)別的語(yǔ)言是A0型語(yǔ)言B1型語(yǔ)言C2型語(yǔ)言D3型語(yǔ)言5掃描器所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立含義的最小語(yǔ)法單位即A字符B單詞C句子D句型6 對(duì)應(yīng)Chomsky四種文法的四種語(yǔ)言之間的關(guān)系是AL0CL!CL2CL3CL3=L2CL!°L07詞法分析的任務(wù)是A識(shí)別單詞C識(shí)別句子8常用的中間代碼形式不含A三元式B四元式9 代碼優(yōu)化的目的是

6、A節(jié)省時(shí)間C節(jié)省時(shí)間和空間10 代碼生成階段的主要任務(wù)是A把高級(jí)語(yǔ)言翻譯成匯編語(yǔ)言DLoULqpB分析句子的含義D.生成目標(biāo)代碼C逆波蘭式D語(yǔ)法樹(shù)B節(jié)省空間D把編譯程序進(jìn)行等價(jià)交換B把高級(jí)語(yǔ)言翻譯成機(jī)器語(yǔ)言C把中間代碼變換成依賴(lài)具體機(jī)器的目標(biāo)代碼D把匯編語(yǔ)言翻譯成機(jī)器語(yǔ)言二、填空題（本大題共5小題，每小題2分，共10分）1編譯程序首先要識(shí)別出源程序中每個(gè)（單詞），然后再分析每個(gè)（句子）并翻譯其意義。2編譯器常用的語(yǔ)法分析方法有（自底向上）和（自頂向下）兩種。3通常把編譯過(guò)程分為分析前端與綜合后端兩大階段。詞法、語(yǔ)法和語(yǔ)義分析是對(duì)源程序的（分析），中間代碼生成、代碼優(yōu)化與目標(biāo)代碼的生成則是對(duì)源程

7、序的（綜合）。4程序設(shè)計(jì)語(yǔ)言的發(fā)展帶來(lái)了日漸多變的運(yùn)行時(shí)存儲(chǔ)管理方案，主要分為兩大類(lèi)，即靜態(tài)存儲(chǔ)分配）方案和（動(dòng)態(tài)存儲(chǔ)分配）方案。5.對(duì)編譯稈序而言輸入數(shù)據(jù)是（源稈序）輸出結(jié)果是（目標(biāo)稈序）。三、名詞解釋題（共5小題，每小題4分，共20分）1 詞法分析詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號(hào)按照詞法規(guī)則從構(gòu)成源程序的字符串中識(shí)別出一個(gè)個(gè)具有獨(dú)立意義的最小語(yǔ)法單位.并轉(zhuǎn)換成統(tǒng)一的內(nèi)咅8表示（token）.送給語(yǔ)法分析程序。2 LL（1）文法若文法的仟何兩個(gè)產(chǎn)牛式AtaIB者E滿(mǎn)足下面兩個(gè)條件：（1）FIRSTQ）cFIRST（B）三込；若Bn*£那么FIRSTQ）cFOLLOW

8、（A）二“我們把滿(mǎn)足這兩個(gè)條件的文法叫做LL（1）文法其中的第一"個(gè)L代表從左向右掃描輸入第二個(gè)L表示產(chǎn)牛最左推導(dǎo).1代表在決定分析器的每步動(dòng)作時(shí)向前看一個(gè)輸入符號(hào)。除了沒(méi)有公共左因子外.LL（1）文法還有一些明顯的性質(zhì)它不是二義的也不含左涕歸。3 語(yǔ)法樹(shù)句子的樹(shù)結(jié)構(gòu)表示法稱(chēng)為語(yǔ)法樹(shù)（語(yǔ)法分析樹(shù)或語(yǔ)法推導(dǎo)樹(shù)）。給定文法G=（Vn，VP.S）.對(duì)干G的仟何句型都能構(gòu)造與之關(guān)聯(lián)的語(yǔ)法樹(shù)。這棵樹(shù)具有下列特征：（1）根節(jié)點(diǎn)的標(biāo)記是開(kāi)始符號(hào)S。（2）每個(gè)節(jié)點(diǎn)的標(biāo)記都是V中的一符號(hào)。(3) 若一棵子樹(shù)的根節(jié)點(diǎn)為A,且其所有直接子孫的標(biāo)記從左向右的排列次序?yàn)锳AA，那么atA,a.A定是P中的一條

9、產(chǎn)牛式。若一標(biāo)記為A的節(jié)點(diǎn)至少有一個(gè)除它以外的子孫，則A巳VN。(5)若樹(shù)的所有葉節(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w,則w是文法G的句型；若w中僅含終結(jié)符號(hào)，則w為文法G所產(chǎn)牛的句子。4 .LR(O)分析器所謂LR(O)分析.是指從左至右掃描和自底向上的語(yǔ)法分析.曰在分析的每一步只須根據(jù)分析棧當(dāng)前已移進(jìn)和歸約岀的全部文法符號(hào)并至多再向前杳看0個(gè)輸入符號(hào)就能確定相對(duì)干某一產(chǎn)牛式左部符號(hào)的句柄是否已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動(dòng)作(是移進(jìn)還是按某一產(chǎn)牛式進(jìn)行歸約等)。5.語(yǔ)言和文法文法就是語(yǔ)言結(jié)構(gòu)的定義和描述.是有窮非空的產(chǎn)牛式集合。文法G定義為四元組的形式：g=(vn,

10、VP,S)其中：VN是非空有窮集合.稱(chēng)為非終結(jié)符號(hào)集合；VT是非空有窮集合.稱(chēng)為終結(jié)符號(hào)集合；P是產(chǎn)牛式的集合(非空)；S是開(kāi)始符號(hào)(或識(shí)別符號(hào))。汶里.v”,nv=0,sgV/V二v”,Uv,稱(chēng)為文法g的字母表它是出頊.NNT文法產(chǎn)牛式中的一切符號(hào)的集合。文法G所描述的語(yǔ)言用L(G)表示它由文法G所產(chǎn)牛的全部句子組成即L(G)二xlSn*x其中S為文法開(kāi)始符號(hào)且xgV+J簡(jiǎn)單的說(shuō)文法描述的語(yǔ)言是該文法一切句子的集合。四、簡(jiǎn)答題(共4小題每小題5分共20分)1.編譯程序和高級(jí)語(yǔ)言有什么區(qū)別?用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫(xiě)的稈序必須先送入計(jì)算機(jī)經(jīng)過(guò)轉(zhuǎn)換成用機(jī)器語(yǔ)言表示的目標(biāo)程序(這個(gè)討程即編譯)才能由

11、計(jì)算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過(guò)稈的程序叫編譯程序。匯編程序是指沒(méi)有編譯過(guò)的匯編語(yǔ)言源文件。編譯程序轉(zhuǎn)換討的叫目標(biāo)稈序也就是機(jī)器語(yǔ)言。編譯稈序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯稈序用來(lái)將匯編語(yǔ)言編寫(xiě)的程序，按照一一對(duì)應(yīng)的關(guān)系，轉(zhuǎn)換成用機(jī)器語(yǔ)言表示的程序。解釋型編譯程序?qū)⒏呒?jí)語(yǔ)言程序的一個(gè)語(yǔ)句，先解釋成為一組機(jī)器語(yǔ)言的指令，然后立即執(zhí)行.執(zhí)行完了.取下一組語(yǔ)句解釋和執(zhí)行.如此繼續(xù)到完成一個(gè)程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以講行人和計(jì)算機(jī)的"對(duì)話"，隨時(shí)可以修改高級(jí)語(yǔ)言的程序。BASIC語(yǔ)言就是解釋型高級(jí)語(yǔ)言。編譯型編譯程序?qū)⒓?jí)語(yǔ)言編寫(xiě)的程序，一次就會(huì)部翻譯

12、成機(jī)器語(yǔ)言表示的程序，而且過(guò)程講行很快，在過(guò)程中不能講行人機(jī)對(duì)話修改。FORTRAN語(yǔ)言就是編譯型高級(jí)語(yǔ)言。2編譯程序的工作分為那幾個(gè)階段？詞法分析、語(yǔ)法分析和語(yǔ)義分析是對(duì)源程序講行的分析（稱(chēng)為編譯程序的前端），而中間代碼牛成、代碼優(yōu)化和代碼生成三個(gè)階段合稱(chēng)為對(duì)源程序講行綜合（稱(chēng)為編譯程序的后端），它們從源程序的中間表示建立起和源程序等價(jià)的目標(biāo)程序3簡(jiǎn)述自下而上的分析方法。所謂自下而上分析法就是從輸入串開(kāi)始逐步講行“歸約”直至歸約到文法的開(kāi)始符號(hào)；或者說(shuō)從語(yǔ)法樹(shù)的末端開(kāi)始步步向上“歸約”直到根節(jié)點(diǎn)。4簡(jiǎn)述代碼優(yōu)化的目的和意義。代碼優(yōu)化是盡量牛成“好”的代碼的編譯階段。也就是要對(duì)稈序代碼講行種等價(jià)變換在保證變換前后代碼執(zhí)行結(jié)果相同的前提下盡量使目標(biāo)程序運(yùn)行時(shí)所需要的時(shí)間短同時(shí)所占用的存儲(chǔ)空間少。五、綜合應(yīng)用題（共3小題每小題10分共30分）1證明下述文法G:SaSbS|aS|d是二義性文法。解:個(gè)文法如果存在某個(gè)句子有不只一棵語(yǔ)法分析樹(shù)與之對(duì)應(yīng)那么稱(chēng)汶個(gè)文法是二義性文法。句子aadbd有兩棵語(yǔ)法樹(shù)。如下圖：d(2)由此可知.SaSbS|aS|d定義的文法是二義性文法。2對(duì)于文法GS:StAB,ATAa|bB,Ba|Sb求句型baSb的全部短語(yǔ)、直接短語(yǔ)和句柄？句型baSb的語(yǔ)法樹(shù)如圖五(2)所示。a圖五(2)句型ba