編譯原理試題答案

料.料.編譯原理期末測試題專業(yè)班級： 學號： 姓名： 總分 一、單項選擇題（共10小題，每小題2分）（題分20分）語言是句子的集合 B.產生式的集合C.符號串的集合 D.句型的集合編譯程序前三個階段完成的工作是詞法分析、語法分析和代碼優(yōu)化代碼生成、代碼優(yōu)化和詞法分析詞法分析、語法分析、語義分析和中間代碼生成詞法分析、語法分析和代碼優(yōu)化一個句型中稱為句柄的是該句型的最左非終結符號 B.短語C.句子D.直接短語下推自動機識別的語言是0型語言 B.1型語言C.2型語言 D.3型語言掃描器所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即字符 B.單詞 C.句子 D.句型對應Chomsky四種文法的四種語言之間的關系是A.LocLicLA.LocLicL2cL3C.L3=L<uLiuLoB?L3cL2cLicLcD?LocLiuL^Ls詞法分析的任務是A.詞法分析的任務是A.識別單詞C.識別句子&常用的中間代碼形式不含A.三元式B.四元式分析句子的含義D.生成目標代碼逆波蘭式 D.語法樹B.B.節(jié)省空間D.把編譯程序進行等價交換代碼優(yōu)化的目的是A.節(jié)省時間C?節(jié)省時間和空間

代碼生成階段的主要任務是把高級語言翻譯成匯編語言把高級語言翻譯成機器語言把中間代碼變換成依賴具體機器的目標代碼把匯編語言翻譯成機器語言二、填空題（本大題共5小題，每小題2分）（題分10分）丨得分1.編譯程序首先要識別出源程序中每個（ ）,然后再分析每個（）并翻譯其意義。2.編譯器常用的語法分析方法有（）和（）兩種。通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的（ ），中間代碼生成、代碼優(yōu)化與目標代碼的生成則是對源程序的（ ）。程序設計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大類，即：（ ）方案和（ ）方案。對編譯程序而言，輸入數(shù)據(jù)是（ ）,輸出結果是（ ）。三、 名詞解釋題洪5小題，每小題4分）（題分20分）詞法分析LL⑴文法3?語法樹LR（0）分析器語言和文法四、 簡答題（共4小題，每小題5分） （題分20分）編譯程序和高級語言有什么區(qū)別？編譯程序的工作分為那幾個階段？簡述自下而上的分析方法。簡述代碼優(yōu)化的目的和意義。五、綜合應用題(共3小題，每小題10分)(題分30分)1?證明下述文法G:1?證明下述文法G:是二義性文法。S->aSbS|aS|d對于文法G⑸：StAB,A->Aa|bB,B->a|Sb求句型baSb的全部短語、直接短語和句柄？句型baSb的語法樹如圖五⑵所示。圖五(2)句型baSb的的語法擁設有非確定的有自限動機NFAM二({A,B,C},{0,】},8,{A},{C}),其中：5(A,0)={C}5(A,1)={A,B}8(B,1)={C}5(C,1)={C}O請畫出狀態(tài)轉換距陣和狀態(tài)轉換圖。

參考答案一、單項選擇題（共10小題，每小題2分，共20分）語言是A.句子的集合 B.產生式的集合C.符號串的集合 D.句型的集合編譯程序前三個階段完成的工作是詞法分析、語法分析和代碼優(yōu)化代碼生成、代碼優(yōu)化和詞法分析詞法分析、語法分析、語義分析和中間代碼生成詞法分析、語法分析和代碼優(yōu)化一個句型中稱為句柄的是該句型的最左A.非終結符號B.短語C.句子D.直接短語下推自動機識別的語言是A.0型語言 B.1型語言C.2型語言 D.3型語言掃描器所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即A.字符 B.單詞 C.句子 D.句型對應Chomsky四種文法的四種語言之間的關系是A.L0CL1UL2CL3C.A.L0CL1UL2CL3C.L3=L2cLicLc詞法分析的任務是A.識別單詞C.識別句子&常用的中間代碼形式不含A.三元式B.四元式代碼優(yōu)化的目的是A.節(jié)省時間C.節(jié)省時間和空間代碼生成階段的主要任務是把高級語言翻譯成匯編語言把高級語言翻譯成機器語言B.LscLgChcLpLocLicL2=L3分析句子的含義D.生成目標代碼逆波蘭式D.語法樹B.節(jié)省空間把編譯程序進行等價交換c.把中間代碼變換成依賴具體機器的目標代碼D.把匯編語言翻譯成機器語言二、填空題（本大題共5小題，每小題2分，共10分）】.編譯程序首先要識別出源程序中每個（單詞）,然后再分析每個（旬土）并翻譯其意義。編譯器常用的語法分析方法有（自底向上）和（自頂向下）兩種。通常把編譯過程分為分析前端與綜合后端兩大階段。詞法、語法和語義分析是對源程序的（分析）,中間代碼生成、代碼優(yōu)化與目標代碼的生成則是對源程序的（綜合）。程序設計語言的發(fā)展帶來了日漸多變的運行時存儲管理方案，主要分為兩大類，即（醫(yī)態(tài)存儲分配）方案和（動態(tài)存儲分配）方案。對編譯程序而言，輸入數(shù)據(jù)是（源程序）,輸出結果是（目標程序）。三、名詞解釋題（共5小題，每小題4分，共20分）詞法分析詞法分析的主要任務是從左向右掃描每行源程序的符號，按照詞法規(guī)則從構成源程序的字符串中識別出一個個具有獨立意義的最小語法單位，并轉換成統(tǒng)一的內部表示（token）,送給語法分析程序。LL⑴文法若文法的任何兩個產生式力ta/0都滿足下面兩個條件:（1） FIRST（a）cFIRST（0）二（2） 若,那么FIRST（a）cFOLLOW（力）二?。我們把滿足這兩個條件的文法叫做LL（1）文法，其中的第一個L代表從左向右掃描綸入，第二個L表示產生最左推導，1代表在決定分析器的每步動作時向前看一個輸入符號。除了沒有公共左因子外，LL（1）文法還有一些明顯的性質，它不是二義的，也不含左遞歸。語法樹句子的樹結構表示法稱為語法樹（語法分析樹或語法推導樹）。給定文法（二2上，V：,P,S）,對于G的任何句型都能構造與之關聯(lián)的語法樹。這棵磺有〒列特征：(】)根節(jié)點的標記是開始符號s。每個節(jié)點的標記都是V中的一個符號。若一棵子樹的根節(jié)點為A,且其所有直接子孫的標記從左向右的排列次序為那么ATA]Aj?Ag_—定是P中的一條產生式。若一標記為A的節(jié)點至少有一個除它以外的子孫，則若樹的所有葉節(jié)點上的標記從左到右排列為字符串w,則w是文法G的句型；若w中僅含終結符號，則w為文法G所產生的句子。LR(O)分析器所謂LR(O)分析，是指從左至右掃描和自底向上的語法分析，旦在分析的每一步，只須根據(jù)分析棧當前已移進和歸約出的全部文法符號，并至多再向前查看0個輸入符號，就能確定相對于某一產生式左部符號的句柄是否已在分析棧的頂部形成，從而也就可以確定當前所應采取的分析動作(是移進還是按某一產生式進行歸約等)。語言和文法文法就是語言結構的定義和描述，是有窮非空的產生式集合。文法G定義為四元組的形式：G=(V幽V],P,S)其中：V’是非空有窮集合，稱為非終結符號集合；V]是非空有窮集合，稱為終結符號集合；P是產生式的集合(非空)；s是開始符號(或識別符號)。這里，二0,S三V二0UV],稱為文法G的字母表，它是出現(xiàn)文法產生式中的一切符號的集合。文法G所描述的語言用L(G)表示，它由文法G所產生的全部句子組成，即L(G)二｛x|Sn%其中S為文法開始符號，且簡單的說，文法描述的語言是該文法一切句子的集合。四、簡答題(共4小題，每小題5分，共20分)編譯程序和高級語言有什么區(qū)別？用匯編語言或高級語言編寫的程序，必須先送入計算機，經過轉換成用機器語言表示的目標程序(這個過程即編譯)，才能由計算機執(zhí)行。執(zhí)行轉換過程的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉

換過的叫目標程序，也就是機器語言。編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，按照一一對應的關系，轉換成用機器語言表示的程序。解釋型編譯程序將高級語言程序的一個語句，先解釋成為一組機器語言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以進行人和計算機的”對話”，隨時可以修改高級語言的程序。BASIC語言就是解釋型高級語言。編譯型編譯程序將級語言編寫的程序，一次就會部翻譯成機器語言表示的程序，而且過程進行很快，在過程中，不能進行人機對話修改。FORTRAN語言就是編譯型高級語言。編譯程序的工作分為那幾個階段？詞法分析、語法分析和語義分析是對源程序進行的分析（稱為編譯程序的前端），而中間代碼生成、代碼優(yōu)化和代碼生成三個階段合稱為對源程序進行綜合（稱為編譯程序的后端），它們從源程序的中間表示建立起和源程序等價的目標程序。簡述自下而上的分析方法。所謂自下而上分析法就是從輸入串開始，逐步進行“歸約”，直至歸約到文法的開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到根節(jié)點。簡述代碼優(yōu)化的目的和意義。代碼優(yōu)化是盡量生成妝子”的代碼的編譯階段。也就是要對程序代碼進行一種等價變換，在保證變換前后代碼執(zhí)行結果相同的前提下，盡量使目標程序運行時所需要的時間短，同時所占用的存儲空間少。五、綜合應用題（共3小題，每小題】0分，共30分）證明下述文法G:SToSbS|aS|d是二義性文法。解：一個文法，如果存在某個句子有不只一棵語法分析樹與之對應，那么稱這個文法是二義性文法。句子oodbd有兩棵語法樹。如下圖：⑴⑵由此可知，SToSbS|oS|d定義的文法是二義性文法。對于文法G⑸：Stab,ATAQlbB,B^a|Sb求句型baSb的全部短語、直接短語和句柄？句型baSb的語法樹如圖五⑵所示。圖五(2)句型baSb的的語法擁解：boSb為句型baSb的相對于S的短語，bo為句型boSb的相對于A的短語，S