西安交通大學15年7月編譯原理考查課試題

西安交通大學15年7月編譯原理》考查課試題一、選擇題描述一個語言的文法是（B）唯一的B.不唯一的C.可能唯一，也可能不唯一若文法G定義的語言是無限集，則文法必然是（D）A.前后文無關文法B.正規(guī)文法C.二義性文法D.遞歸文法數(shù)組的內(nèi)情向量中肯定不含數(shù)組的（B）信息A.維數(shù)B.類型C.各維的上下界D.各維的界差簡單優(yōu)先分析每次歸約的是（C）A.最左直接短語B.直接短語C.最左素短語D.控制結(jié)點最適合動態(tài)建立數(shù)據(jù)實體的內(nèi)存分配方式是（B）A.棧式分配B.堆式分配C.編譯時預先分配D.以上三種均可文法G產(chǎn)生的（D）的全體是該文法描述的語言。A.句型B.終結(jié)符集C.非終結(jié)符集D.句子若文法G定義的語言是無限集，則文法必然是 （A）:A.遞歸的B前后文無關的C二義性的D無二義性的Chomsky定義的四種形式語言文法中，0型文法又稱為（A）文法；1型文法又稱為（C）文法；2型語言可由（G）識別。A.短語結(jié)構文法B前后文無關文法C前后文有關文法D正規(guī)文法E圖靈機F有限自動機G下推自動機.一個文法所描述的語言是 （A）;描述一個語言的文法是（B）。A.唯一的B不唯一的C可能唯一，好可能不唯一.數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的 （A）的信息A.維數(shù)B.類型C.維上下界D.各維的界差.在下述的編譯方法中，自底向上的方法有 （F），自頂向下的分析方法有（A）。①簡單優(yōu)先分析②算符優(yōu)先分析③遞歸下降分析④預測分析技術LR（K）分析SLR（k）分析⑦LL（k）分析⑧LALR（K）分析A.③④⑦B.③④⑧C.①②⑧D.③④⑤⑥⑦E.①②⑤⑥⑦F①②⑤⑥⑧下推自動機識別的語言是（C）A.0型語言 B.1型語言C.2型語言 C.3型語言常見的中間代碼形式不含（D）A.三元式 B.四元式C.逆波蘭式 D.語法樹語言是（A）的集合A.句子 B.產(chǎn)生式C.符號串 D.句型掃描器所完成的任務是從字符串形式的源程序中識別出一個個具有獨立含義的最小語法單位即（B）D.A.字符 B.單詞 C.句子D.句型代碼優(yōu)化的目的是（C）A.節(jié)省時間 B.節(jié)省空間C.節(jié)省時間和空間 D.把編譯程序進行等價交換代碼生成階段的主要任務是（C）把高級語言翻譯成匯編語言把高級語言翻譯成機器語言把中間代碼變換成依賴具體機器的目標代碼把匯編語言翻譯成機器語言二、 判斷正誤TOC\o"1-5"\h\z1、算符優(yōu)先關系表不一定存在對應的優(yōu)先函數(shù)。 V2、數(shù)組元素的地址計算與數(shù)組的存儲方式有關。 V3、僅考慮一個基本塊，不能確定一個賦值是否真是無用的。 V4、 每個文法都能改寫為LL（1）文法。X5、 對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動態(tài)貯存分配策略。X三、 填空題1、從功能上說，程序語言的語句大體可分為 語句和 語句兩大類。（執(zhí)行性、說明性）2、掃描器的任務是從 中識別出一個個 。（源程序、單詞符號）4、語法分析最常用的兩類方法是 和 分析法。（自上而下、自下而上）5、一個上下文無關文法所含四個組成部分是 。（一組終結(jié)符號，一組非終結(jié)符號、一個開始符號、一組產(chǎn)生式）6、所謂語法制導翻譯方法是 。（為每個產(chǎn)生式配上一個翻譯子程序，并在語法分析的同時執(zhí)行這些子程序 ）四、簡答題1、 什么是遍（指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次）2、 什么是語法分析（按文法的產(chǎn)生式識別輸入的符號串是否為一個句子的分析過程）3、 什么是后綴式（一種把運算量寫在前面，把算符寫在后面的表示表達式的方法）4、 編譯程序與解釋程序有何區(qū)別？答：二者的工作方法不同，后者是邊解釋邊執(zhí)行，解釋所得的代碼并不保存；前者是先將高級語言翻譯感情上標代碼，將其保存到指定的空間中，待需要時再執(zhí)行之，甚至可以在案一個機器上編譯，而在另一臺機器上執(zhí)行。5、 何謂素短語？答：素短語是滿足下述條件的短語：（1）它至少含有一個終結(jié)符號（2）滿足條件（1）的最小”短語6、 過程調(diào)用時，主調(diào)程序與被調(diào)程序之間的信息傳遞有哪些方式？答：形式參數(shù)與實在參數(shù)結(jié)合方式傳遞（簡稱參數(shù)傳遞）、返回值傳遞、共享數(shù)據(jù)區(qū)傳遞。7、 何謂語法制導翻譯？答：語法制導翻譯是對前后文無關文法的擴充，即對文法中的每個產(chǎn)生式都附加一個語義動作或語義子程序，且在語法分析過程中，每當需要使用一個產(chǎn)生式進行推導或歸約時，語法分析程序除執(zhí)行相應的語法分析動作外，還要執(zhí)行相應的語義動作或調(diào)用相應的語義子程序，完成相應的語義分析和翻譯工作。&何謂算符文法？答：當一個文法的所有產(chǎn)生式的右部均不出現(xiàn)兩個非終結(jié)符號相鄰的情況時，該就被稱為算符文法。9、常見的存儲分配策略有幾種？它們都適合于什么性質(zhì)的語言？有三種分配存儲空間的方式：（1）靜態(tài)分配若在編譯階段就能確定源程序中各個數(shù)據(jù)實體的存儲空間大小，則可以采用較簡單的靜態(tài)存儲管理。適合靜態(tài)管理的語言應具備條件：數(shù)組上下界是常數(shù)、過程調(diào)用不允許遞歸、不允許動態(tài)建立數(shù)據(jù)實體。 （2）棧式分配適用于允許遞歸調(diào)用的程序設計語言；（3）堆式分配對于允許程序在運行時為變量動態(tài)申請和釋放存儲空間的語言，采用堆式分配是最有效的解決方案。10、常見循環(huán)優(yōu)化都有哪些項目？不變運算外提；運算強度削弱；消除歸納變量；下標變量地址計算優(yōu)化。11、 什么是活動記錄？它主要由哪些內(nèi)容構成？一個過程的一次執(zhí)行所需信息的管理，是通過稱為活動記錄的連續(xù)存儲塊來實現(xiàn)的?；顒佑涗浀闹饕獌?nèi)容有：（1）臨時變量域存放目標程序臨時變量的值；（2）局部數(shù)據(jù)域存放過程本次執(zhí)行時的局部數(shù)據(jù)、簡單變量及數(shù)組內(nèi)情向量等；（3）機器狀態(tài)域保存在調(diào)用過程前有關機器狀態(tài)的信息，包括各寄存器的當前值及返回地址等；（4）存取鏈為訪問其它活動記錄中所存放的非局部數(shù)據(jù)所提供的鏈地址；（5）控制鏈指向主調(diào)過程的活動記錄；（6）實參存放主調(diào)過程為被調(diào)用過程所提供的實參信息； （6）返回值為主調(diào)過程存放被調(diào)過程的返回值12、 目標代碼有哪幾種形式？生成目標代碼時通常應考慮哪幾個問題？答：目標代碼通常米用三種形式：機器語言，匯編語言，待裝配機器語言模塊。應著重考慮的問題：（1） 如何使生成的目標代碼較短；（2） 如何充分利用寄存器，以減少訪問內(nèi)存次數(shù)；（3） 如何充分利用指僅系統(tǒng)的的特點。13、 何謂二義性文法？試舉一例說明。答：若文法G的一個句子對應有兩棵或兩棵以上不同的推導樹，則稱該句子是二義性的。產(chǎn)生二義性句子的文法稱為二義性文法， 否則該文法是無二義性的。例子：給定文法G[<R>]:<R>—<R>*|vR>vR>|a|b考察句子ab*，它有兩棵不同的推導樹，如下所示：14、 在一個基本塊內(nèi)通?？蓪崿F(xiàn)哪些優(yōu)化？答：①合并已知量刪除公共子表達式刪除無用代碼復寫傳播15、設G=(VN,VT,P,<S>)是上下文無關文法，產(chǎn)生式集合P中任意一個產(chǎn)生式應具有什么樣的形式？若G是正則文法呢？答：一般形式為<v>，―<v>(VNUVT)*。 ：VN,若G是正則文法，則一般形式為<A>—a<B>或<A>—a,<A>、<B>VT(或€VN,a*A>—<B>a,<A>—a)。五、綜合題1、考慮下面程序Vara:integer；ProcedureS(X);VarX：integer;Begina：=a+1;X：=a+XEnd;Begina：=5;S(a);Print(a)End.試問：若參數(shù)傳遞方式分別采取傳名和傳值時，程序執(zhí)行后輸出a的值是什么？答：傳名：a=12傳值：a=62、寫出表達式(a+b*c)/(a+b)—d的逆波蘭表示及三元式序列。答：逆波蘭表示：abc*+ab+/d—三元式序列：(*,b,c)(+,a,①)|(+,a,b)(/，②，③)

(―，④，d)3、已知文法G(S)S-a|A|(T)T—T,S|S寫出句子((a,a),a)的規(guī)范歸約過程及每一步的句柄答：句型歸約規(guī)則句柄((a，a)，a)S—aa((S，a)，a)T—SS((T，a)，a)S—aa((T，S)，a)T—T,ST,S((S)，a)T—SS((T)，a)S—S(T)(T)(S，a)T—SS(T，a)S—aa(T，S)T—T,ST,S(T)S—(T)(T)S4、設L{ab,c}*是滿足下述條件的符號串構成的語言：若出現(xiàn)a,則其后至少緊跟兩個c；若出現(xiàn)b，其后至少緊跟一個c。試構造識別L的最小化的DFA，并給出描述L的正規(guī)表達式DFA如圖所示。相應的正規(guī)式為(c|acc|bc)*。5、 將下面的條件語句表示成四元式序列：ifa>bthenx:=a+b*celsex:=b-a;四元式：(1)(j>,a,b,(3))⑵(j,,,(7))⑶(*,b,c,T1)⑷(+,a,T1,T2)(：=,T2,,x)(j,,,(9))⑺(-,b,a,T3)(:=,T3,,x)(……)0開頭。6、 寫一個文法，使其語言是奇數(shù)集，且每個奇數(shù)不以解：文法G(N)0開頭。N—AB|BA—AC|DB—1|3|5|7|9D—B|2|4|6|8C—0|D7、 設文法G(S):S—(L)|aS|a

L—L,S|S消除左遞歸和回溯；計算每個非終結(jié)符的FIRST和FOLLOW;解嚴1)S—(L)|aS'S'—S|￡L—SL'L'—SL'|￡FOLLOW(S)=FOLLOW(S)={#,,,)}FOLLOW(S')={#,,,)}FOLLOW(L)={)}FOLLOW(L〕={)}FIRST)S)={(,a}FIRST(S')={,a,門FIRST(L)={(,a}FIRST(L')={,,門&Whilea>0Vbv0doBeginX:=X+1;ifa>0thena:=a—1elseb:=b+1End;翻譯成四元式序列解:(1)(j>,a,0,5)(2)(j，—,―,3)(+,X,1,T1)(:=,T1X)(j,a,0,9)(j,-,-,12)(-,a,1,T2)(:=,T2，-,a)(j,-,-,