大學(xué)《編譯原理》期末試題含答案(五)

大學(xué)《編譯原理》期末試題含答案一、單項(xiàng)選擇題(共10小題，每小題2分，共20分)語言是A．句子的集合 B．產(chǎn)生式的集合C．符號串的集合 D．句型的集2．編譯程序前三個(gè)階段完成的工作是A．詞法分析、語法分析和代碼優(yōu)化B．代碼生成、代碼優(yōu)化和詞法分析C．詞法分析、語法分析、語義分析和中間代碼生成D．詞法分析、語法分析和代碼優(yōu)化3．一個(gè)句型中稱為句柄的是該句型的最左A．非終結(jié)符號 B．短語 C．句子 直接短4．下推自動(dòng)機(jī)識別的語言是A．0型語言 B．1型語言型語言 型語言5．掃描器所完成的任務(wù)是從字符串形式的源程序中識別出一個(gè)個(gè)具有獨(dú)立含義的最小語單位即A．字符 B．單詞 C．句子 句6．對應(yīng)Chomsky四種文法的四種語言之間的關(guān)系是A．LC．L

LLL0123=LLL0123

D．L

LLL3210LL=L32103 2 1 0 0 1 2 3詞法分析的任務(wù)是A．識別單詞 B．分析句子的含義C．識別句子 D．生成目標(biāo)代8．常用的中間代碼形式不含A．三元式 B．四元式 C．逆波蘭式 D．語法樹代碼優(yōu)化的目的是A．節(jié)省時(shí)間 B．節(jié)省空間C．節(jié)省時(shí)間和空間 D．把編譯程序進(jìn)行等價(jià)交10．代碼生成階段的主要任務(wù)是A．把高級語言翻譯成匯編語言B．把高級語言翻譯成機(jī)器語言C．把中間代碼變換成依賴具體機(jī)器的目標(biāo)代碼D．把匯編語言翻譯成機(jī)器語言二、填空題（本大題共5小題，每小題2分，共10分）)(并翻譯其意義。(和兩種。的())。(方案。()(。三、名詞解釋題(共5小題，每小題4分，共20分)詞法分析詞法分析的主要任務(wù)是從左向右掃描每行源程序的符號，按照詞法規(guī)則從構(gòu)成源程序的字符串中識別出一個(gè)個(gè)具有獨(dú)立意義的最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示(token)，送給語法分析程序。文法若文法的任何兩個(gè)產(chǎn)生式A|都滿足下面兩個(gè)條件：FIRST())=；*)FOLLOWA。我們把滿足這兩個(gè)條件的文法叫做法，其中的第一個(gè)L代表從左向右掃描輸入，第二個(gè)L表示產(chǎn)生最左推導(dǎo)，1代表在決定分析器的每步動(dòng)作時(shí)向前看一個(gè)輸入符號。除了沒有公共左因子外，LL(1)文法還有一些明顯的性質(zhì)，它不是二義的，也不含左遞歸。語法樹句子的樹結(jié)構(gòu)表示法稱為語法樹(語法分析樹或語法推導(dǎo)樹)。N G=(V，V，P，S)G的任何句型都能構(gòu)造與之關(guān)聯(lián)的語法樹。這棵樹具有下列特征：N S。V中的一個(gè)符號。A，且其所有直接子孫的標(biāo)記從左向右的排列R次序?yàn)锳A…A，那么AAA…A一定是P中的一條產(chǎn)生式。R12 12 RNA的節(jié)點(diǎn)至少有一個(gè)除它以外的子孫，則AV。N若樹的所有葉節(jié)點(diǎn)上的標(biāo)記從左到右排列為字符串w，則w是文法的句型；若w中僅含終結(jié)符號，則w為文法G所產(chǎn)生的句子。4．LR(0)分析器所謂LR(0)每一步，只須根據(jù)分析棧當(dāng)前已移進(jìn)和歸約出的全部文法符號，并至多再0個(gè)輸入符號，就能確定相對于某一產(chǎn)生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當(dāng)前所應(yīng)采取的分析動(dòng)作(是移進(jìn)。5．語言和文法文法就是語言結(jié)構(gòu)的定義和描述，是有窮非空的產(chǎn)生式集合。文法G定義為四元組的形式：N G=(V，V，P，S)N V V N TN T N N 稱為終結(jié)符號集合；P是產(chǎn)生式的集合(非空)；S是開始符號(或識別符號)。N T N N 這里，V

∩V=，SV。V=V∪V，稱為文法G的字母表，它是出現(xiàn)文法產(chǎn)生式中的一切符號的集合。文法G所描述的語言用L(G)表示，它由文法G所產(chǎn)生的全部句子組成，即L(G)={x|S*x，其中S為文法開始符號，且xV }T簡單的說，文法描述的語言是該文法一切句子的集合。四、簡答題(共4小題，每小題5分，共20分)1．編譯程序和高級語言有什么區(qū)別?語言表示的目標(biāo)程序（這個(gè)過程即編譯），才能由計(jì)算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn)換過的叫目標(biāo)程序，也就是機(jī)器語言。將匯編語言編寫的程序，按照一一對應(yīng)的關(guān)系，轉(zhuǎn)換成用機(jī)器語言表示的程序。解釋型編譯程序?qū)⒏呒壵Z言程序的一個(gè)語句，先解釋成為一組機(jī)器語言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個(gè)程序?qū)υ払ASIC語言就是解釋型高級語言。編譯型編譯程序?qū)⒓塅ORTRAN語言就是編譯型高級語言。2．編?(稱為)。3．簡述自下而上的分析方法。“”歸約”，直到根節(jié)點(diǎn)。4．簡述代碼優(yōu)化的目的和意義。好”一種等價(jià)變換，在保證變換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目標(biāo)程序運(yùn)行時(shí)所需要的時(shí)間短，同時(shí)所占用的存儲空間少。五、綜合應(yīng)用題(31030分)證明下述文法G：SaSbS|aS|d是二義性文法。解：一個(gè)文法，如果存在某個(gè)句子有不只一棵語法分析樹與之對應(yīng)，那么稱這個(gè)文法是二義性文法。句子aadbd有兩棵語法樹。如下圖：S Sa Sa S b Sa S d a S b d d (1) (2)由此可知，SaSbS|aS|d定義的文法是二義性文法。baSb句型baSb的語法樹如圖(2)所示。 SA Bb B S bab為句型b的相對于Sa為句型b的相對于Ab為句型BbaSbB柄。3．設(shè)有非確定的有自限動(dòng)機(jī)NFAM=({A，B，C}