編譯原理模擬期末試題匯總6套含答案

1、編譯原理模擬試題一一、是非題（請?jiān)诶ㄌ杻?nèi)，正確的劃，錯誤的劃×）（每個2分，共20分）1計(jì)算機(jī)高級語言翻譯成低級語言只有解釋一種方式。(×)2在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。(×)3甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。 ( )4正則文法其產(chǎn)生式為 a->a ， a->bb,  a,bvn ， a 、 bvt 。 (×)5每個文法都能改寫為 ll(1) 文法。 ()6遞歸下降法允許任一非終極符是直接左遞歸的。 ()7算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。 (×

2、;)8自底而上語法分析方法的主要問題是候選式的選擇。 (×)9lr 法是自頂向下語法分析方法。 (×)10簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相同右部。 (×)二、選擇題(請?jiān)谇袄ㄌ杻?nèi)選擇最確切的一項(xiàng)作為答案劃一個勾，多劃按錯論)(每個4分，共40分)1 一個編譯程序中，不僅包含詞法分析，_，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個部分。a( ) 語法分析 b( )文法分析c( )語言分析d( )解釋分析2 詞法分析器用于識別_。  a( ) 字符串   b( )語句c( )單詞 d( )標(biāo)識符3 語法分析器則可以發(fā)現(xiàn)源程序中的_。a( ) 語

3、義錯誤   b( ) 語法和語義錯誤c( ) 錯誤并校正    d( ) 語法錯誤4 下面關(guān)于解釋程序的描述正確的是_。 (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 解釋程序處理語言時 , 大多數(shù)采用的是_方法。a( ) 源程序命令被逐個直接解釋執(zhí)行   b( ) 先將源程序轉(zhuǎn)化為中間代碼 , 再解釋執(zhí)行

4、c( ) 先將源程序解釋轉(zhuǎn)化為目標(biāo)程序 , 再執(zhí)行   d( ) 以上方法都可以6 編譯過程中 , 語法分析器的任務(wù)就是_。 (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)7 編譯程序是一種_。a. ( ) 匯編程序 b( ) 翻譯程序      

5、c( ) 解釋程序         d( ) 目標(biāo)程序8 文法 g 所描述的語言是_的集合。 a. ( ) 文法 g 的字母表 v 中所有符號組成的符號串b( ) 文法 g 的字母表 v 的閉包 v* 中的所有符號串c( ) 由文法的開始符號推出的所有終極符串d. ( ) 由文法的開始符號推出的所有符號串9 文法分為四種類型，即0型、1型、2型、3型。其中3型文法是_。a. ( ) 短語文法     b( ) 正則文法     c( ) 上下文有關(guān)文法 d( ) 上

6、下文無關(guān)文法10 一個上下文無關(guān)文法 g 包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組 _。a( ) 句子 b( ) 句型c( ) 單詞 d( ) 產(chǎn)生式三、填空題(每空1分，共10分)1編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義分析,中間代碼生成,代碼優(yōu)化等幾個基本階段,同時還會伴有_表格處理_和 _出錯處理_。 2若源程序是用高級語言編寫的,_目標(biāo)程序_是機(jī)器語言程序或匯編程序,則其翻譯程序稱為 _編譯程序_ 。3編譯方式與解釋方式的根本區(qū)別在于_是否生成目標(biāo)代碼_。4對編譯程序而言,輸入數(shù)據(jù)是_源程序_, 輸出結(jié)果是_目標(biāo)程序_。5產(chǎn)生式是

7、用于定義_語法成分_的一種書寫規(guī)則。 6語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。 四、簡答題（20分）1. 什么是句子？ 什么是語言 ? 答：(1)設(shè)g是一個給定的文法，s是文法的開始符號，如果s x(其中xvt*),則稱x是文法的一個句子。 (2)設(shè)gs是給定文法，則由文法g所定義的語言l(g)可描述為： l(g)xs x,xvt* 。(每個2分，共4分)答：(1)設(shè)g是一個給定的文法，s是文法的開始符號，如果s x(其中xvt*),則稱x是文法的一個句子。 (2)設(shè)gs是給定文法，則由文法g所定義的語言l(g)可描述為： l(g)xs x,xvt* 。 2. 寫一文法，

8、使其語言是偶正整數(shù)的集合,要求：    (1)允許0打頭；   (2) 不允許0打頭。解：(1)gs=(s,p,d,n,0,1,2,9,p,s) p: s->pd|d p->np|n d->0|2|4|6|8 n->0|1|2|3|4|5|6|7|8|9 (2)gs=(s,p,r,d,n,q ,0,1,2,9,p,s) p: s->pd|p0|d p->nr|n r->qr|q d->2|4|6|8 n->1|2|3|4|5|6|7|8|9 q->0|1|2|3|4|5|6|

9、7|8|9 3. 已知文法 ge 為：     et|e+t|e-t     tf|t*f|t/f     f （ e ） |i 該文法的開始符號（識別符號）是什么？ 請給出該文法的終結(jié)符號集合 vt 和非終結(jié)符號集合 vn 。 找出句型 t+t*f+i 的所有短語、簡單短語和句柄。解： 該文法的開始符號（識別符號）是e。 該文法的終結(jié)符號集合vt=+、-、*、/、（、）、i。 非終結(jié)符號集合vn=e、t、f。 句型t+t*f+i的短語為i、t*f、第一個t、t+t*f+i;

10、 簡單短語為i、t*f、第一個t;句柄為第一個t。4. 構(gòu)造正規(guī)式相應(yīng)的 nfa : 1(0|1)*101 解1(0|1)*101對應(yīng)的nfa為 5. 寫出表達(dá)式(ab*c)/(ab)d的逆波蘭表示和三元式序列。逆波蘭表示： abc*ab/d 三元式序列： (*，b，c) (，a，) (，a，b) (/，) (，d)五.計(jì)算題（10分）構(gòu)造下述文法 gs 的自動機(jī)： s->a0 a->a0|s1|0 該自動機(jī)是確定的嗎？若不確定，則對它確定化。解：由于該文法的產(chǎn)生式s->a0，a->a0|s1中沒有字符集vt的輸入，所以不是確定的自動機(jī)。 要將其他確定化，必須先用代入法

11、得到它對應(yīng)的正規(guī)式。把s?a0代入產(chǎn)生式a?s1有：a=a0|a01|0=a(0|01)|0=0(0|01)*。 代入s->a0有該文法的正規(guī)式：0(0|01)*0，所以，改寫該文法為確定的自動機(jī)為： 由于狀態(tài)a有3次輸入0的重復(fù)輸入，所以上圖只是nfa，下面將它確定化： 下表由子集法將nfa轉(zhuǎn)換為dfa: 由上表可知dfa為：編譯原理模擬試題二一、是非題（請?jiān)诶ㄌ杻?nèi)，正確的劃，錯誤的劃×）（每個2分，共20分）1“ 用高級語言書寫的源程序都必須通過編譯,產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行 ”這種說法。(× )2若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。(

12、× )3一個句型的句柄一定是文法某產(chǎn)生式的右部。 ()4在程序中標(biāo)識符的出現(xiàn)僅為使用性的。 (× )5僅考慮一個基本塊，不能確定一個賦值是否真是無用的。 ( )6削減運(yùn)算強(qiáng)度破壞了臨時變量在一基本塊內(nèi)僅被定義一次的特性。 ( )7在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。 (× )8算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。 (×)9數(shù)組元素的地址計(jì)算與數(shù)組的存儲方式有關(guān)。 (×)10編譯程序與具體的機(jī)器有關(guān),與具體的語言無關(guān)。 (× )二、選擇題(請?jiān)谇袄ㄌ杻?nèi)選擇最確切的一項(xiàng)作為答案劃一個勾，多劃按錯論)(每個4

13、分，共40分)1 通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個部分，還應(yīng)包括_。a( ) 模擬執(zhí)行器             b( ) 解釋器       c( ) 表格處理和出錯處理     d( ) 符號執(zhí)行器2 文法 gn= （ b ， n ， b ， n ， nbbb ， bbn ），該文法所描述的語言是  a( ) l(g

14、n)=bii0   b( ) l(gn)=b2ii0 c( ) l(gn)=b2i+1i0  d( ) l(gn)=b2i+1i13 一個句型中的最左_稱為該句型的句柄。a( ) 短語         b( ) 簡單短語       c( ) 素短語          d( ) 終結(jié)符號 4 設(shè) g 是一個給定的文法， s 是文法的開始符號，如果 s->x( 其中 xv*), 則稱 x 是文

15、法 g 的一個_。a( ) 候選式       b( ) 句型         c( ) 單詞         d( ) 產(chǎn)生式 5 文法 ge ：       ete t       tft f       fa （ e ） 該

16、文法句型 e f (e t) 的簡單短語是下列符號串中的_。 （ e t ）   e t      f    f (e t) a( ) 和 b( ) 和 c( ) 和 d( ) 6 若一個文法是遞歸的，則它所產(chǎn)生的語言的句子_。a( ) 是無窮多個   b( ) 是有窮多個     c( ) 是可枚舉的       d( ) 個數(shù)是常量 7 詞法分析器用于識別_。a( ) 句子   &#

17、160;  b( ) 句型         c( ) 單詞         d( ) 產(chǎn)生式 8 在語法分析處理中， first 集合、 follow 集合、 select 集合均是_。a. ( ) 非終極符集       b( ) 終極符集        c( ) 字母表       d

18、. ( ) 狀態(tài)集 9 在自底向上的語法分析方法中，分析的關(guān)鍵是_。 a.( ) 尋找句柄         b.( ) 尋找句型       c.( ) 消除遞歸       d.( ) 選擇候選式 10 在 lr 分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型_的 dfa 狀態(tài)。 a.( )句柄            

19、b.( ) 前綴           c.( )活前綴         d.( ) lr(0) 項(xiàng)目 三、填空題(每空1分，共10分)1設(shè)g是一個給定的文法，s是文法的開始符號，如果s->x( 其中 xvt*), 則稱 x是文法的一個_句子_。 2遞歸下降法不允許任一非終極符是直接_左_遞歸的。3自頂向下的語法分析方法的基本思想是：從文法的_開始符號_開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行_直接推導(dǎo)_，試圖推導(dǎo)

20、出文法的_句子_，使之與給定的輸入串_匹配_。 4自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行_直接歸約_ ，力求歸約到文法的_開始符號_。 5常用的參數(shù)傳遞方式有_傳地址_，傳值和傳名。 6在使用高級語言編程時,首先可通過編譯程序發(fā)現(xiàn)源程序的全部_語法_錯誤和語義部分錯誤。四、簡答題（20分）1. 已知文法 gs 為：    sdab    aaa|a    bbb|    gs 產(chǎn)生的語言是什么？ 答：gs產(chǎn)生的語言是l(gs)=d

21、anbmn1,m0。2. 簡述 dfa 與 nfa 有何區(qū)別 ? 答：dfa與nfa的區(qū)別表現(xiàn)為兩個方面:一是nfa可以若干個開始狀態(tài)，而dfa僅只一個開始狀態(tài)。 另一方面，dfa的映象m是從k×到k，而nfa的映象m是從k×到k的子集， 即映象m將產(chǎn)生一個狀態(tài)集合（可能為空集），而不是單個狀態(tài)。3. 構(gòu)造正規(guī)式相應(yīng)的 dfa : 1(1010 * | 1(010) * 1) * 0。解：1(1010 * | 1(010) * 1) * 0對應(yīng)的nfa為：4. 已知文法g(s) sa|(t) tt，s|s 寫出句子(a，a)，a)的規(guī)范歸約過程及每一步的句柄。解：句型歸約規(guī)

22、則句柄 (a，a)，a)saa (s，a)，a)tss (t，a)，a)saa (t，s)，a)tt，s t，s (s)，a) tss (t)，a) ss(t) (t) (s，a) tss (t，a) saa (t，s) tt，s t，s (t) s(t)(t) s5. 何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級優(yōu)化？1)優(yōu)化：對程序進(jìn)行各種等價變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。 (2) 三種級別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。五.計(jì)算題（10分） 對下面的文法 g ： e->te' e'->+e| t->ft' t' -&g

23、t;t| f-> pf' f'-> *f'| p->(e)|a|b| (1)計(jì)算這個文法的每個非終結(jié)符的 first 集和 follow 集。 (4分) (2) 證明這個方法是 ll(1) 的。(4分) (3) 構(gòu)造它的預(yù)測分析表。(2分) 解：（1）計(jì)算這個文法的每個非終結(jié)符的first集和follow集。 first集合有： first(e)=first(t)=first(f)=first(p)=(,a,b,; first(e')=+, first(t)=first(f)=first(p)=(,a,b,; first(t')=fir

24、st(t)=(,a,b,; first(f)=first(p)=(,a,b,; first(f')=first(p)=*,; first(p)=(,a,b,; follow集合有： follow(e)=),#; follow(e')=follow(e)=),#; follow(t)=first(e')follow(e)=+,),#;/不包含 follow(t')=follow(t)=first(e')follow(e)=+,),#; follow(f)=first(t')follow(t)=(,a,b,+,),#;/不包含 follow(f

25、9;)=follow(f)=first(t')follow(t)=(,a,b,+,),#; follow(p)=first(f')follow(f)=*,(,a,b,+,),#;/不包含 (2)證明這個方法是ll(1)的。 各產(chǎn)生式的select集合有： select(e->te')=first(t)=(,a,b,; select(e'->+e)=+; select(e'->)=follow(e/)=),# select(t->ft')=first(f)=(,a,b,; select(t'->t)=first

26、(t)=(,a,b,; select(t'->)=follow(t/)=+,),#; select(f->pf')=first(p)=(,a,b,; select(f'->*f')=*; select(f'->)=follow(f')=(,a,b,+,),#; select(p->(e)=( select(p->a)=a select(p->b)=b select(p->)= 可見，相同左部產(chǎn)生式的select集的交集均為空，所以文法ge是ll(1)文法。 (3)構(gòu)造它的預(yù)測分析表。 文法ge的預(yù)測

27、分析表如下： 編譯原理模擬試題三一、是非題（請?jiān)诶ㄌ杻?nèi)，正確的劃，錯誤的劃×）（每個2分，共20分）1對于數(shù)據(jù)空間的存貯分配，fortran采用動態(tài)貯存分配策略。(×)2甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。(× )3遞歸下降分析法是自頂向上分析方法。( )4產(chǎn)生式是用于定義詞法成分 的一種書寫規(guī)則。 (×)5lr 法是自頂向下語法分析方法。 ( )6在 slr （ 1 ）分析法的名稱中，s的含義是簡單的。()7綜合屬性是用于 “ 自上而下 ” 傳遞信息。(× )8符號表中的信息欄中登記了每個名字的

28、屬性和特征等有關(guān)信息 ，如類型、種屬、所占單元大小、地址等等。 (×)9程序語言的語言處理程序是一種應(yīng)用軟件。 (×)10解釋程序適用于 cobol 和 fortran 語言。 (×)二、選擇題(請?jiān)谇袄ㄌ杻?nèi)選擇最確切的一項(xiàng)作為答案劃一個勾，多劃按錯論)(每個4分，共40分)1 文法 g 產(chǎn)生的_的全體是該文法描述的語言。a( ) 句型 b( ) 終結(jié)符集 c( ) 非終結(jié)符集 d( ) 句子2 若文法 g 定義的語言是無限集，則文法必然是 _。  a( ) 遞歸的   b( ) 前后文無關(guān)的  c( ) 二義性的 d( ) 無二義性

29、的3 四種形式語言文法中，1型文法又稱為 _文法。a( ) 短語結(jié)構(gòu)文法       b( ) 前后文無關(guān)文法 c( ) 前后文有關(guān)文法     d( ) 正規(guī)文法 4 一個文法所描述的語言是_。a( ) 唯一的         b( ) 不唯一的   c( ) 可能唯一，好可能不唯一   d( ) 都不對5 _和代碼優(yōu)化部分不是每個編譯程序都必需的。a( ) 語法分析   b( ) 中間代碼生成  

30、60;    c( ) 詞法分析       d( ) 目標(biāo)代碼生成 6_是兩類程序語言處理程序。 a( ) 高級語言程序和低級語言程序         b( ) 解釋程序和編譯程序 c( ) 編譯程序和操作系統(tǒng)                 d( ) 系統(tǒng)程序和應(yīng)用程序 7 數(shù)組的內(nèi)情向量中肯定

31、不含有數(shù)組的_的信息。a. ( ) 維數(shù) b( ) 類型       c( ) 維上下界         d( ) 各維的界差 8. 一個上下文無關(guān)文法 g 包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組 _。 a( ) 句子 b( ) 句型c( ) 單詞 d( ) 產(chǎn)生式9 文法分為四種類型，即0型、1型、2型、3型。其中2型文法是_。a. ( ) 短語文法     b( ) 正則文法   &

32、#160; c( ) 上下文有關(guān)文法d( ) 上下文無關(guān)文法10文法 g 所描述的語言是_的集合。 a. ( ) 文法 g 的字母表 v 中所有符號組成的符號串b( ) 文法 g 的字母表 v 的閉包 v* 中的所有符號串c( ) 由文法的開始符號推出的所有終極符串d. ( ) 由文法的開始符號推出的所有符號串三、填空題(每空1分，共10分)1一個句型中的最左簡單短語稱為該句型的_句柄_。 2對于文法的每個產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為 _語義規(guī)則_ 。3一個典型的編譯程序中，不僅包括_詞法分析_、_語法分析_、_中間代碼生成_、代碼優(yōu)化、目標(biāo)代碼生成等五個部分，還應(yīng)包括表格處理和出錯

33、處理。4 從功能上說，程序語言的語句大體可分為_執(zhí)行性_語句和_說明性_語句兩大類。5 掃描器的任務(wù)是從_源程序_中識別出一個個_單詞符號_。 6 產(chǎn)生式是用于定義_語法范疇_的一種書寫規(guī)則。 四、簡答題（20分）1. 寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以0開頭。解：文法g(n)： nab|b aac|d b1|3|5|7|9 db|2|4|6|8 c0|d2. 設(shè)文法g(s)： s(l)|a s|a ll，s|s    (1) 消除左遞歸和回溯；   (2) 計(jì)算每個非終結(jié)符的first和follow。解：(1) s(l)|

34、as' s's| lsl' l'sl'| (2) first)s)(，afollow(s)#，) first(s')，a,follow(s')#，) first(l)(，afollow(l) ) first(l')，follow(l' )3. 已知文法g(e) et|et tf|t *f f(e)|i (1)給出句型(t *fi)的最右推導(dǎo)； (2)給出句型(t *fi)的短語、素短語。解：(1) 最右推導(dǎo)： e->t->f->(e)->(et)->(ef)->(ei) ->(ti

35、)->(t*fi) (2) 短語：(t*fi)，t*fi，t*f，i 素短語：t*f,i 4. whilea0 b0do begin x：x1； if a0 then a：a1 else b：b1 end； 翻譯成四元式序列。解： (1) (j，a，0，5) (2) (j，3) (3) (j，b，0，5) (4) (j，15) (5) (，×，1，t1) (6) (：，t1，×) (7) (j，a，0，9) (8) (j，12) (9) (，a，1，t2) (10) (：，t2，a) (11) (j，1) (12) (，b，1， t3) (13) (：，t3，b) (

36、14) (j，1) (15)五.計(jì)算題（10分）已知 nfa= （ x,y,z,0,1,m,x,z ），其中：m(x,0)=z,m(y,0)=x,y,m(z,0)=x,z,m(x,1)=x, m(y,1)= ,m(z,1)=y, 構(gòu)造相應(yīng)的dfa并最小化。 解：根據(jù)題意有nfa圖: 下表由子集法將nfa轉(zhuǎn)換為dfa： 下面將該dfa最小化： (1) 首先將它的狀態(tài)集分成兩個子集：p1=a,d,e,p2=b,c,f (2) 區(qū)分p2:由于f(f,1)=f(c,1)=e,f(f,0)=f并且f(c,0)=c,所以f，c等價。由于f(b,0)=f(c,0)=c, f(b,1)=d,f(c,1)=e,

37、而d，e不等價（見下步），從而b與c，f可以區(qū)分。有p21=c,f,p22=b。 (3) 區(qū)分p1:由于a，e輸入0到終態(tài)，而d輸入0不到終態(tài)，所以d與a，e可以區(qū)分，有p11=a,e,p12=d。 (4) 由于f(a,0)=b,f(e,0)=f,而b，f不等價，所以a，e可以區(qū)分。 (5) 綜上所述，dfa可以區(qū)分為p=a，b，d，e，c，f。所以最小化的dfa如下： 編譯原理模擬試題四一、是非題（請?jiān)诶ㄌ杻?nèi)，正確的劃，錯誤的劃×）（每個2分，共20分）1一個 ll(l)文法一定是無二義的。 (× )2正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 (× )3

38、一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認(rèn)為是初態(tài)，最多只有一個終態(tài)。 ()4目標(biāo)代碼生成時，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。 (× )5逆波蘭法表示的表達(dá)式亦稱前綴式 。 ( )6如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的。 ( )7lr 法是自頂向下語法分析方法。 (× )8數(shù)組元素的地址計(jì)算與數(shù)組的存儲方式有關(guān)。(× )9算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。 (×)10對于數(shù)據(jù)空間的存貯分配， fortran 采用動態(tài)貯存分配策略。 (×)二、選擇題(請?jiān)谇袄ㄌ杻?nèi)選擇最確切的一項(xiàng)作為答案劃一個勾，多劃按

39、錯論)(每個4分，共40分)1詞法分析器用于識別_。  a( ) 字符串   b( )語句 c( )單詞 d( )標(biāo)識符2文法分為四種類型，即0型、1型、2型、3型。其中0型文法是_。a. ( ) 短語文法     b( ) 正則文法     c( ) 上下文有關(guān)文法 d( ) 上下文無關(guān)文法3一個上下文無關(guān)文法 g 包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組 _。 a( ) 句子 b( ) 句型 c( ) 單詞 d( ) 產(chǎn)生式4_是一種典型的解釋型語言。  a( )

40、 basic b( ) c c( ) fortran  d( ) pascal5與編譯系統(tǒng)相比，解釋系統(tǒng)_。a( ) 比較簡單 , 可移植性好 , 執(zhí)行速度快 b( ) 比較復(fù)雜 , 可移植性好 , 執(zhí)行速度快   c( ) 比較簡單 , 可移植性差 , 執(zhí)行速度慢 d( ) 比較簡單 , 可移植性好 , 執(zhí)行速度慢 6用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫_。   a( ) 源程序       b( ) 目標(biāo)程序      c( )

41、 連接程序 d( ) 解釋程序7詞法分析器用于識別_。   a. ( ) 字符串       b( ) 語句          c( ) 單詞        d( ) 標(biāo)識符 8編寫一個計(jì)算機(jī)高級語言的源程序后 , 到正式上機(jī)運(yùn)行之前，一般要經(jīng)過_這幾步: (1) 編輯   (2) 編譯   (3) 連接   (4) 運(yùn)行 a. ( ) (1)(2)(3)(

42、4)     b( ) (1)(2)(3)    c( ) (1)(3)     d( ) (1)(4)9把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由_完成的。a( ) 編譯器            b( ) 匯編器             c( ) 解釋器 &#

43、160;          d( ) 預(yù)處理器10文法 g 所描述的語言是_的集合。 a. ( ) 文法 g 的字母表 v 中所有符號組成的符號串b( ) 文法 g 的字母表 v 的閉包 v* 中的所有符號串c( ) 由文法的開始符號推出的所有終極符串d. ( ) 由文法的開始符號推出的所有符號串三、填空題(每空1分，共10分)1語法分析是依據(jù)語言的_語法_規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的_語義_規(guī)進(jìn)行的。2語法分析器的輸入是_單詞符號串_，其輸出是_語法單位_。3一個名字的屬性包括_類型_

44、和_作用域_。4產(chǎn)生式是用于定義_語法成分_的一種書寫規(guī)則。5逆波蘭式 ab+c+ d*e- 所表達(dá)的表達(dá)式為_(a+b+c)*d-e_ 。 6語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。 四、簡答題（20分）1. 寫出下列表達(dá)式的三地址形式的中間表示。   (1) 5+6 *(a + b);    (2)for j:=1 to 10 do aj + j:=0。答： (1)100: t1:=a+b 101: t2:=6*t1 102: t3:=5+t2 (2)100: j:=1 101: if j>10 goto

45、 next 102: i:=j+j 103: ai:=02. 設(shè)基本塊p由如下語句構(gòu)成：    t 0 : =3.14;    t 1 :=2*t 0 ;    t 2 :=r+r;    a:=t l *t 2 ；    b:=a;    t 3 :=2*t 0 ;    t 4 :=r+r;    t 5 :=t 3 *t 4 ;   

46、; t 6 :=r-r ；    b:=t 5 *t 6 ；試給出基本塊p的 dag 。解：基本塊p的dag圖:3. 寫出表達(dá)式(a+b)/(a-b-(a+b*c)的三元序列及四元序列。解：（1）三元式： （，a，b） （，a，b） （/，） （*，b，c） （，a，） （，） （2）四元式： （，a，b，t1） （，a，b，t2） （/，t1，t2，t3） （*，b，c，t4） （，a，t4，t5） （，t3，t5，t6）4. 寫一個文法使其語言為偶數(shù)集，且每個偶數(shù)不以0開頭。 解：文法g（s）： sab|b|a0 aad|c b2|4|6|8 c1|

47、3|5|7|9|b d0|c5. 設(shè)文法 g （ s ）：    ss af|af| af    f*af|*a  （1）消除左遞歸和回溯； （2）構(gòu)造相應(yīng)的 first 和 follow 集合。1） s->afs'|afs' s'->afs'| f->*af' f'->f| （2） first（s）a，+ follow（s） first（s'）+， follow（s'） first（f）* follow（f）（+， first（f'）*，

48、 follow（+，五.計(jì)算題（10分）  已知文法為：   s->a|(t)   t->t,s|s   構(gòu)造它的 lr(0)分析表。 解：加入非終結(jié)符s'，方法的增廣文法為： s'->s s->a s-> s->(t) t->t,s t->s 下面構(gòu)造它的lr(0)項(xiàng)目集規(guī)范族為： 從上表可看出,不存在移進(jìn)-歸約沖突以及歸約歸約沖突，該文法是lr(0)文法。 從而有下面的lr(0)分析表： 編譯原理模擬試題五一、是非題（請?jiān)诶ㄌ杻?nèi)，正確的劃，錯誤的劃

49、×）（每個2分，共20分）1編譯程序是對高級語言程序的解釋執(zhí)行。(× )2一個有限狀態(tài)自動機(jī)中，有且僅有一個唯一的終態(tài)。(×)3一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。 ( )4語法分析時必須先消除文法中的左遞歸 。 (×)5lr分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔn)確地指出出錯地點(diǎn)。 ()6逆波蘭表示法表示表達(dá)式時無須使用括號。 ( )7靜態(tài)數(shù)組的存儲空間可以在編譯時確定。 (×)8進(jìn)行代碼優(yōu)化時應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將起更大作用。 (×)9兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價

50、。 (× )10一個語義子程序描述了一個文法所對應(yīng)的翻譯工作。 (×)二、選擇題(請?jiān)谇袄ㄌ杻?nèi)選擇最確切的一項(xiàng)作為答案劃一個勾，多劃按錯論)(每個4分，共40分)1詞法分析器的輸出結(jié)果是_。a( ) 單詞的種別編碼 b( ) 單詞在符號表中的位置 c( ) 單詞的種別編碼和自身值 d( ) 單詞自身值2 正規(guī)式 m 1 和 m 2 等價是指_。  a( ) m1和m2的狀態(tài)數(shù)相等          b( ) m1和m2的有向邊條數(shù)相等c( ) m1和m2所識別的語言集相等 d( ) m1和m2狀

51、態(tài)數(shù)和有向邊條數(shù)相等 3 文法g：sxsx|y所識別的語言是_。a( ) xyx  b( ) (xyx)* c( ) xnyxn(n0)     d( ) x*yx* 4如果文法g是無二義的，則它的任何句子_。a( )最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同 b( ) 最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同 c( ) 最左推導(dǎo)和最右推導(dǎo)必定相同   d( )可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同 5構(gòu)造編譯程序應(yīng)掌握_。a( )源程序   b( ) 目標(biāo)語言     

52、0; c( ) 編譯方法      d( ) 以上三項(xiàng)都是 6四元式之間的聯(lián)系是通過_實(shí)現(xiàn)的。 a( ) 指示器         b( ) 臨時變量 c( ) 符號表             d( ) 程序變量 7表達(dá)式(ab)(cd)的逆波蘭表示為_。a. ( ) abcd b( ) abcd       

53、 c( ) abcd         d( ) abcd 8. 優(yōu)化可生成_的目標(biāo)代碼。a( ) 運(yùn)行時間較短               b( ) 占用存儲空間較小c( ) 運(yùn)行時間短但占用內(nèi)存空間大 d( ) 運(yùn)行時間短且占用存儲空間小9下列_優(yōu)化方法不是針對循環(huán)優(yōu)化進(jìn)行的。a. ( ) 強(qiáng)度削弱     b( ) 刪除歸納變量  &

54、#160;  c( ) 刪除多余運(yùn)算   d( ) 代碼外提10編譯程序使用_區(qū)別標(biāo)識符的作用域。 a. ( ) 說明標(biāo)識符的過程或函數(shù)名b( ) 說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次c( ) 說明標(biāo)識符的過程或函數(shù)的動態(tài)層次 d. ( ) 標(biāo)識符的行號三、填空題(每空1分，共10分)1計(jì)算機(jī)執(zhí)行用高級語言編寫的程序主要有兩種途徑：_解釋_和_編譯_。 2掃描器是_詞法分析器_，它接受輸入的_源程序_，對源程序進(jìn)行_詞法分析_并識別出一個個單詞符號，其輸出結(jié)果是單詞符號，供語法分析器使用。3自上而下分析法采用_移進(jìn)_、歸約、錯誤處理、_接受_等四種操作。4一個lr分析

55、器包括兩部分：一個總控程序和_一張分析表_。5后綴式abc-/所代表的表達(dá)式是_a/(b-c)_。 6局部優(yōu)化是在_基本塊_范圍內(nèi)進(jìn)行的一種優(yōu)化。四、簡答題（20分）1. 簡要說明語義分析的基本功能。答：語義分析的基本功能包括: 確定類型、類型檢查、語義處理和某些靜態(tài)語義檢 查。2. 考慮文法 gs: s (t) | a+s | a t t,s | s 消除文法的左遞歸及提取公共左因子。解：消除文法gs的左遞歸： s(t) | a+s | a tst t,st| 提取公共左因子： s(t) | as s+s | tst t,st| 3. 試為表達(dá)式 w+(a+b)*(c+d/(e-10)+8)

56、 寫出相應(yīng)的逆波蘭表示。解： w a b + c d e 10 - / + 8 + * +4. 按照三種基本控制結(jié)構(gòu)文法將下面的語句翻譯成四元式序列：while (a<c b<d) if (a 1) c=c+1;else while (a d)a=a+2;。解：該語句的四元式序列如下(其中e1、e2和e3分別對應(yīng)acbd、a1和ad，并且關(guān)系運(yùn)算符優(yōu)先級高)： 100 (j<,a,c,102) 101 (j,_,_,113) 102 (j<,b,d,104) 103 (j,_,_,113) 104 (j=,a,1,106) 105 (j,_,_,108) 106 (+,

57、 c, 1, c) 107 (j,_,_,112) 108 (j,a,d,110) 109 (j,_,_,112) 110 (+, a, 2, a) 111 (j,_,_,108) 112 (j,_,_,100) 1135. 已知文法 gs 為 s asb|sb|b ，試證明文法 gs 為二義文法。證明： 由文法gs：sasb|sb|b，對句子aabbbb對應(yīng)的兩棵語法樹為： 因此，文法gs為二義文法。 五.計(jì)算題（10分）已知文法 a->aad|aab| 判斷該文法是否是 slr(1) 文法，若是構(gòu)造相應(yīng)分析表，并對輸入串 ab# 給出分析過程。解：增加一個非終結(jié)符s/后，產(chǎn)生原文法的

58、增廣文法有： s'->a a->aad|aab| 下面構(gòu)造它的lr(0)項(xiàng)目集規(guī)范族為： 從上表可看出,狀態(tài)i0和i2存在移進(jìn)-歸約沖突，該文法不是lr(0)文法。對于i0來說有：follow(a)a=b,d,#a=，所以在i0狀態(tài)下面臨輸入符號為a時移進(jìn)，為b,d,#時歸約，為其他時報錯。對于i2來說有也有與i0完全相同的結(jié)論。這就是說，以上的移進(jìn)-歸約沖突是可以解決的，因此該文法是slr(1)文法。 其slr(1)分析表為： 對輸入串a(chǎn)b#給出分析過程為： 編譯原理模擬試題六一、是非題（請?jiān)诶ㄌ杻?nèi)，正確的劃，錯誤的劃×）（每個2分，共20分）1設(shè)r和s分別是正

59、規(guī)式，則有l(wèi)(r|s)=l(r)l(s)。(×)2確定的自動機(jī)以及不確定的自動機(jī)都能正確地識別正規(guī)集。()3詞法分析作為單獨(dú)的一遍來處理較好。 (× )4構(gòu)造lr分析器的任務(wù)就是產(chǎn)生lr分析表。 ()5規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個過程。 (× )6同心集的合并有可能產(chǎn)生新的“移進(jìn)”/“歸約”沖突。 (× )7lr分析技術(shù)無法適用二義文法。 (× )8樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。 (×)9程序中的表達(dá)式語句在語義翻譯時不需要回填技術(shù)。 ()10對中間代碼的優(yōu)化依賴于具體的計(jì)算機(jī)。 (× )二、

60、選擇題(請?jiān)谇袄ㄌ杻?nèi)選擇最確切的一項(xiàng)作為答案劃一個勾，多劃按錯論)(每個4分，共40分)1編譯程序絕大多數(shù)時間花在_ 上。a( ) 出錯處理 b( ) 詞法分析 c( ) 目標(biāo)代碼生成 d( ) 表格管理2 編譯程序是對_。  a( ) 匯編程序的翻譯   b( ) 高級語言程序的解釋執(zhí)行  c( ) 機(jī)器語言的執(zhí)行 d( ) 高級語言的翻譯 3 采用自上而下分析，必須_。a( ) 消除左遞歸  b( ) 消除右遞歸  c( ) 消除回溯   d( ) 提取公共左因子 4在規(guī)范歸約中，用_來刻畫可歸約串。a( )直接短語 b( )句柄   c( )最左素短語