編譯原理》常見題型一、填空題編譯程序的工作過程一般可以劃分為 詞法分析，語法分析 ，中間代碼生成 ，.代碼優(yōu)化(可省_，目標(biāo)代碼生成 等幾個(gè)基本階段。若源程序是用高級語言編寫的，目標(biāo)程序是機(jī)器語言程序或匯編程序—，則其翻譯程序稱為編譯程序.編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼 5.對編譯程序而言，輸入數(shù)據(jù)是源程序 ，輸出結(jié)果是目標(biāo)程序若源程序是用高級語言編寫的，目標(biāo)程序是機(jī)器語言程序或匯編程序，則其翻譯程序稱TOC\o"1-5"\h\z為編譯程序 。一個(gè)典型的編譯程序中，不僅包括詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括—表格處理和.出錯(cuò)處理—。其中，詞法分析器用于識別單詞 。10.一個(gè)上下文無關(guān)文法所含四個(gè)組成部分是一組終結(jié)符號 、一組非終結(jié)符號—、一個(gè)開始符號、一組產(chǎn)生式, °產(chǎn)生式是用于定義語法成分 的一種書寫規(guī)則。設(shè)G[S]是給定文法，則由文法G所定義的語言L(G)可描述為：：L(G)={x|S=>*x.x￡\o"CurrentDocument"VT*} °*設(shè)G是一個(gè)給定的文法，S是文法的開始符號，如果S二x(其中x^V*)，則稱x是文法的一個(gè)，句型_°*設(shè)G是一個(gè)給定的文法，S是文法的開始符號，如果S二x(其中xWVT*)，則稱x是文法的一個(gè)句子—°掃描器的任務(wù)是從源程序中識別出一個(gè)個(gè)單詞符號 °語法分析最常用的兩類方法是自上而下—和自下而上 分析法。語法分析的任務(wù)是識別給定的終結(jié)符串是否為給定文法的句子_°遞歸下降法不允許任一非終結(jié)符是直接_左_遞歸的。自頂向下的語法分析方法的關(guān)鍵是如何選擇候選式 的問題。遞歸下降分析法是自.頂向下—分析方法。自頂向下的語法分析方法的基本思想是：從文法的開始符號開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的句子 ，使之與給定的輸入串匹配°自底向上的語法分析方法的基本思想是：從給定的終結(jié)符串開始，根據(jù)文法的規(guī)則一步TOC\o"1-5"\h\z一步的向上進(jìn)行直接歸約—，試圖.歸約—到文法的 開始符號 °自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行直接歸約—，力求歸約—到文法的開始符號 °26.在LR(0)分析法的名稱中，L的含義是自左向右的掃描輸入串 ，R的含義是最左歸約，0的含義是向貌似句柄的符號串后查看0個(gè)輸入符號 °終結(jié)符只有綜合屬性 ，它們由詞法分析器提供。在使用高級語言編程時(shí)，首先可通過編譯程序發(fā)現(xiàn)源程序的全部A(語法」錯(cuò)誤和B(語義)部分錯(cuò)誤.34?一個(gè)句型中的最左簡單短語稱為該句型的—句柄—。36．從功能上說，程序語言的語句大體可分為_執(zhí)行性 語句和說明性 語句兩大類。?語法分析是依據(jù)語言的—語法—規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的_語義—規(guī)進(jìn)行的。TOC\o"1-5"\h\z?語法分析器的輸入是—單詞符號 ，其輸出是_語法單位 。?逆波蘭式ab+c+d*e-所表達(dá)的表達(dá)式為__(a+b+c)*d-c_。?計(jì)算機(jī)執(zhí)行用高級語言編寫的程序主要有兩種途徑：—解釋_和_編譯_。?自上而下分析法采用—移進(jìn)—、歸約、錯(cuò)誤處理、接受—等四種操作。?一個(gè)LR分析器包括兩部分：一個(gè)總控程序和—一張分析表 。?后綴式abc-/所代表的表達(dá)式是a/(b-c) 。46?語法分析基于_上下文無關(guān)—文法進(jìn)行，即識別的是該類文法的句子。語法分析的有效工具是_語法樹___。?語義分析階段所生成的與源程序等價(jià)的中間表示形式可以有_逆波蘭_、四元式表示—與_三元式表示 等。自頂向下語法分析會遇到的主要問題有左遞歸和回溯—。已知文法G[E]:E—TIE+T;T—F|T*F;F—(E)|i該文法的開始符號是 ，終結(jié)符號集合VT是 ，非終結(jié)符號結(jié)合V是 。二、單選題?一個(gè)編譯程序中，不僅包含詞法分析，(A)，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分。A?語法分析 B?文法分析 C?語言分析D?解釋分析?語法分析器則可以發(fā)現(xiàn)源程序中的(D)。A?語義錯(cuò)誤 B?語法和語義錯(cuò)誤 C?錯(cuò)誤并校正D?語法錯(cuò)誤?解釋程序處理語言時(shí)，大多數(shù)采用的是(B)B方法。A?源程序命令被逐個(gè)直接解釋執(zhí)行B?先將源程序轉(zhuǎn)化為中間代碼，再解釋執(zhí)行C?先將源程序解釋轉(zhuǎn)化為目標(biāo)程序，再執(zhí)行D?以上方法都可以?編譯程序是一種(B)°A?匯編程序 B?翻譯程序 C?解釋程序 D?目標(biāo)程序5?通常一個(gè)編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括(C)°A?模擬執(zhí)行器 B?解釋器 C?表格處理和出錯(cuò)處理 D?符號執(zhí)行器?一個(gè)句型中的最左(B)稱為該句型的句柄。A?短語 B?簡單短語 C?素短語 D?終結(jié)符號?文法G[E]:E—T|E+TT—F|T*FF—a|(E)該文法句型E+F*(E+T)的簡單短語是下列符號串中的(B)°①(E+T) ②E+T ③F ④F*(E+T)A?①和③B?②和③C?③和④D?③?詞法分析器用于識別(C)°A?句子 B?句型 C?單詞 D?產(chǎn)生式?在自底向上的語法分析方法中，分析的關(guān)鍵是(D)°A?尋找句柄 B?尋找句型 C?消除遞歸 D?選擇候選式?文法G產(chǎn)生的(D)的全體是該文法描述的語言。A?句型B?終結(jié)符集C?非終結(jié)符集 D?句子?若文法G定義的語言是無限集，則文法必然是(A)°A?遞歸的 B?前后文無關(guān)的 C?二義性的 D?無二義性的?四種形式語言文法中，1型文法又稱為(C)C文法。A?短語結(jié)構(gòu)文法 B?前后文無關(guān)文法 C?前后文有關(guān)文法D?正規(guī)文法?一個(gè)文法所描述的語言是(A)°A?唯一的 B?不唯一的 C?可能唯一，好可能不唯一 D?都不對?(B)和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。A?語法分析 B?中間代碼生成 C?詞法分析 D?目標(biāo)代碼生成?(B)是兩類程序語言處理程序。A?高級語言程序和低級語言程序 B?解釋程序和編譯程序C?編譯程序和操作系統(tǒng) D?系統(tǒng)程序和應(yīng)用程序16.—個(gè)上下文無關(guān)文法G包括四個(gè)組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個(gè)開始符號，以及一組(D)°A?句子 B?句型 C?單詞D?產(chǎn)生式?文法分為四種類型，即0型、1型、2型、3型。其中2型文法是(D)°A?短語文法 B?正則文法 C?上下文有關(guān)文法 D?上下文無關(guān)文法?文法G所描述的語言是(C)的集合。A?文法G的字母表V中所有符號組成的符號串B?文法G的字母表V的閉包V*中的所有符號串C?由文法的開始符號推出的所有終結(jié)符串D?由文法的開始符號推出的所有符號串?文法分為四種類型，即0型、1型、2型、3型。其中0型文法是(A)°A?短語文法 B?正則文法 C?上下文有關(guān)文法 D?上下文無關(guān)文法?(A是一種典型的解釋型語言。A?BASICB?CC?FORTRAND?PASCAL?與編譯系統(tǒng)相比，解釋系統(tǒng)(D)°A?比較簡單，可移植性好，執(zhí)行速度快B?比較復(fù)雜，可移植性好，執(zhí)行速度快C?比較簡單，可移植性差，執(zhí)行速度慢D?比較簡單，可移植性好，執(zhí)行速度慢?用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫(B)°A?源程序 B?目標(biāo)程序C?連接程序 D?解釋程序?編寫一個(gè)計(jì)算機(jī)高級語言的源程序后，到正式上機(jī)運(yùn)行之前，一般要經(jīng)過(B)這幾步：(1)編輯 (2)編譯 (3)連接 (4)運(yùn)行A?⑴⑵⑶⑷B?⑴⑵⑶C?⑴⑶D?⑴⑷?把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由(B)完成的。A?編譯器 B?匯編器 C?解釋器 D?預(yù)處理器?詞法分析器的輸出結(jié)果是(C)°A?單詞的種別編碼 B?單詞在符號表中的位置C?單詞的種別編碼和自身值 D?單詞自身值?正規(guī)式M1和M2等價(jià)是指(C)°A?M1和M2的狀態(tài)數(shù)相等 B?M1和M2的有向邊條數(shù)相等C?M1和M2所識別的語言集相等 D?M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等?文法G：S—xSx|y所識別的語言是(C)°A?xyxB?(xyx)*C?xnyxn(n0)D?x*yx*?如果文法G是無二義的，則它的任何句子a(A)°A?最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B?最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C?最左推導(dǎo)和最右推導(dǎo)必定相同D?可能存在兩個(gè)不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同?構(gòu)造編譯程序應(yīng)掌握(D)°A?源程序 B?目標(biāo)語言 C?編譯方法 D?以上三項(xiàng)都是

30?四元式之間的聯(lián)系是通過(B)實(shí)現(xiàn)的。?指示器 B?臨時(shí)變量 C?符號表表達(dá)式GAV30?四元式之間的聯(lián)系是通過(B)實(shí)現(xiàn)的。?指示器 B?臨時(shí)變量 C?符號表表達(dá)式GAVB)A(CVD)的逆波蘭表示為(B)?！窤BVACDV B?AqBVCDVA C?ABV^CDVA編譯程序是對(D)。匯編程序的翻譯 B?高級語言程序的解釋執(zhí)行機(jī)器語言的執(zhí)行 D?高級語言的翻譯采用自上而下分析，必須(C)。消除左遞歸 B?消除右遞歸 C?消除回溯在規(guī)范歸約中，用()B來刻畫可歸約串。直接短語 B?句柄間接三元式表示法的優(yōu)點(diǎn)為(A)。采用間接碼表，便于優(yōu)化處理便于優(yōu)化處理，節(jié)省存儲空間D?程序變量31．33．C34．35．36．C?最左素短語C?在目標(biāo)代碼生成階段，符號表用(D)。A?目標(biāo)代碼生成 B?語義檢查?下面關(guān)于解釋程序的描述正確的」B(1)解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼D-AqBVACDVD?提取公共左因子D?素短語B?節(jié)省存儲空間，不便于表的修改D?節(jié)省存儲空間，不便于優(yōu)化處理C?語法檢查 D?地址分配解釋程序適用于COBOL和FORTRAN語言解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的A.(1)(2) B.(1)C.(1)(2)(3) D.(2)(3)解釋程序處理語言時(shí)，大多數(shù)采用的是方法.源程序命令被逐個(gè)直接解釋執(zhí)行先將源程序轉(zhuǎn)化為中間代碼，再解釋執(zhí)行先將源程序解釋轉(zhuǎn)化為目標(biāo)程序，在執(zhí)行以上方法都可以用不同語言編寫的程序產(chǎn)生 后，可用 連接在一起生成機(jī)器可執(zhí)行的程序.在機(jī)器中真正執(zhí)行的是 上面三空格對應(yīng)的選項(xiàng)是：A a.源程序 b.目標(biāo)程序 c.函數(shù) d.過程e.機(jī)器指令代碼 f.模塊 g.連接程序 h.程序庫A.b、g、eB.b、c、eC.e、g、f D.e、c、f由于受到具體機(jī)器主存容量的限制，編譯程序幾個(gè)不同階段的工作往往被組合 ，諸階段的工作往往是進(jìn)行的.上面兩空格對應(yīng)的選項(xiàng)是：諸階段的工作往往是進(jìn)行的.上面兩空格對應(yīng)的選項(xiàng)是：.丄a.過程a.過程b.程序c.批量d.遍e.順序f.并行g(shù).成批h.穿插A.d和hB.d和eC.a和hD.a和e編譯過程中，語法分析器的任務(wù)就分析單詞是怎樣構(gòu)成的編譯過程中，語法分析器的任務(wù)就分析單詞是怎樣構(gòu)成的分析單詞串是如何構(gòu)成語句和說明分析語句和說明是如何構(gòu)成程序的(4)分析程序的結(jié)構(gòu)A.(2)(3)B.(2)(3)(4)C.(1)(2)(3) D.(1)(2)(3)(4)編譯程序必須完成的工作有 A(1)詞法分析 (2)語法分析 (3)語義分析代碼生成 (5)中間代碼生成(6)代碼優(yōu)化A.(1)(2)(3)(4) B.(1)(2)(3)(4)(5)C.(1)(2)(3)(4)(5)(6) D.(1)(2)(3)(4)(6)?按邏輯上劃分，編譯程序第二步工作—C_。A.語義分析 B.詞法分析 C.語法分析D.代碼優(yōu)化45?已知語言L={xnyyn|n>=1}，則下述文法中，D可以產(chǎn)生語言L。Al.Z—xZy|xAy|y Bl.A—xAyA—xAy|x 2.A—XCl.Z—AyB Dl.Z—xAyA—xA|x 2.A—xAy|yB—yB|y46?喬姆斯基(Chomsky)把文法分為四種類型，即0型、1型、2型、3型。其中3型文法是 B_—A.短語文法 B.正則文法C.上下文有關(guān)文法D.上下文無關(guān)文法?設(shè)G是一個(gè)給定的文法，S是文法的開始符號，如果S禺x(其中x^V*)，則稱x是文法G的一個(gè)_B °A.候選式B.句型 C.單詞 D.產(chǎn)生式?若一個(gè)文法是遞歸的，則它所產(chǎn)生的語言的句子—A—°A.是無窮多個(gè)B.是有窮多個(gè)C.是可枚舉的 D.個(gè)數(shù)是常量?文法的二義性和語言的二義性是兩個(gè) —的概念。A不同 B相同 C無法判斷D不存在在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是B °A.非終結(jié)符集B.終結(jié)符集 C.字母表 D.狀態(tài)集編譯程序中語法分析器接收—A_為單位的輸入。A.單詞 B.表達(dá)式 C.產(chǎn)生式D.句子在LR分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型 C 的DFA狀態(tài)。A.句柄 B.前綴 C.活前綴 D.LR(0)項(xiàng)目三、是非題（下列各題，你認(rèn)為正確的，請?jiān)陬}干的括號內(nèi)打“/”，錯(cuò)的打“X”。）1．計(jì)算機(jī)高級語言翻譯成低級語言只有解釋一種方式。（X）2．在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。（X）3．甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。（X）4．“用高級語言書寫的源程序都必須通過編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說法。（X）TOC\o"1-5"\h\z5?正則文法其產(chǎn)生式為ATa，ATBb，A，BwVN，a、bwVT。 （V）6．產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。 （X）7?解釋程序適用于COBOL和FORTRAN語言。 （X）8．正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 （V）?如果一個(gè)文法存在某個(gè)句子對應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的。（V）?編譯程序是對高級語言程序的解釋執(zhí)行。 （X）?一個(gè)有限狀態(tài)自動機(jī)中，有且僅有一個(gè)唯一的終態(tài)。 （X）12?語法分析時(shí)必須先消除文法中的左遞歸。 （X）?兩個(gè)正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價(jià)。 （V）?設(shè)r和s分別是正規(guī)式，則有L（r|s）=L（r）L（s）。 （X）?確定的自動機(jī)以及不確定的自動機(jī)都能正確地識別正規(guī)集。 （V）?詞法分析作為單獨(dú)的一遍來處理較好。 （X）?構(gòu)造LR分析器的任務(wù)就是產(chǎn)生LR分析表。 （V）?編譯程序與具體的機(jī)器有關(guān)，與具體的語言無關(guān)。 （X）?每個(gè)文法都能改寫為LL（1）文法。 （X）?遞歸下降法允許任一非終結(jié)符是直接左遞歸的。 （V）?遞歸下降分析法是自頂向下分析方法。 （V）?一個(gè)LL（l）文法一定是無二義的。 （V）?算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。 （X）24?自底而上語法分析方法的主要問題是候選式的選擇。 （X）?LR分析方法是自頂向下語法分析方法。 （X）?簡單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。 （X）?若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄（X）?一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。 （V）?在SLR（1）分析法的名稱中，S的含義是簡單的。 （V）?綜合屬性是用于“自上而下”傳遞信息。 （X）?一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。 （V）?LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。（V）?規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。 （V）?LR分析技術(shù)無法適用二義文法。 （X）?逆波蘭表示法表示表達(dá)式時(shí)無須使用括號。 （V）?逆波蘭法表示的表達(dá)式亦稱后綴式。 （V）38?在程序中標(biāo)識符的出現(xiàn)僅為使用性的。 （X）設(shè)工為｛a，b｝，則a，ba，｛E｝，①都是工上的正規(guī)式。(X)對于上下文無關(guān)文法G[S]，若S=aAB=a^Y則A—Y一定是一條產(chǎn)生式規(guī)則，TOC\o"1-5"\h\z其中a,B,Y丘(VTVVN)*。 (X)對于逆波蘭后綴式，無論從哪頭開始分析均可得到唯一正確的分解(V)LR(0)分析法是一種規(guī)范歸約法。 (V)算符優(yōu)先分析法只能用來分析算符優(yōu)先文法。(V)解釋程序和編譯程序一樣，生成目標(biāo)代碼。 (X)編譯程序生成的目標(biāo)代碼只能是機(jī)器語言。 (X)等價(jià)文法是指兩個(gè)文法完全相同。 (X)對于字母表工上的任一NFAM'，必存在工上與NFAM'等價(jià)的DFAM°(V)每個(gè)文法都能改寫為LL(1)文法。(X)不存在正規(guī)文法能產(chǎn)生語言：L=｛anbn|n>=l｝(V)四、簡答題1、什么是句子？什么是語言?答：設(shè)G是一個(gè)給定的文法，S是文法的開始符號，如果S=>*x(其中x^Vt*)，則稱x是文法的一個(gè)句子。設(shè)G[S]是給定文法則由文法G所定義的語言L(G)可描述為L(G)={x|S=>*x,x^VT*}2、 已知文法G[E]為：E—TIE+TIE-TT—F|T*F|T/FF—(E)|i該文法的開始符號(識別符號)是什么？請給出該文法的終結(jié)符號集合VT和非終結(jié)符號集合VN。找出句型T+T*F+i的所有短語、簡單短語和句柄。答：①該文法的開始符號(識別符號)是E。該文法的終結(jié)符號集合VT={+、-、*、/、(、)、i}。非終結(jié)符號集合VN={E、T、F}。句型T+T*F+I的句柄為第一個(gè)T。3、 已知文法G[S]為：S—dABA—aAIaB—Bb|eG[S]產(chǎn)生的語言是什么？G[S]能否改寫為等價(jià)的正規(guī)文法？答：①G[S]產(chǎn)生的語言是L(G[S])={da"nbF|n21,m±0}。②G[S]能改寫為等價(jià)的正規(guī)文法，其改寫后的等價(jià)的正規(guī)文法G[S/]為：S/—dAA—aAIaBIaB—bBIb5、證明下面文法G[N]是二義性文法。G[N]:N—SE|ES—SD|DE—0|2|10D—0|1|27、簡述DFA與NFA有何區(qū)別？

答：主要區(qū)別在于，1.DFA沒有8轉(zhuǎn)換；2.DFA的狀態(tài)轉(zhuǎn)換函數(shù)是單值映射，即當(dāng)前狀態(tài)輸入一個(gè)字符后轉(zhuǎn)換到下一個(gè)狀態(tài)，而NFA的狀態(tài)轉(zhuǎn)換函數(shù)是非單值映射，也就是說當(dāng)前狀態(tài)輸入一個(gè)字符后可以轉(zhuǎn)換到下面N個(gè)狀態(tài)。8、 試給出非確定自動機(jī)的定義。答：一個(gè)非確定的有窮自動機(jī)(NFA)