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

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

2、的選擇。（X）9 . LR法是自頂向下語(yǔ)法分析方法。（X）10 .簡(jiǎn)單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。（X）二、 選擇題 （ 請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論）（ 每個(gè) 4 分，共 40 分 ）1 一個(gè)編譯程序中，不僅包含詞法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分。A （ ） 語(yǔ)法分析B （ ） 文法分析C （ ） 語(yǔ)言分析D （ ） 解釋分析2 詞法分析器用于識(shí)別。A （ ） 字符串B （ ） 語(yǔ)句C （ ） 單詞D （ ） 標(biāo)識(shí)符3 語(yǔ)法分析器則可以發(fā)現(xiàn)源程序中的。A （ ） 語(yǔ)義錯(cuò)誤B （ ） 語(yǔ)法和語(yǔ)義錯(cuò)誤D （ ） 語(yǔ)法錯(cuò)誤C （ ） 錯(cuò)

3、誤并校正4 下面關(guān)于解釋程序的描述正確的是。(1) 解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼解釋程序適用于COBOL和FORTRAN言(3) 解釋程序是為打開(kāi)編譯程序技術(shù)的僵局而開(kāi)發(fā)的A ( ) (1)(2)B ( ) (1)C ( ) (1)(2)(3)D ( ) (2)(3)5 解釋程序處理語(yǔ)言時(shí), 大多數(shù)采用的是方法。A ( ) 源程序命令被逐個(gè)直接解釋執(zhí)行8 ( ) 先將源程序轉(zhuǎn)化為中間代碼, 再解釋執(zhí)行C ( ) 先將源程序解釋轉(zhuǎn)化為目標(biāo)程序, 再執(zhí)行D ( ) 以上方法都可以6 編譯過(guò)程中, 語(yǔ)法分析器的任務(wù)就是。(1) 分析單詞是怎樣構(gòu)成的(2) 分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的

4、(3) 分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的(4) 分析程序的結(jié)構(gòu)A ( ) (2)(3)B( ) (2)(3)(4)C ( ) (1)(2)(3)D( ) (1)(2)(3)(4)7 編譯程序是一種A. ( ) 匯編程序8 ( ) 翻譯程序C ( ) 解釋程序D ( ) 目標(biāo)程序9 文法 G 所描述的語(yǔ)言是的集合。A. ( )文法G 的字母表V 中所有符號(hào)組成的符號(hào)串B ( ) 文法G 的字母表V 的閉包V* 中的所有符號(hào)串C ( ) 由文法的開(kāi)始符號(hào)推出的所有終極符串D. ( ) 由文法的開(kāi)始符號(hào)推出的所有符號(hào)串9 .文法分為四種類型，即0型、1型、2型、3型。其中3型文法是。A.() 短語(yǔ)文法

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

6、輸出結(jié)果是目標(biāo)程序 。5 .產(chǎn)生式是用于定義語(yǔ)法成分的一種書(shū)寫(xiě)規(guī)則。6 .語(yǔ)法分析最常用的兩類方法是 自上而下 和 自下而上 分析法。四、簡(jiǎn)答題(20分)1 .什么是句子？什么是語(yǔ)言？答：(1)設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果S x(其中xC VT*),則稱x是文法的一個(gè)句子。(2)設(shè)GS是給定文法，則由文法G所定義的語(yǔ)言L(G)可描述為：L(G)=x S x,XE VT*。2 .寫(xiě)一文法，使其語(yǔ)言是偶正整數(shù)的集合，要求：(1)允許0打頭；(2)不允許0打頭。解：GS=(S,P,D,N,0,1,2,9,P,S)P:S->PD|DP->NP|ND->0|2|4|6

7、|8N->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|DP->NR|NR->QR|QD->2|4|6|8N->1|2|3|4|5|6|7|8|9Q->0|1|2|3|4|5|6|7|8|93 .已知文法GE為：E-T|E+T|E -T T- F|T*F|T/F F- （ E ） |i該文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）是什么？請(qǐng)給出該文法的終結(jié)符號(hào)集合VT和非終結(jié)符號(hào)集合 VN 。 找出句型T+T*F+i的所有短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。解：該文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）是 E。該文法的終

8、結(jié)符號(hào)集合VT=+、-、*、/、（、）、i。非終結(jié)符號(hào)集合 VN=E、T、F。句型T+T*F+I的短語(yǔ)為i、T*F、第一個(gè)T、T+T*F+i;簡(jiǎn)單短語(yǔ)為i、T*F、第一個(gè)T;句柄 為第一個(gè)To4 .構(gòu)造正規(guī)式相應(yīng)的 NFA : 1（0|1）*101解1（0|1）*101對(duì)應(yīng)的NFA為5 .寫(xiě)出表達(dá)式（a+b*c）/（a+b）d的逆波蘭表示和三元式序列。逆波蘭表示：abc*+ab+/d 三元式序列：（* , b, c）（+ , a,）（+ ,a, b）（/ ,，）（一，d）五.計(jì)算題（10分） 構(gòu)造下述文法 GS的自動(dòng)機(jī):S->A0A->A0|S1|0 該自動(dòng)機(jī)是確定的嗎？若不確定，

9、則對(duì)它確定化。解：由于該文法的產(chǎn)生式S->A0, A->A0|S1中沒(méi)有字符集 VT的輸入，所以不是確定的自S?A0代入產(chǎn)生式A?S10（0|01）*0，所以，改寫(xiě)該文法為確定的自動(dòng)機(jī)為:動(dòng)機(jī)。 要將其他確定化，必須先用代入法得到它對(duì)應(yīng)的正規(guī)式。把 有：A=A0|A01|0=A（0|01）|0=0（0|01）* 。代入 S->A0 舉由于狀態(tài)A有3次輸入0的重復(fù)輸入，所以上圖只是 NFA, 下 表 由 子 集 法 將 NFA 轉(zhuǎn) 換 為DFA:IL = ey4部rg合加曰而也C）It =殳&皿rw國(guó)?ve助"FAMbMC 區(qū) Tf ZC兀7C區(qū)兀zbM由上表

10、可知DFA為:編譯原理模擬試題二一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃M錯(cuò)誤的劃X）（每個(gè)2分，共20分）1 “ 用高級(jí)語(yǔ)言書(shū)寫(xiě)的源程序都必須通過(guò)編譯,產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說(shuō)法。（乃2 .若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。（X）3 . 一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。（，）4 .在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。（X）5 .僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無(wú)用的。（，）6 .削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。（，）7 .在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。（區(qū)8 .算符優(yōu)先關(guān)系表不一定存在對(duì)

11、應(yīng)的優(yōu)先函數(shù)。（9 .數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。（10 .編譯程序與具體的機(jī)器有關(guān) ，與具體的語(yǔ)言無(wú)關(guān)。（乃二、 選擇題（請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論）（每個(gè)4分， 共40 分 ）1 通常一個(gè)編譯程序中，不僅包含詞法分析，語(yǔ)法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括。A （ ） 模擬執(zhí)行器B （ ） 解釋器C （ ） 表格處理和出錯(cuò)處理D （ ） 符號(hào)執(zhí)行器2文法 GN= (b述的語(yǔ)言是N , B , N , N-b bB , B- bN),該文法所描A. ( ) L(GN尸bii >0 B. ( ) L(GN尸b2ii &

12、gt;0C. ( ) L(GN尸b2i+1i >0D. ( ) L(GN尸b2i+1i >13 一個(gè)句型中的最左稱為該句型的句柄。A ( ) 短語(yǔ)B ( ) 簡(jiǎn)單短語(yǔ)C ( ) 素短語(yǔ)D ( ) 終結(jié)符號(hào)4 設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果S->x(其中xCV*),則稱x是文法 G 的一個(gè) 。A ( ) 候選式B ( ) 句型C ( ) 單詞D ( ) 產(chǎn)生式5 文法 GE ：EfT I E + TTfF I T * FFa I ( E )該文法句型 E + F * (E + T)的簡(jiǎn)單短語(yǔ)是下列符號(hào)串中的 。(E+T) E+T F F*(E + T)A ( )

13、 和 B ( ) 和 C ( ) 和 D ( ) 6 若一個(gè)文法是遞歸的，則它所產(chǎn)生的語(yǔ)言的句子。A ( ) 是無(wú)窮多個(gè)B ( ) 是有窮多個(gè)C ( ) 是可枚舉的D ( ) 個(gè)數(shù)是常量7 詞法分析器用于識(shí)別。A ( ) 句子8 ( ) 句型C ( ) 單詞D ( ) 產(chǎn)生式8 在語(yǔ)法分析處理中，F(xiàn)IRST 集合、 FOLLOW 集合、 SELECT 集合均是。A. ( ) 非終極符集B ( ) 終極符集C ( ) 字母表D. ( ) 狀態(tài)集9 在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是。A.( ) 尋找句柄B.( ) 尋找句型C.( ) 消除遞歸D.( ) 選擇候選式10 在 LR 分析法中，

14、分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型的 DFA 狀態(tài)。A.( ) 句柄B.( ) 前綴C.( )活前綴D.( ) LR(0) 項(xiàng)目(每空1 分，共 10 分 )1 .設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果 S->x(其中xCVT*),則稱x是文 法的一個(gè)_句子_。2遞歸下降法不允許任一非終極符是直接_左 _遞歸的。3自頂向下的語(yǔ)法分析方法的基本思想是：從文法的_開(kāi)始符號(hào)開(kāi)始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行_直接推導(dǎo)，試圖推導(dǎo)出文法的_句子，使之與給定的輸入串_匹配_。4自底向上的語(yǔ)法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行_直接歸約

15、_ ，力求歸約到文法的_開(kāi)始符號(hào)_。5常用的參數(shù)傳遞方式有_傳地址_，傳值和傳名。6在使用高級(jí)語(yǔ)言編程時(shí),首先可通過(guò)編譯程序發(fā)現(xiàn)源程序的全部_語(yǔ)法_錯(cuò)誤和語(yǔ)義部分錯(cuò)誤。四、簡(jiǎn)答題(20 分)1 . 已知文法GS 為：SfdABAf aA|aBfBb| sGS產(chǎn)生的語(yǔ)言是什么？答：GS產(chǎn)生的語(yǔ)言是 L(GS尸danbmn>1,m>02 .簡(jiǎn)述 DFA與NFA有何區(qū)別 ？ 答：DFA與NFA的區(qū)別表現(xiàn)為兩個(gè)方面：一是NFA可以若干個(gè)開(kāi)始狀態(tài)，而 DFA僅只一個(gè) 開(kāi)始狀態(tài)。 另一方面，DFA的映象M是從KXmij K,而NFA的映象M是從KX與U K的 子集，即映象M將產(chǎn)生一個(gè)狀態(tài)集合(

16、可能為空集)，而不是單個(gè)狀態(tài)。3 .構(gòu)造正規(guī)式相應(yīng)的 DFA : 1(1010 * | 1(010) * 1) * 0 。解：1(1010*|1(010)*1)*0 對(duì) 應(yīng) 的 NFA 為：4.已知文法G(S)Sf a| A |(T)T-T , S|S解：句型歸約規(guī)則句柄(a, a), a)S一 aa(S, a), a)TfS(T, a), a)S一 aa(T, S), a)T-T , ST, S(S), a)TfS(T), a)S一 S(T)(T)(S, a)TfS(T, a)S一 aa(T, S)T-T , ST, S(T)S- (T)(T)(a, a), a)的規(guī)范歸約過(guò)程及每一步的句柄

17、。寫(xiě)出句子5. 何謂優(yōu)化？按所涉及的程序范圍可分為哪幾級(jí)優(yōu)化？1) 優(yōu)化：對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能產(chǎn)生更有效的目標(biāo)代碼。2) ) 三種級(jí)別：局部?jī)?yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。五 . 計(jì)算題(10 分)對(duì)下面的文法G ：E->TE'E'->+E| sT->FT'T' ->T| sF-> PF'F'-> *F'|£P->(E)|a|bF(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST 集和 FOLLOW 集。 (4 分 )(2) 證明這個(gè)方法是LL(1) 的。 (4 分 )

18、(3) 構(gòu)造它的預(yù)測(cè)分析表。(2 分 )解： ( 1 )計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST 集和 FOLLOW 集。FIRST 集合有：FIRST(E尸F(xiàn)IRST(T尸F(xiàn)IRST(F尸F(xiàn)IRST(P尸(,a,bF;FIRST(E'尸+,£ FIRST(T尸F(xiàn)IRST(F尸F(xiàn)IRST(P尸(ab,”FIRST(T'尸F(xiàn)IRST(T) U £ =(,a,b,A,£ ;FIRST(F尸F(xiàn)IRST(P尸(,a,bF;FIRST(F'尸F(xiàn)IRST(P)=*,£ ;FIRST(P)=( ,a,b,A;FOLLOW 集合有：FOLLOW(E

19、)=),#;FOLLOW(E'尸F(xiàn)OLLOW(E)=),#;FOLLOW(T尸F(xiàn)IRST(E') U FOLLOW(E尸+,),#;不包含 £FOLLOW(T'尸F(xiàn)OLLOW(T尸F(xiàn)IRST(E')U FOLLOW(E尸+,),#;FOLLOW(F尸F(xiàn)IRST(T') U FOLLOW(T)=(,a,b,A,+,),#;/不包含 £FOLLOW(F'尸F(xiàn)OLLOW(F尸F(xiàn)IRST(T')U FOLLOW(T尸(,a,b,A,+,),#；FOLLOW(P尸F(xiàn)IRST(F') U FOLLOW(F尸*,(,a,b,

20、A,+,),#；不包含 £(2)證明這個(gè)方法是LL(1)的。各產(chǎn)生式的SELECT集合有：SELECT(E->TE')=FIRST(T)=(,a,b,A；SELECT(E'->+E尸+;SELECT(E'- > e )=FOLLOW(E/)=),#SELECT(T->FT')=FIRST(F)=(,a,b,A；SELECT(T'->T)=FIRST(T)=(,a,b,A；SELECT(T'- > e )=FOLLOW(T/尸+,),#;SELECT(F->PF')=FIRST(P)=(,

21、a,b,A；SELECT(F'->*F')=*;SELECT(F'- > £ )=FOLLOW(F')=(,a,b,A,+,),# ；SELECT(P->(E)=(SELECT(P->a尸aSELECT(P->b尸bSELECT(P->A)=A可見(jiàn)，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法 GE是LL(1)文法。(3)構(gòu)造它的預(yù)測(cè)分析表。文法GE的預(yù)測(cè)分析表如下：+*()bfttET TE;4TE,TTEET+E4T吟時(shí)TFT'9FTTFTT4良TT4£9T4T平.F爾刑->PF;

22、PF'F；->3護(hù)4->s->sP (E)Tb編譯原理模擬試題三、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃M錯(cuò)誤的劃乂）（每個(gè)2分，共20分）1.對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。(2甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。(X)3 .遞歸下降分析法是自頂向上分析方法。(V )4 .產(chǎn)生式是用于定義詞法成分的一種書(shū)寫(xiě)規(guī)則。(5 . LR法是自頂向下語(yǔ)法分析方法。(，)6 .在SLR (1 )分析法的名稱中，S的含義是簡(jiǎn)單的。(，)7 .綜合屬性是用于“自上而下”傳遞信息。(兇8符號(hào)表中的信息欄中登記了每個(gè)名字的屬

23、性和特征等有關(guān)信息，如類型、種屬、所占單元大小、地址等等。(>)9 .程序語(yǔ)言的語(yǔ)言處理程序是一種應(yīng)用軟件。(10 .解釋程序適用于 COBOL和FORTRAN語(yǔ)言。(二、 選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)(每個(gè)4分，共40 分 )1 文法 G 產(chǎn)生的 的全體是該文法描述的語(yǔ)言。A ( ) 句型B ( ) 終結(jié)符集C ( ) 非終結(jié)符集D ( ) 句子2 若文法 G 定義的語(yǔ)言是無(wú)限集，則文法必然是。A ( ) 遞歸的B ( ) 前后文無(wú)關(guān)的C ( ) 二義性的D ( ) 無(wú)二義性的3 四種形式語(yǔ)言文法中，1 型文法又稱為文法。B ( ) 前后文無(wú)關(guān)文法

24、A ( ) 短語(yǔ)結(jié)構(gòu)文法C ( ) 前后文有關(guān)文法D ( ) 正規(guī)文法4 一個(gè)文法所描述的語(yǔ)言是。A ( ) 唯一的B ( ) 不唯一的C ( ) 可能唯一，好可能不唯一D ( ) 都不對(duì)5 和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。A ( ) 語(yǔ)法分析B ( ) 中間代碼生成C ( ) 詞法分析D ( ) 目標(biāo)代碼生成6 是兩類程序語(yǔ)言處理程序。B ( ) 解釋程序和編譯程序D ( ) 系統(tǒng)程序和應(yīng)用程序_的信息。( ) 維上下界D ( ) 各維的界差A(yù) ( ) 高級(jí)語(yǔ)言程序和低級(jí)語(yǔ)言程序C ( ) 編譯程序和操作系統(tǒng)7 數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的_A. ( ) 維數(shù)B ( ) 類型C8

25、 一個(gè)上下文無(wú)關(guān)文法G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組。A ( ) 句子B ( ) 句型C ( ) 單詞D ( ) 產(chǎn)生式9 文法分為四種類型，即0 型、 1 型、 2 型、 3 型。其中2 型文法是。A. ( ) 短語(yǔ)文法B ( ) 正則文法C ( ) 上下文有關(guān)文法D ( ) 上下文無(wú)關(guān)文法10文法G 所描述的語(yǔ)言是的集合。A. ( ) 文法 G 的字母表V 中所有符號(hào)組成的符號(hào)串B ( ) 文法 G 的字母表V 的閉包 V* 中的所有符號(hào)串C ( ) 由文法的開(kāi)始符號(hào)推出的所有終極符串D. ( ) 由文法的開(kāi)始符號(hào)推出的所有符號(hào)串三、填空題

26、(每空1 分，共 10 分 )1 一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱為該句型的_句柄_。2對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為_(kāi)語(yǔ)義規(guī)則_ 。3 一個(gè)典型的編譯程序中，不僅包括_詞法分析_、 _語(yǔ)法分析_、 _中間代碼生成_代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。4 從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為_(kāi)執(zhí)行性_語(yǔ)句和_說(shuō)明性_語(yǔ)句兩大類。5 掃描器的任務(wù)是從_源程序_中識(shí)別出一個(gè)個(gè)_單詞符號(hào)_。6 產(chǎn)生式是用于定義_語(yǔ)法范疇_的一種書(shū)寫(xiě)規(guī)則。四、簡(jiǎn)答題(20 分)1. 寫(xiě)一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0 開(kāi)頭。解：文法G(N) ：NH AB|BAf

27、AC|DB-1|3|5|7|9A B|2|4|6|8C- 0|D2. 設(shè)文法 G(S)：Sf (L)|a S|aLL , S|S(1) 消除左遞歸和回溯；(2) 計(jì)算每個(gè)非終結(jié)符的FIRST 和 FOLLOW 。解： (1)Sf(L)|aS'SS| £LfSL'L'fSL'| £2. )FIRST)S)=(, aFOLLOW(S) =#, )FIRST(S') = , a, s FOLLOW(S') =#, )FIRST(L) =(, aFOLLOW(L) = )FIRST(L') = , £ FOLLOW(

28、L'= )3. 已知文法G(E)T|E +TT- F|T *FF- (E)|i(1)給出句型(T *F +i)的最右推導(dǎo)；(2)給出句型(T *F + i)的短語(yǔ)、素短語(yǔ)。解 ：(1) 最 右 推 導(dǎo) ：E->T->F->(E)->(E T)->(E F)->(E i)->(T i)->(T*F i)(2) 短語(yǔ)： (T*F i)， T*F i， T*F ， i素短語(yǔ)：T*F,i4. Whilea>0 V b<0 doBeginX： = X+ 1;if a > 0 then a： = a 1else b： = b +1翻

29、譯成四元式序列。解：(j>, a, 0, 5)(2) (j,3)(3) (j<, b, 0, 5)(4) (j,15)(5)( + , X, 1, T1)(6)(: =, T1,沖(7) (j ,. 0, 9)(8) (j,12)(9)( 一 , a, 1, T2)(10)(: =, T2,a)(11) (j,1)(12)( + , b, 1, T3)(13) (: =, T3,b)(14) (j, 一, 1)(15)五.計(jì)算題(10分)已知 NFA= ( x,y,z,0,1,M,x,z)，其中:（）,M騰柑可地DFAM(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M

30、(x,1)=x, M(y,1)=并最小化。解：根據(jù)題意有 NFA圖：下 表 由 子 集 法 將 NFA 轉(zhuǎn) 換 為 DFAI%=腎匕味廿 re i = e-40tmr /MovoAxAxBzC氏zDMC區(qū)，工】C k,=yDyE kj yE yF展內(nèi)工A&ysF k,苑 eE瓦y下面將該DFA最小化：(1)首先將它的狀態(tài)集分成兩個(gè)子集：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 等價(jià)。由于 F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而 D, E 不等價(jià)(見(jiàn)

31、下步)，從而 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(niǎo), F不等價(jià)，所以 A, E可以區(qū)分。綜上所述，DFA可以區(qū)分為P=A , B , D , E , C , F。所以最小化的DFA如下：編譯原理模擬試題四、是非題(請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃M錯(cuò)誤的劃乂)(每個(gè)2分，共20分)1 .一個(gè) LL(l)文法一定是無(wú)二義的。(X)2 .正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。(X)3 . 一張轉(zhuǎn)換圖只包

32、含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。(，)4 .目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。(X)5 .逆波蘭法表示的表達(dá)式亦稱前綴式。(，)6 .如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義的。(，)7 . LR法是自頂向下語(yǔ)法分析方法。(兇8 .數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。(X)9 .算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。(10 .對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN 采用動(dòng)態(tài)貯存分配策略。(二、 選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)(每個(gè) 4分， 共40 分 ) 1 詞法分析器用于識(shí)別A (

33、 ) 字符串B ( )語(yǔ)句C ( )單詞D ( )標(biāo)識(shí)符2文法分為四種類型，即0 型、 1 型、 2 型、 3 型。其中0 型文法是。A. ( ) 短語(yǔ)文法B ( ) 正則文法C ( ) 上下文有關(guān)文法D ( ) 上下文無(wú)關(guān)文法3一個(gè)上下文無(wú)關(guān)文法G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組。A ( ) 句子B ( ) 句型C ( ) 單詞D ( ) 產(chǎn)生式4 是一種典型的解釋型語(yǔ)言。A ( ) BASICB ( ) CC ( ) FORTRAND ( ) PASCAL5與編譯系統(tǒng)相比，解釋系統(tǒng)。A ( ) 比較簡(jiǎn)單, 可移植性好, 執(zhí)行速度快B ( )

34、比較復(fù)雜, 可移植性好, 執(zhí)行速度快C ( ) 比較簡(jiǎn)單, 可移植性差, 執(zhí)行速度慢D ( ) 比較簡(jiǎn)單, 可移植性好, 執(zhí)行速度慢6用高級(jí)語(yǔ)言編寫(xiě)的程序經(jīng)編譯后產(chǎn)生的程序叫A ( ) 源程序B ( ) 目標(biāo)程序7詞法分析器用于識(shí)別。A. ( ) 字符串B ( ) 語(yǔ)句8編寫(xiě)一個(gè)計(jì)算機(jī)高級(jí)語(yǔ)言的源程序后(1) 編輯 (2) 編譯 (3) 連接A. ( ) (1)(2)(3)(4) B ( ) (1)(2)(3)C( ) 連接程序D ( ) 解釋程序C ( ) 單詞D( ) 標(biāo)識(shí)符, 到正式上機(jī)運(yùn)行之前，一般要經(jīng)過(guò)(4) 運(yùn)行C ( ) (1)(3) D ( ) (1)(4)這幾步 :9把匯編語(yǔ)

35、言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由完成的。A ( ) 編譯器B ( ) 匯編器C ( ) 解釋器D ( ) 預(yù)處理器10文法G 所描述的語(yǔ)言是的集合。A. ( ) 文法 G 的字母表V 中所有符號(hào)組成的符號(hào)串B ( ) 文法 G 的字母表V 的閉包 V* 中的所有符號(hào)串C ( ) 由文法的開(kāi)始符號(hào)推出的所有終極符串D. ( ) 由文法的開(kāi)始符號(hào)推出的所有符號(hào)串三、填空題(每空1 分，共 10 分 )_語(yǔ)義_規(guī)1 語(yǔ)法分析是依據(jù)語(yǔ)言的_語(yǔ)法_規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語(yǔ)言的進(jìn)行的。2語(yǔ)法分析器的輸入是_單詞符號(hào)串_，其輸出是_語(yǔ)法單位_。3一個(gè)名字的屬性包括_類型_和 _作用域_。4

36、產(chǎn)生式是用于定義_語(yǔ)法成分_的一種書(shū)寫(xiě)規(guī)則。5逆波蘭式ab+c+ d*e- 所表達(dá)的表達(dá)式為_(kāi)(a+b+c)*d-e _ 。6語(yǔ)法分析最常用的兩類方法是_自上而下_和 _自下而上_分析法。四、簡(jiǎn)答題(20 分)1. 寫(xiě)出下列表達(dá)式的三地址形式的中間表示。1: ) 5+6 *(a + b);(2)for j:=1 to 10 do aj + j:=0 。答： (1)100: t1:=a+b101: t2:=6*t1102: t3:=5+t2(2)100: j:=1103: if j>10 goto NEXT104: i:=j+j105: ai:=02. 設(shè)基本塊p 由如下語(yǔ)句構(gòu)成：T 0

37、: =3.14;T 1 :=2叮 0T 2 kR+r;A:=T l *T 2 ;B:=A;T 3 :=2*T 0 ;T 4 :=R+r;T 5 :=T 3 *T 4 ;T 6 :=R-r ;B:=T 5 *T 6試給出基本塊p的DAG解：基本塊的DAG圖3. 寫(xiě)出表達(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, T

38、5, T6)4. 寫(xiě)一個(gè)文法使其語(yǔ)言為偶數(shù)集，且每個(gè)偶數(shù)不以0 開(kāi)頭。解：文法G（ S） ：S-AB|B|A0Af AD|CB-2|4|6|8C- 1|3|5|7|9|BA 0|C5. 設(shè)文法 G （ S ）：Sf S + aF|aF| + aFF- *aF|*a1）消除左遞歸和回溯；2）構(gòu)造相應(yīng)的FIRST 和 Follow 集合。1)S->aFS'| aFS' S'-> + aFS'| £ F->*aF' F'->F| £2) 2)FOLLOW (S) = #FOLLOW (S') = #F

39、OLLOW (F) = ( +, #FOLLOW ( + , #FIRST (S) = a, + FIRST (S') = + , s FIRST ( F) = * FIRST ( F') = *, &五 . 計(jì)算題（10 分）已知文法為:S->aFI(T)T->T,S|S構(gòu)造它的LR(0)分析表。解：加入非終結(jié)符 S',方法的增廣文法為：S'->SS->aS->AS->(T)T->T,ST->S下面構(gòu)造它的LR(0)項(xiàng)目集規(guī)范族為:飛上與瞥號(hào)a()J#ST5"S5" ST YDL:ST

40、a*L:I :EX叮) "T3 T->*S ST。5* SH (T)Ii： s ->s-Iia.cc1=LI ： ST(，T)T今4»LLI.L：TTS,b： STT) TTS品：ST)I：=S->(1)'耳TTT,咚S-> ,a sx 百I(mǎi)eLIL： 沖. aST*” XT)I3ILI。從上表可看出，不存在移進(jìn)-歸約沖突以及歸約歸約沖突，該文法是LR(0)文法。從而有下面的LR(0)分析表：觸ACTIOKGOTOa()Fn5T0s3sr i1acc2*1IIflHUX1工】3士上X-ri4&se55s；s，6工弓r515is7II也

41、t3上，Xs3SsSjs99X 1TrX 1rH編譯原理模擬試題五一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃M錯(cuò)誤的劃X）（每個(gè)2分，共20分）1 .編譯程序是對(duì)高級(jí)語(yǔ)言程序的解釋執(zhí)行。（X）2 . 一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。（3 . 一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。（，）4 .語(yǔ)法分析時(shí)必須先消除文法中的左遞歸。（5 . LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。（，）6 .逆波蘭表示法表示表達(dá)式時(shí)無(wú)須使用括號(hào)。（，）7 .靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。（8 .進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對(duì)提高目標(biāo)代碼的效率將起更大

42、作用。（方9 .兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。（X）（方10 . 一個(gè)語(yǔ)義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。多劃按錯(cuò)論)(每個(gè) 4分， 共二、 選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，40 分 )1 詞法分析器的輸出結(jié)果是A ( ) 單詞的種別編碼C ( ) 單詞的種別編碼和自身值2 正規(guī)式 M 1 和 M 2 等價(jià)是指A ( ) M1 和 M2 的狀態(tài)數(shù)相等C ( ) M1 和 M2 所識(shí)別的語(yǔ)言集相等B ( ) 單詞在符號(hào)表中的位置D ( ) 單詞自身值B ( ) M1 和 M2 的有向邊條數(shù)相等D ( ) M1 和 M2 狀態(tài)數(shù)和有向邊條數(shù)相等3 .

43、文法G: S- xSx|y所識(shí)別的語(yǔ)言是 。A. ( ) xyx B. ( ) (xyx)* C. ( ) xnyxn(n >0) D. ( ) x*yx*4 .如果文法 G是無(wú)二義的，則它的任何句子a A ( )最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同B ( ) 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能不同C ( ) 最左推導(dǎo)和最右推導(dǎo)必定相同D ( )可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹(shù)相同5構(gòu)造編譯程序應(yīng)掌握。A ( )源程序B ( ) 目標(biāo)語(yǔ)言C ( ) 編譯方法D ( ) 以上三項(xiàng)都是6四元式之間的聯(lián)系是通過(guò)實(shí)現(xiàn)的。B ( ) 臨時(shí)變量A ( ) 指示器D ( ) 程序變量C

44、 ( ) 符號(hào)表7.表達(dá)式AV B) A (C V D)的逆波蘭表示為 。A. ( ) n ABA CD VB. ( ) A n B/ CD V AC. ( ) AB Vn CDV AD. ( ) A NACDV8. 優(yōu)化可生成的目標(biāo)代碼。A ( ) 運(yùn)行時(shí)間較短B ( ) 占用存儲(chǔ)空間較小C ( ) 運(yùn)行時(shí)間短但占用內(nèi)存空間大D ( ) 運(yùn)行時(shí)間短且占用存儲(chǔ)空間小9下列 優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。A. ( ) 強(qiáng)度削弱B ( ) 刪除歸納變量C ( ) 刪除多余運(yùn)算D ( ) 代碼外提10編譯程序使用區(qū)別標(biāo)識(shí)符的作用域。A. ( ) 說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)名B ( ) 說(shuō)明標(biāo)識(shí)符的過(guò)程

45、或函數(shù)的靜態(tài)層次C ( ) 說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)的動(dòng)態(tài)層次D. ( ) 標(biāo)識(shí)符的行號(hào)三、填空題(每空1 分，共 10 分 )1 計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序主要有兩種途徑：_解釋_和 _編譯_。2掃描器是_詞法分析器_，它接受輸入的_源程序_，對(duì)源程序進(jìn)行_詞法分析并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語(yǔ)法分析器使用。3自上而下分析法采用_移進(jìn)_、歸約、錯(cuò)誤處理、_接受_等四種操作。4一個(gè)LR 分析器包括兩部分：一個(gè)總控程序和_一張分析表5.后綴式abc-/所代表的表達(dá)式是 a/(b-c)。6局部?jī)?yōu)化是在_基本塊_范圍內(nèi)進(jìn)行的一種優(yōu)化。四、簡(jiǎn)答題(20 分)1. 簡(jiǎn)要說(shuō)明語(yǔ)義分析

46、的基本功能。答：語(yǔ)義分析的基本功能包括: 確定類型、類型檢查、語(yǔ)義處理和某些靜態(tài)語(yǔ)義檢查。2. 考慮文法GS:S f (T) | a+S | aT f T,S | S消除文法的左遞歸及提取公共左因子。解：消除文法GS 的左遞歸：Sf (T) | a+S | aTf STf，ST ' | £提取公共左因子：Sf (T) | aS'S' f +S |&Tf STf，ST ' | £3. 試為表達(dá)式w+(a+b)*(c+d/(e-10)+8) 寫(xiě)出相應(yīng)的逆波蘭表示。解： w a b + c d e 10 - / + 8 + * +4. 按照

47、三種基本控制結(jié)構(gòu)文法將下面的語(yǔ)句翻譯成四元式序列： while (A<C A B<D) if (A > 1) C=C+1;else while (A & D)A=A+2;。解：該語(yǔ)句的四元式序列如下(其中E1、E2和E3分別對(duì)應(yīng) ACAB< D、AA1和AWD,并且關(guān)系運(yùn)算符優(yōu)先級(jí)高)：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 (+, C, 1, C)107 (j,_,_,112)108 (j <

48、; ,A,D,110)109 (j,_,_,112)110 (+, A, 2, A)111 (j,_,_,108)112 (j,_,_,100)1135.已知文法 GS為S f aSb|Sb|b,試證明文法 GS為二義文法。證明：由文法GS : SfaSb|Sb|b,對(duì)句子aabbbb對(duì)應(yīng)的兩棵語(yǔ)法樹(shù)為：五.計(jì)算題(10分)已知文法A->aAd|aAb| £判斷該文法是否是 SLR(1)文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串a(chǎn)b#給出分析過(guò)程。解：增加一個(gè)非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有：S'->AA->aAd|aAb| £下 面 構(gòu) 造 它

49、的 LR(0) 項(xiàng) 目 集 規(guī) 范 族 為abd#AIo： sb咽a/詆2予L：Afa 四A->十油AT"皿A,岫Ii： 5'TA'accL：且母地d 且毋aAb A毋LL：A->aA*bL：QaA"%TaA/I ；旦今我卜IExAaAd*IJ且 TaAb*L： 人 aid"從上表可看出，狀態(tài)I0和I2存在移進(jìn)-歸約沖突，該文法不是LR(0)文法。對(duì)于I0來(lái)說(shuō)有：FOLLOW(A)n a=b,d,# 0但二,慚以在I0狀態(tài)下面臨輸入符號(hào)為 a時(shí)移進(jìn)，為b,d,#時(shí) 歸約，為其他時(shí)報(bào)錯(cuò)。對(duì)于 I2來(lái)說(shuō)有也有與I0完全相同的結(jié)論。這就是說(shuō)，以上的移進(jìn) - 歸約沖突是可以解決的，因此該文法是 SLR(1)文法。其SLR(1)分析表為：狀態(tài)ACTIONCOTOabdA0工riT?Is11acc2工l,1TjIs33s.s54H ;T;工；H二5HlIIXlXl對(duì)輸入串a(chǎn)b#合出分析過(guò)程為:步賽狀態(tài)棧符號(hào)程輸入串ACTIOIT(XTO10ab#s：202#3h/工333033s4。羽4聲就bx=1501*acc編譯原理模擬試題六一、是非題（請(qǐng)?jiān)诶ㄌ?hào)內(nèi)，正確的劃M錯(cuò)誤的劃X）（每個(gè)2分，共20分）1