編譯原理考前練習(xí).doc

一、填空題:1.編譯程序的工作過程一般可以劃分為 詞法分析,語法分析,語義分析，中間代碼生成,代碼優(yōu)化 等幾個基本階段,同時還會伴有 表格處理 和 出錯處理 .2.若源程序是用高級語言編寫的,目標(biāo)程序是 機(jī)器語言程序或匯編程序 ,則其翻譯程序稱為編譯程序.3.編譯方式與解釋方式的根本區(qū)別在于 是否生成目標(biāo)代碼 .4.翻譯程序是這樣一種程序,它能夠?qū)?用甲語言書寫的程序 轉(zhuǎn)換成與其等價的 用乙語言書寫的程序 .5.對編譯程序而言,輸入數(shù)據(jù)是 源程序 ,輸出結(jié)果是 目標(biāo)程序 .6.如果編譯程序生成的目標(biāo)程序是機(jī)器代碼程序,則源程序的執(zhí)行分為兩大階段: 編譯階段 和 運(yùn)行階段 .如果編譯程序生成的目標(biāo)程序是匯編語言程序,則源程序的執(zhí)行分為三個階段: 編譯階段 , 匯編階段 和 運(yùn)行階段 .7.若源程序是用高級語言編寫的，目標(biāo)程序是機(jī)器語言程序或匯編程序 ，則其翻譯程序稱為 編譯程序 。8.所謂最右推導(dǎo)是指： 任何一步都是代換句型中最右邊非終結(jié)符的推導(dǎo) 。9.一個上下文無關(guān)文法所含四個組成部分是 一組終結(jié)符號、一組非終結(jié)符號、一個開始符號、一組產(chǎn)生式 。10.產(chǎn)生式是用于定義語法成分的一種書寫規(guī)則，它指明了 終結(jié)符 和 非終結(jié)符 組成串的方式。11.設(shè)G是一個給定的文法，S是文法的開始符號，如果Sx（其中xV*），則稱x是文法的一個句型 。12.設(shè)G是一個給定的文法，S是文法的開始符號，如果Sx(其中xVT*),則稱x是文法的一個句子。13.掃描器的任務(wù)是從源程序中識別出一個個 單詞符號 。14.語法分析最常用的兩類方法是 自上而下 和 自下而上 分析法。15.語法分析的任務(wù)是識別給定的終極符串是否為給定文法的句子。16.遞歸下降法不允許任一非終極符是直接 左 遞歸的。17.自頂向下的語法分析過程本質(zhì)上是一種 試探 的過程，是反復(fù)使用不同的產(chǎn)生式謀求匹配輸入串的過程。18.遞歸下降分析法是自 頂向下 分析方法。19.自頂向下的語法分析方法的基本思想是：從文法的 開始符號 開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的 句子 ，使之與給定的輸入串匹配。20.自底向上的語法分析方法的基本思想是：從給定的終極符串開始，根據(jù)文法的規(guī)則一步一步的向上進(jìn)行歸約，試圖歸約到文法的 開始符號 。21.簡單優(yōu)先方法每次歸約當(dāng)前句型的 句柄 ，是不斷移進(jìn)輸入符號，直到符號棧頂出現(xiàn) 可歸約串 的尾，再向前找到 可歸約串 的頭，然后歸約。22.在SLR（1）分析法的名稱中，S的含義是 簡單的，L的含義是 自左向右的掃描輸入串 ，R的含義是 構(gòu)成最右歸約的逆 ，1 的含義是 決定分析動作時向前搜索1個符號 。23.代碼優(yōu)化的主要目標(biāo)是如何提高 目標(biāo)程序的運(yùn)行速度 和如何減少 目標(biāo)程序運(yùn)行時所需的空間 。二、單選題:1.一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個部分，還應(yīng)包括 (1)c .其中, (2)b 和代碼優(yōu)化部分不是每個編譯程序都必需的.詞法分析器用于識別 (3)c ,語法分析器則可以發(fā)現(xiàn)源程序中的 (4)d . (1) a.模擬執(zhí)行器 b.解釋器 c.表格處理和出錯處理 d.符號執(zhí)行器 (2) a.語法分析 b.中間代碼生成 c.詞法分析 d.目標(biāo)代碼生成 (3) a.字符串 b.語句 c.單詞 d.標(biāo)識符 (4) a.語義錯誤 b.語法和語義錯誤 c.錯誤并校正 d.語法錯誤2.程序語言的語言處理程序是一種 (1)a . (2)b 是兩類程序語言處理程序,他們的主要區(qū)別在于 (3)d . (1) a.系統(tǒng)軟件 b.應(yīng)用軟件 c.實(shí)時系統(tǒng) d.分布式系統(tǒng) (2) a.高級語言程序和低級語言程序 b.解釋程序和編譯程序 c.編譯程序和操作系統(tǒng) d.系統(tǒng)程序和應(yīng)用程序 (3) a.單用戶與多用戶的差別 b.對用戶程序的查錯能力c.機(jī)器執(zhí)行效率 d.是否生成目標(biāo)代碼3.匯編程序是將 a 翻譯成 b ,編譯程序是將 c 翻譯成 d .a.匯編語言程序 b.機(jī)器語言程序 c.高級語言程序d. a 或者 b e. a 或者 c f. b 或者 c4.下面關(guān)于解釋程序的描述正確的是 b . (1) 解釋程序的特點(diǎn)是處理程序時不產(chǎn)生目標(biāo)代碼 (2) 解釋程序適用于COBOL 和 FORTRAN 語言 (3) 解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的 a. (1)(2) b. (1) c. (1)(2)(3) d.(2)(3)5.高級語言的語言處理程序分為解釋程序和編譯程序兩種.編譯程序有五個階段，而解釋程序通常缺少 (1)e 和 (1)b .其中， (1)e 的目的是使最后階段產(chǎn)生的目標(biāo)代碼更為高效. 與編譯系統(tǒng)相比，解釋系統(tǒng) (2)d .解釋程序處理語言時,大多數(shù)采用的是 (3)b 方法. (4)a 就是一種典型的解釋型語言. (1): a. 中間代碼生成 b.目標(biāo)代碼生成 c.詞法分析 d.語法分析 e.代碼優(yōu)化 (2): a.比較簡單,可移植性好,執(zhí)行速度快 b.比較復(fù)雜,可移植性好,執(zhí)行速度快 c.比較簡單,可移植性差,執(zhí)行速度慢 d.比較簡單,可移植性好,執(zhí)行速度慢 (3): a.源程序命令被逐個直接解釋執(zhí)行 b.先將源程序轉(zhuǎn)化為中間代碼,再解釋執(zhí)行c.先將源程序解釋轉(zhuǎn)化為目標(biāo)程序,在執(zhí)行 d.以上方法都可以 (4) : a. BASIC b. C c. FORTRAN d. PASCAL6.用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫 b .用不同語言編寫的程序產(chǎn)生 b 后,可用 g 連接在一起生成機(jī)器可執(zhí)行的程序.在機(jī)器中真正執(zhí)行的是 e .a. 源程序 b. 目標(biāo)程序 c. 函數(shù) d. 過程 e. 機(jī)器指令代碼 f. 模塊 g. 連接程序 h.程序庫7.要在某一臺機(jī)器上為某種語言構(gòu)造一個編譯程序,必須掌握下述三方面的內(nèi)容: c , d , f .a. 匯編語言 b. 高級語言 c. 源語言 d. 目標(biāo)語言e. 程序設(shè)計(jì)方法 f. 編譯方法 g. 測試方法 h. 機(jī)器語言8.由于受到具體機(jī)器主存容量的限制,編譯程序幾個不同階段的活動往往被組合成在一起，叫作 (1)d ,諸階段的工作往往是 (2)d 進(jìn)行的. (1) a. 過程 b. 程序 c. 批量 d.遍 (2) a. 順序 b. 并行 c. 成批 d.穿插9.編譯程序與具體的機(jī)器 a , 與具體的語言 a .a. 有關(guān) b.無關(guān)10.編譯過程中,語法分析器的任務(wù)就是 b . (1) 分析單詞是怎樣構(gòu)成的 (2) 分析單詞串是如何構(gòu)成語句和說明的 (3) 分析語句和說明是如何構(gòu)成程序的 (4) 分析程序的結(jié)構(gòu)a. (2)(3) b. (2)(3)(4) c. (1)(2)(3) d.(1)(2)(3)(4)11.編寫一個計(jì)算機(jī)高級語言的源程序后,到正式上機(jī)運(yùn)行之前，一般要經(jīng)過 b 這幾步. (1) 編輯 (2) 編譯 (3) 連接 (4) 運(yùn)行a. (1)(2)(3)(4) b. (1)(2)(3) c. (1)(3) d.(1)(4)12.編譯程序必須完成的工作有 a . (1) 詞法分析 (2) 語法分析 (3) 語義分析 (4) 代碼生成 (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) e. (1)(2)(3)(5)(6)13.“用高級語言書寫的源程序都必須通過編譯,產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說法 a .a. 不正確 b.正確14.把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由 b 完成的.a. 編譯器 b. 匯編器 c. 解釋器 d. 預(yù)處理器15.編譯程序生成的目標(biāo)程序 b 是機(jī)器語言的程序.a. 一定 b. 不一定16.編譯程序生成的目標(biāo)程序 b 是可執(zhí)行的程序.a. 一定 b. 不一定17編譯程序是一種 B 。A. 匯編程序 B. 翻譯程序 C. 解釋程序 D. 目標(biāo)程序18按邏輯上劃分，編譯程序第二步工作是 C 。A. 語義分析 B. 詞法分析 C. 語法分析 D. 代碼優(yōu)化19通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個部分，還應(yīng)包括 C 。A.模擬執(zhí)行器 B.解釋器 C.表格處理和出錯處理 D.符號執(zhí)行器20文法G所描述的語言是 C 的集合。A.文法G的字母表V中所有符號組成的符號串B.文法G的字母表V的閉包V*中的所有符號串C.由文法的開始符號推出的所有終極符串D.由文法的開始符號推出的所有符號串21.文法GN=（b，N，B，N，NbbB，BbN），該文法所描述的語言是 C 。A. L(GN)=bii0 B. L(GN)=b2ii0C. L(GN)=b2i+1i0 D. L(GN)=b2i+1i122設(shè)G是一個給定的文法，S是文法的開始符號，如果Sx(其中xV*),則稱x是文法G的一個 B 。A. 候選式 B. 句型 C. 單詞 D. 產(chǎn)生式23一個上下文無關(guān)文法G包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組 D 。A. 句子 B. 句型 C. 單詞 D. 產(chǎn)生式24若一個文法是遞歸的，則它所產(chǎn)生的語言的句子 A 。A.是無窮多個 B.是有窮多個 C.是可枚舉的 D.個數(shù)是常量25詞法分析器用于識別 C 。A. 句子 B. 句型 C. 單詞 D. 產(chǎn)生式26.在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合均是 B 。A. 非終極符集 B.終極符集 C. 字母表 D. 狀態(tài)集27.編譯程序中語法分析器接收以 A 為單位的輸入。A. 單詞 B. 表達(dá)式 C. 產(chǎn)生式 D. 句子28在自頂向下的語法分析方法中，分析的關(guān)鍵是 D 。A. 尋找句柄 B. 尋找句型 C. 消除遞歸 D. 選擇候選式29. 在LR分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型 C 的DFA狀態(tài)。A.句柄 B. 前綴 C. 活前綴 D. LR(0)項(xiàng)目30一個確定的有限自動機(jī)是一個 D 。A二元組 B.三元組 C.四元組 D.五元組31.下述編譯方法中，屬于自下而上分析方法的有 A 。ASLR分析B.LL(1)分析 C.遞歸下降分析 D.預(yù)測分析32.文法G產(chǎn)生的 D 全體是該文法描述的語言A句型B.終結(jié)符集 C.非終結(jié)符集 D.句子33.編譯原理詞法分析器的輸出是一個二元組，該二元組的組成是 C A.單詞種類和參數(shù)B. 單詞數(shù)據(jù)種類和參數(shù)C詞法記號和屬性值 D.單詞種類和屬性值34.給定文法AAa|b下面的符號串可由其推出的是 C A.aab B.aaab C.baa D35給定文法, A Aa|b, 下面的符號串可由其推導(dǎo)出的是( C )Aan b|n0 Banb|n1 Cban |n0 Dban b|n1 36.高級語言編譯程序常用的語法分析方法中，LL分析法屬于哪種分析方法？(B )A自左至右 B自上而下 C自下而上 D自右至左三、是非題(下列各題，你認(rèn)為正確的，請?jiān)陬}干的括號內(nèi)打“ ”，錯的打“”。)1.計(jì)算機(jī)高級語言翻譯成低級語言只有解釋一種方式。 （）2.在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。 （）3.甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。 （）4.正則文法其產(chǎn)生式為Aa，ABb, A,BVN，a、bVT。 （）5.每個文法都能改寫為LL(1)文法。 （）6.遞歸下降法允許任一非終極符是直接左遞歸的。 （）7.自底而上語法分析方法的主要問題是候選式的選擇。 （）8.LR文法是自頂向下語法分析方法。 （）9.若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。 （）10.一個句型的句柄一定是文法某產(chǎn)生式的右部。 （）11.確定有限自動機(jī)比不確定有限自動機(jī)的功能更加強(qiáng)大。 （）12.SLR比規(guī)范LR的分析能力更加強(qiáng)大。 （）13LR分析中不允許出現(xiàn)左遞歸。 （）14語法分析處于編譯器編譯的第二階段。（）15. 一個文法句子一定是文法的句型（）16. 遞歸下降分析法和LL(K)分析法均是自下向上的語法分析文法( )17. 任何一個NFA總存在一個DFA與之等價（）18. 若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄()19. 二義性的解決辦法只有修改文法一種方法()20文法的開始符號不能出現(xiàn)在規(guī)則的右部()四、名詞解釋1. 掃描遍：指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。2.句柄是一個句型中和一個產(chǎn)生式右部匹配的子串，并且把它歸約成該產(chǎn)生式左部的非終結(jié)符代表了最右推導(dǎo)過程的逆過程中的一步。3什么是句子？ 什么是語言? 答：設(shè)G是一個給定的文法，S是文法的開始符號，如果Sx(其中xVT*),則稱x是文法的一個句子。設(shè)GS是給定文法，則由文法G所定義的語言L(G)可描述為： L(G)xSx,xVT*。4.試給出非確定自動機(jī)的定義。答：一個非確定的有窮自動機(jī)（NFA）M是一個五元組：M=（S，move，s0 ，F(xiàn)）。其中:1. 一個有限的狀態(tài)集合S；2. 是一個輸入符號集合，不在中；3. move是狀態(tài)轉(zhuǎn)換函數(shù)，是在S*S的子集的映射，即，move: S*2S ；表明在某狀態(tài)下對于某輸入符號可能有多個后繼狀態(tài)；4. s0是唯一的開始狀態(tài)； 5. F是接受（或終止）狀態(tài)集合，且F屬于S一個子集。5. 試給出確定自動機(jī)的定義。答：確定的有限自動機(jī)是不確定有限自動機(jī)的特殊情況。1任何狀態(tài)都沒有轉(zhuǎn)換，即任何狀態(tài)必須進(jìn)行輸入符號的匹配才能進(jìn)入下一個狀態(tài)。2對任何狀態(tài)s和任何輸入符號a，最多只有一條標(biāo)記為a的邊的離開s，即轉(zhuǎn)換函數(shù)move：S*S可以是一個部分函數(shù)。 6.自上而下分析思想是什么？答：從開始符出發(fā)導(dǎo)出句型并一個符號一個符號地與給定終結(jié)符串進(jìn)行匹配。如果全部匹配成功，則表示開始符號可推導(dǎo)出給定的終結(jié)符串。因此判定給定終結(jié)符號串是正確句子。7.自上而下的缺點(diǎn)是什么？答：在推導(dǎo)過程中，如果對文法不做限制。那么產(chǎn)生式的選擇成為無根據(jù)的，只好一一去試所有可能的產(chǎn)生式，直至成功為止。這種方法的致命弱點(diǎn)是不斷地回溯，大大影響速度。8.上下文無關(guān)文法的定義：一個上下文無法文法G是一個四元組（VT，VN,S,P），其中：1 VT是一個非空有限集合，其元素稱為終結(jié)符。2 VN是一個非空有限集合，其元素稱為非終結(jié)符，并有VTVN = 3S是一個非終結(jié)符，稱為開始符號。它定義的終結(jié)符串集就是文法定義的語言。4P是產(chǎn)生式的有限集合，每個產(chǎn)生式的形式是Aa，其實(shí)AVN a（VTVN）五、簡答題：1.已知文法GE為：ET|E+T|E-TTF|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的句柄為第一個T。2簡述DFA與NFA有何區(qū)別 ? 答：主要區(qū)別在于，1.DFA沒有轉(zhuǎn)換；2.DFA的狀態(tài)轉(zhuǎn)換函數(shù)是單值映射，即當(dāng)前狀態(tài)輸入一個字符后轉(zhuǎn)換到下一個狀態(tài)，而NFA的狀態(tài)轉(zhuǎn)換函數(shù)是非單值映射，也就是說當(dāng)前狀態(tài)輸入一個字符后可以轉(zhuǎn)換到下面N個狀態(tài)。3. 為正規(guī)式（a|b）*a(a|b) 構(gòu)造一個等價的DFA。解答：考試時需要有步驟，先構(gòu)造出NFA，然后再將NFA轉(zhuǎn)換為DFA，最后化簡。4. 給定下列自動機(jī)：把此自動機(jī)轉(zhuǎn)換為確定自動機(jī)DFA。其中：開始狀態(tài)：0 終止?fàn)顟B(tài)：2aaa0bbb12解答：（1）： 有狀態(tài)矩陣如圖： a b0 01 201 01 22 1 2 1 2a b 0 0,1 2 1 2 2 1 2從而可得DFA如圖：-02aaba101bbb極小化后：02babb1a5.消除下列文法GE的左遞歸。EE-TTTT/FFF( E )i解答：消除文法GE的左遞歸后得到：ETEE -TETFTT/FTF( E )i6.在LL(1)分析法中,LL分別代表什么含義?答:第一個L代表從左到右的掃描，第二個L代表每次進(jìn)行最左推導(dǎo)。7.滿足LL（1）文法的兩個條件是什么？答：一個上下文無關(guān)文法是LL(1)文法的充分必要條件是每個非終結(jié)符A的兩個不同產(chǎn)生式，A,A；滿足FIRST()FIRST()=。若，則FIRST() FOLLOW(A)= 。8.什么是文法的左遞歸？答：一個文法含有下列形式的產(chǎn)生式之一時：1)AA，AVN，V*2)AB，BA，A、BVN，、V* 則稱該文法是左遞歸的,其中1表示直接左遞歸，2表示間接左遞歸。9.遞歸下降法的主要思想是什么？答：對每個非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫出相應(yīng)語法分析子程序。因?yàn)槲姆ㄟf歸相應(yīng)子程序也遞歸，子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱此種方法稱為遞歸子程序法或遞歸下降法。10.自下而上分析法的原理是什么？答：在采用自左向右掃描，自底向上分析的前提下，該類分析方法是從輸入符號串入手，通過反復(fù)查找當(dāng)前句型的句柄，并使用文法的產(chǎn)生式把句柄歸約成相應(yīng)的非終極符來一步步地進(jìn)行分析的。最終把輸入串歸約成文法的開始符號，表明分析成功。11.給定文法和文法的句子，寫出最左推導(dǎo)、最右推導(dǎo)。見書本第40-41頁。6綜合題： 1. 文法GM是否是LL(1)文法，說明理由。GM：MTBTBa|BDb|eT|Dd|解：本題考查LL(1)方法對文法的要求，涉及到FIRST集、FOLLOW集的求法。首先求出文法的每一個非終結(jié)符號的FIRST集、FOLLOW集：FIRST(D)=FIRST(d)FIRST()=d, FIRST(B)=FIRST(Db)FIRST(eT)FIRST()=FIRST(db)FIRST(b)FIRST(eT)FIRST()=d，b，e，F(xiàn)IRST(T)=FIRST(Ba)FIRST()=d，b，e，a，F(xiàn)IRST(M)=FIRST(Tb)= d，b，e，a，F(xiàn)OLLOW(M)=#FOLLOW(B)=FOLLOW(M)FIRST(a)=a，#FOLLOW(T)=FOLLOW(B)FOLLOW(M) FOLLOW(B)=d，b，e，#，aFOLLOW(D)=FIRST(b)=b可以看出，對文法GM的產(chǎn)生式TBa|，有FIRST(Ba)FOLLOW(T)=d，b，e，ad，b，e，#，a=d，b，e，a僅此一條就會導(dǎo)致在自上而下的語法分析過程中出現(xiàn)回朔。所以文法GM不是LL(1)文法。2.設(shè)文法GS：SSbA|aABSbABc將該文法改寫成LL(1)文法。求文法的每一個非終結(jié)符號的FIRST集合和FOLLOW集合。構(gòu)造相應(yīng)的LL(1)分析表。解：本題考查“LL(1)文法”的概念及LL(1)分析表的構(gòu)造方法，涉及文法符號串的FIRST集，文法非終結(jié)符號的FOLLOW集的求法。 將該文法改寫成LL(1)文法。 因?yàn)镾SbA|aA有左遞歸，將其改寫為SaAbA 文法變?yōu)镚S：SaAbA BSb ABc 文法GS滿足LL(1)文法的條件 文法GS中每一個非終結(jié)符號的FIRST集合為FIRST(S)=aFIRST(A)=aFIRST(B)=a 文法GS中每一個非終結(jié)符號的FOLLOW集合為S為開始符號，且有產(chǎn)生式BSbFOLLOW(S)=#FIRST(b)=#，bSaAbAFOLLOW(A)=FIRST(bA)FOLLOWS=#，bABcFOLLOW(B)=FIRSTc=c 構(gòu)造相應(yīng)的LL(1)分析表FIRST(aAbA)=aMS，a=SaAbAFIRST(A)=aMA，a=BBcFIRST(B)=aMB，a=BSb 文法GS的分析表如表5.3所示。表5.3 文法GS的分析表abc#SSaAbAAABcBBSb3已知文法G是LL(1)文法，請構(gòu)造其分析表并給出輸入串a(chǎn)ade#的分析過程。G：AaCCABe|BdBBbB|求出每一個非終結(jié)符號的FIRST集和FOLLOW集：FIRST(A)=aFOLLOW(A)=FIRST(Be)#=#，dFIRST(B)=dFOLLOW(B)=FIRS