1、編譯原理題庫一、選擇題： 1.編譯原理是對（C）。A、機器語言的執(zhí)行B、匯編語言的翻譯C、高級語言的翻譯D、高級語言程序的解釋執(zhí)行2.編譯程序是將高級語言程序翻譯成D。A、匯編語言程序 B、機器語言程序C、高級語言程序 D、匯編語言或機器語言程序3.文法：G：SxSx | y所識別的語言是（D）。A、xnyxm B、(xyx)*C、x*yx* D、xnyxm（n0）4.設有文法GI：II0|I1|I a|Ic|a|b|c下列符號串中是該文法的句子的有B。ab0 a0c01 aaa bc10 可選項有A、 B、 C、 D、5.詞法分析器的輸出結果是（C）。A、單詞自身值B、單詞在符號表中的位置C

2、、單詞的種別編碼D、單詞的種別編碼和自身值6.為了使編譯程序能夠對程序設計語言進行正確的翻譯，必須采用_C_方法定義程序設計語言。A、非形式化B、自然語言描述問題C、形式化D、自然語言和符號體系相結合7. 若文法G定義的語言是無限集，則文法必然是（C）A.前后文無關文法B.正規(guī)文法C.二義性文法D.遞歸文法8、描述一個語言的文法是B。A、唯一的B、不唯一的C、個數(shù)有限的9、表達式（a+b）*c的逆波蘭表示為_C_A、ab+c* B、abc+* C、a*c+b*c10、遞歸下降分析法和預測分析法要求描述語言的文法是_C_A、正規(guī)文法B、（）文法、LL（1）文法D、右線性文法11編寫一個計算機高級

3、語言的源程序后，到正式上機運行之前，一般要經過_A_這幾步編輯 編譯 連接 運行A、 B、 C、 D、12、符號表的查找一般可以使用_B_：順序查找 折半查找 雜湊查找 排序查找可選項有：A、 B、 C、 D、13、語法分析的常用方法是B：自頂向下 自底向上 自左向右 自右向左 可選項有：A、 B、 C、 D、14、LR語法分析棧中存放的狀態(tài)是識別文法規(guī)范句型_A_的DFA狀態(tài)。A、前綴B、活前綴C、項目D、句柄15、一個確定的有窮自動機DFA是一個A_A、五元組（K，f,，）、四元組（VN，VT，P， S）、四元組（，f,S，Z)D、三元組（VN，VT，P）16、設有文法GE:EE+TTTT

4、*FFF(E)a句型T+T*F+a的素短語是_A_A、a B、E+T C、T D、T+T*F17遞歸下降分析方法屬于_B_A,自左至右B,自頂向下C,自底向上D,自右向左18、文法的二義性和語言的二義性是兩個_A_概念。A、不同B、相同C、無法判斷19、編譯過程中，詞法分析階段的任務是_B_A、識別表達式B、識別語言單詞C、識別語句D、識別程序20、無符號常數(shù)的識別和評數(shù)工作，通常都在B_階段完成。A、詞法分析B、語法分析C、語義分析D、目標代碼生成21、編譯程序中安排優(yōu)化的目的是為了得到_C_的目標代碼A、結構清晰 B、較短C、高效率D、使用存儲空間最小22、代碼優(yōu)化的主要目標是_B_。如何

5、提高目標程序的運行速度如何減少目標程序運行所需的空間。如何協(xié)調和 如何使生成的目標代碼盡可能簡短可選項有：A、 B、 C、 D、23、后綴式iii-/的中綴表達式是_A_A、i(i/(i-i) B、(i-i)/iiC、i (i-i) /I D、(i-i)i/i24字母表中的元素可以是_D_A、字母 B、字母和數(shù)字C、數(shù)字 D、字母、數(shù)字和其他符號25、編譯過程中，比較常見的中間語言有_D_。波蘭表示逆波蘭表示三元式四元式樹形表示可選項有：A、 B、 C、 D、26、正規(guī)式（ab）(ab01)*對應的文法為_C_A、SaAbA B、SaAbA AaA1A AaAbA0A1AC、SaAbA D、S

6、aAbA AaAbA0A1A AAbA0A1A27、在規(guī)則產生式中，符號“”表示_B_A、與 B、或 C、非 D、引導開關參數(shù)28、循環(huán)優(yōu)化是對_A_中的代碼進行優(yōu)化。A、循環(huán) B、函數(shù) C、基本塊 D、整個程序29、設有文法GI：II0|I1|I a|Ic|a|b下列符號串中是該文法的句子的有_B_。ab0 a0c01 aaa cb10 可選項有A、 B、C、 D、30、為了使編譯程序能夠對程序設計語言進行正確的翻譯，必須采用_C_方法定義程序設計語言。A、非形式化 B、自然語言描述問題C、形式化 D、自然語言和符號體系相結合31、無符號常數(shù)的識別和評數(shù)工作，通常都在_B_階段完成。A、詞法

7、分析 B、語法分析 C、語義分析 D、目標代碼生成32、遞歸下降分析法和預測分析法要求描述語言的文法是_C_A、正規(guī)文法 B、（）文法、LL（1）文法 D、右線性文法33、表達式a*（-b+c）的逆波蘭表示為_A_A、abc+* B、abc+* C、a b* +ac 34、文法的二義性和語言的二義性是兩個_A_概念。A、不同 B、相同C、無法判斷35、設有文法GE:EE+TTTT*FFF(E)a句型T+T*F+a的素短語是_A_A、T*F B、E+T C、T D、T+T*F36字母表中的元素可以是_D_A、字母B、字母和數(shù)字C、數(shù)字 D、字母、數(shù)字和其他符號37、編譯過程中，比較常見的中間語言

8、有_D_。波蘭表示逆波蘭表示三元式四元式樹形表示可選項有：A、 B、 C、 D、38、正規(guī)式（ab）(ab01)*對應的文法為_CA、SaAbA B、SaAbA AaA1A AaAbA0A1AC、SaAbA D、SaAbA AaAbA0A1A AAbA0A1A39、在規(guī)則產生式中，符號“”表示_D_A、恒等于B、等于C、取決于D、定義為40、關于短語與句柄，正確的論述是：BA、短語就是句柄B、直接短語才可能是句柄C、左短語一定是句柄D、最右短語一定是句柄二、判斷題（對下列敘述中正確的說法，在題后括號內打“”，錯誤的打“×”，）1、編譯程序是一種常用的應用軟件。 （ × ）2

9、、名字就是標識符，標識符就是名字。（×）3、編譯程序與具體的語言無關。 （ ）4、C語言的編譯程序可以用C語言來編寫。 （ ）5、一個語言的文法是唯一的。 （ × ）2、數(shù)組元素的地址計算與數(shù)組的存儲方式有關。( )6、無左遞歸的文法是（）文法。（×）7、含有優(yōu)化部分的編譯程序的執(zhí)行效率高。 （ × ）8、若兩個正規(guī)式所表示的正規(guī)集相同，則認為二者是等價的。 （ ）9、算符優(yōu)先關系表不一定存在對應的優(yōu)先函數(shù)。 ( × )10、僅考慮一個基本塊，不能確定一個賦值是否真是無用的。( × )11、每個文法都能改寫為LL(1)文法。( 

10、15; )二、填空題1、編譯程序的工作過程一般主要可以劃分為詞法分析 語法分析 語義分析 中間代碼生成 中間代碼優(yōu)化 目標代碼生成。_等幾個基本階段。2、語法分析的任務是：依據(jù)語言的_語法規(guī)則_ ，逐一地分析詞法分析時得到的_單詞符號_，以確定它們是怎樣組成說明和語句的，以及說明和語句是怎樣組成_語法_的。如無語法錯誤，則給出正確的_語法單位_。3、代碼優(yōu)化是_對程序進行 等價變換_ ，提高目標程序的質量。即：使目標代碼運行時所需的時間盡可能_短_，所占用的存儲空間盡可能_少_。4、Chomsky定義的四種形式語言文法分別為：_0型_文法（又稱為_短語_ 文法）、_1型 _文法（又稱為_上下文

11、有關_文法）、_2型_ _文法（又稱為_上下文無關 文法）、_3型_文法（又稱為_正規(guī)(或正則)_文法）。5、在代碼優(yōu)化階段，優(yōu)化的主要方法有：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化_。6、掃描器的任務是從_源程序_中識別出一個個_單詞符號_。 7、所謂最右推導是指：_任何一步Þ都是對中最右非終結符進行替換的_。 8、語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。 9、一個上下文無關文法所含四個組成部分是 一組終結符、一組非終結符、一個開始符號、一組產生式_。 10、所謂語法制導翻譯方法是_為每個產生式配上一個翻譯子程序，并在語法分析的同時執(zhí)行這些子程序_。 11、符號表中的信息

12、欄中登記了每個名字的有關的性質，如_類型、種屬、所占單元大小、地址_等等。 12、一個過程相應的DISPLAY表的內容為 現(xiàn)行的活動記錄的地址和所有外出最新活動的記錄地址 。 13、常用的兩種動態(tài)存貯分配辦法是 棧式 動態(tài)分配和 堆式 動態(tài)分配。 14、產生式是用于定義_語法范疇_的一種書寫規(guī)則。 15、一般程序語言的語法單位有：表達式、語句、分程序、和 函數(shù)、過程、程序 等等。16、語法分析器的任務是在詞法分析識別出單詞符號串的基礎上，分析并判定程序的語法結構是否符合語法規(guī)則。17、若源語言用高級語言編寫的，目標程序是_等價的機器語言程序或匯編程序 ，則其翻譯程序稱為 編譯程序 。18、高級

13、語言經過編譯生成的目標程序一般是_機器語言程序 或_匯編語言程序_19、一個高級語言的源程序在編寫形成后到正式運行前，一般要經過 編輯 、編譯、連接 這三個階段20、假設G是一個文法，S是文法的開始符號，如果SÞ*X，則稱X是句型三、名詞解釋：（每題5分，共20分）1、非終結符出現(xiàn)在文法產生式的左部且能派生出符號或符號串的那些符號稱為非終結符號。2、終結符出現(xiàn)在文法產生式的右部且不能派生出符號或符號串的那些符號稱為終結符號。3 、語法制導翻譯語法制導翻譯就是在語法分析的過程中，當進行推導或歸約時同步完成附加在所使用的產生式上的語義規(guī)則描述的動作，從而實現(xiàn)語義處理。4編譯程序是一種翻譯

14、程序，它將高級語言所寫的源程序翻譯成等價的機器語言或匯編語言的目標程序5掃描遍指編譯程序對源程序或中間代碼程序從頭到尾掃描一次。6自上而下分析法就是指從文法的開始符號出發(fā)，根據(jù)文法規(guī)則正向推導出給定句子的一種方法。7句柄給定句型中的最左簡單短語就是句柄8上下文無關文法若文法G=（VN，VT，P， S）中的每一條規(guī)則的形式為A，其中AÎVN，Î（VNVT），則稱其為上下文無關文法9活前綴規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。 或給定文法規(guī)范句型的可歸前綴的任意首部。4、 簡答1、 何謂二義性文法？試舉例說明。答：若文法G的一個句子對應有兩棵或兩棵以上不同的推導樹

15、，則稱該句子是二義性的。產生二義性句子的文法稱為二義性文法，否則該文法是無二義性的。例子：給定文法G<R>:<R><R>*|<R><R>|a|b考察句子ab*，它有兩棵不同的推導樹，如下所示：2、 設G=（VN,VT,P,<s>)是上下文無關文法，產生式集合P中任意一個產生式應具有一個什么樣的形式？若G是正規(guī)文法呢？答：一般形式為<V>,<V>VN,(VNVT)*若G是正則文法，則一般形式為<A>,<B>或<A>,<A>,<B>VN,aVT

16、(或<A><B>a,<A>a)3,編譯過程的5個階段是什么？答：編譯過程的5個階段：詞法分析，語法分析，語義分析及中間代碼生成，代碼優(yōu)化，目標代碼生成。4，常見的存儲分配策略有幾種？它們都適合于什么性質的語言？答：有三種分配存儲空間的方式：（1） 靜態(tài)分配，若在編譯階段就能確定源程序中各個數(shù)據(jù)實體的存儲空間大小，則可以采用較簡單的靜態(tài)存儲管理。適合靜態(tài)管理的語言應具備條件：數(shù)組上下界是常數(shù)過程調用不允許遞歸，不允許動態(tài)建立數(shù)據(jù)實體。（2） 棧式分配：適用于允許遞歸調用的程序設計語言。（3） 堆式分配：對于允許程序在運行時為變量，動態(tài)申請和釋放存儲空間的語言，

17、采用堆式分配，是最有效的解決方案。5，設有文法GE: EE+TE-TT TT*FTFF F(E)I試證明E+T*F是它的一個句型，指出這個句型的所有短語，直接短語和句柄。答：因為EE+TE+T*F,所以E+T*F是文法GE的句型。短語：E+T*F,T*F,其中T*F是直接短語，也是句柄。6，在一個基本塊內通?？梢詫崿F(xiàn)哪些優(yōu)化？答：（1)合并已知量 （2）刪除公共表達式 （3）刪除無用代碼 （4)復寫傳播 （5）循環(huán)優(yōu)化7，設有文法GA ABCcgDB BbCDE CDaBca DdD EgAfc計算該文法的每一個非終結符的FIRST集和FOLLOW集。答：文法的每一個非終結符的FIRST集和FOLLOW集如下：FIRST(A)=FIRST(BCc)FIRST(gDB) =FIRST(B)FIRST(C)cg =bFIRST(D)ac,g =a,b,c,d,gFIRST(B)=FIRST(bCDE) =b,FIRST(C)=FIRST(DaB)FIRST(ca) =FIRST(D)ac =a,c,dFIRST(D)=FIRST(dD) =d,FIRST(E)=FIRST(gAf)c =g,cFOLLOW(A)=f,FOLLOW(B)=a,c,d,f,g,FOLLOW(C)=c,d,gFOLLOW(D)=a,b,c,g,f,FOLLOW(E)=a,c,