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

大學(xué)《編譯原理》期末試題含答案一、單項(xiàng)選擇題(共10小題，每小題2分，共20分)語(yǔ)言是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．句子 直接短4．下推自動(dòng)機(jī)識(shí)別的語(yǔ)言是A．0型語(yǔ)言 B．1型語(yǔ)言型語(yǔ)言 型語(yǔ)言5．掃描器所完成的任務(wù)是從字符串形式的源程序中識(shí)別出一個(gè)個(gè)具有獨(dú)立含義的最小語(yǔ)單位即A．字符 B．單詞 C．句子 句6．對(duì)應(yīng)Chomsky四種文法的四種語(yǔ)言之間的關(guān)系是A．LC．L

LLL0123=LLL0123

D．L

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

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