編譯原理自測(一、二、三)及答案復(fù)習(xí)過程

1、編譯原理自測一一、是非題（下列各題，你認為正確的，請在題干的括號內(nèi)打“vf錯的打“X。每題1分 ,共 5 分 ）1、算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。 正確2、數(shù)組元素的地址計算與數(shù)組的存儲方式有關(guān)。 .正確3、 僅考慮一個基本塊，不能確定一個賦值是否真是無用的。正確4、每個文法都能改寫為 LL（1） 文法。 不正確5、對于數(shù)據(jù)空間的存貯分配， FORTRAN 采用動態(tài)貯存分配策略。 不正確二、填空題1 、 從功能上說， 程序語言的語句大體可分為 （執(zhí)行性） 語句和 （說明性） 語句兩大類。2、 掃描器的任務(wù)是從（源程序）中識別出一個個（單詞符號）。3、所謂最右推導(dǎo)是指：（任何一步af都

2、是對a中最右非終結(jié)符進行替換的）。4、語法分析最常用的兩類方法是（自上而下）和（自下而上）分析法。5、一個上下文無關(guān)文法所含四個組成部分是 （一組終結(jié)符號，一組非終結(jié)符號、一 個開始符號、一組產(chǎn)生式 ）。6、所謂語法制導(dǎo)翻譯方法是 （為每個產(chǎn)生式配上一個翻譯子程序，并在語法分析的 同時執(zhí)行這些子程序 ）。7、符號表中的信息欄中登記了每個名字的有關(guān)的性質(zhì)，如（類型、種屬、？）等 等。8、一個過程相應(yīng)的 DISPLAY 表的內(nèi)容為（現(xiàn)行活動記錄） 。9、 常用的兩種動態(tài)存貯分配辦法是（棧式）動態(tài)分配和（堆式）動態(tài)分配。10、產(chǎn)生式是用于定義 （語法范疇 ）的一種書寫規(guī)則。三、名詞解釋1遍指編譯程序

3、對源程序或中間代碼程序從頭到尾掃描一次。2. 無環(huán)路有向圖（DAG）如果有向圖中任一通路都不是環(huán)路， 則稱廬有向圖為 無環(huán)路有向圖，簡稱 DAG。3. 語法分析按文法的產(chǎn)生式識別輸入的符號串是否為一個句子的分析過程。4短語令G是一個文法。S劃文法的開始符號，假定 a f S是文法G的一 個句型，如果有Sa AS且AB則稱f是句型a f相對非終結(jié)符A的短語。5.后綴式一種把運算量寫在前面，把算符寫在后面的表示表達式的方法。編譯原理自測二、是非題（下列各題，你認為正確的，請在題干的括號內(nèi)打“V”錯的打“X”每題1分,共5分）1、一個 LL（1） 文法一定是無二義的。 .正確2、 逆波蘭法表示的表達

4、式亦稱前綴式。.不正確3、 目標代碼生成時，應(yīng)考慮如何充分利用計算機的寄存器的問題。.正確4、 正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。.正確5、一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認為是初態(tài)，最多只有一個終態(tài) 。不正確二、填空題1、語法分析是依據(jù)語言的 （語法）規(guī)則進行的，中間代碼產(chǎn)生是依據(jù)語言的 （語 義）規(guī)則進行的 。2、程序語言的單詞符號一般可以分為（ 基本字、標識符、常量、算符、界符 ） 等等。3、語法分析器的輸入是 （單詞符號串），其輸出是 （語法單位）4、所謂自上而下分析法是指（ 從開始符號出發(fā)，向下推導(dǎo)，推出句子 ）。5、如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹

5、， 則稱這個文法是 （二義 的）。6對于文法G僅含終結(jié)符號的句型稱為（句子）。7、逆波蘭式 ab+c+d*e- 所表達式為 （）。8、一個名字的屬性包括 （類型）和（作用域）。9、對于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRA采用（靜態(tài)存儲分配）策略，PASCAL 采用 （動態(tài)存儲分配）策略。10、所謂優(yōu)化是指（ 對程序進行各種等價變換，使得從變換后的程序出發(fā)，能生 成更有效的目標代碼 ）。三、 名詞解釋1詞法分析器指執(zhí)行詞法分析的程序。2語法一組規(guī)則，用它可以形成和產(chǎn)生一個合式的程序3最右推導(dǎo)指對于一個推導(dǎo)序列中的每一步直接推導(dǎo)，被替換的總是當(dāng)前 符號串中的最右非終結(jié)符號。4語法制導(dǎo)翻譯在語法分析過程

6、中，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序 進行翻譯的辦法叫做語法制導(dǎo)翻譯。學(xué)習(xí)-好資料5 基本塊一一指程序中一個順序執(zhí)行的語句序列，其中只有一個入口，一個出 口，入口即第一個語句。出口即最后一個語句。編譯原理自測三一選擇題（每空2分，共20分）1文法 G產(chǎn)生的 的全體是該文法描述的語言。DA.句型廣B.終結(jié)符集C.非終結(jié)符集燈 D.句子2、 若文法 G定義的語言是無限集，則文法必然是：A蔣 A.遞歸的廠B.前后文無關(guān)的廠 C.二義性的 D.無二義性的3、 Chomsky定義的四種形式語言文法中，0型文法又稱為 A文法；1型文法又稱為 C文法；2型語言可由 G識別?！?A.短語結(jié)構(gòu)文法B.前后文無關(guān)

7、文法廠C前后文有關(guān)文法"D.正規(guī)文法廠E.圖靈機廠F有限自動機廠G.下推自動機A.短語結(jié)構(gòu)文法B.前后文無關(guān)文法C.前后文有關(guān)文法D.正規(guī)文法E.圖靈機廠F有限自動機廠G.下推自動機“ A.短語結(jié)構(gòu)文法"B.前后文無關(guān)文法" C.前后文有關(guān)文法" D.正規(guī)文法CE.圖靈機廠F有限自動機"G.下推自動機4、 一個文法所描述的語言是A ;描述一個語言的文法是B。rrA.唯一的 B.不唯一的C.可能唯一，可能不唯一A.唯一的* B.不唯一的C.可能唯一，可能不唯一5、數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的A的信息A.維數(shù)廠B.類型廠C.維上下界"

8、 D.各維的界差6、在下述的編譯方法中，自底向上的方法有F，自頂向下的分析方法有A。簡單優(yōu)先分析算符優(yōu)先分析遞歸下降分析預(yù)測分析技術(shù)LR（ K）分析 SLR（ k）分析 LL（ k）分析 LALR（ K）分析A.廠B.廠 C. D.學(xué)習(xí)-好資料E."F.A.廠B.廠C.廠D.E.廠F.簡答題1 . LL ( 1 )分析法對文法有哪些要求?對于G中的每個產(chǎn)生式 A -Y 1 | 丫 2 | 丫 m ,其各候選式均應(yīng)滿足：(1)不同的候選式不能推出以同一終結(jié)符號打頭的符號串，即FIRST( 丫i ) n FIRST( 丫 j )=©( 1 < i , j < m ；

9、 i j )(2)若有丫 j £ ,則其余候選式丫 i所能推出的符號串不能以 FOLLOW(A)中的終結(jié)符號開始，即有FIRST( 丫 i ) n FOLLOW(A)邛(i < 1 ,2,，m ; i 工 j)2 .常見的存儲分配策略有幾種？它們都適合于什么性質(zhì)的語言?有三種分配存儲空間的方式：(1 )靜態(tài)分配若在編譯階段就能確定源程序中各個數(shù)據(jù)實體的存 儲空間大小，則可以采用較簡單的靜態(tài)存儲管理。 適合靜態(tài)管理的語言應(yīng)具備條 件：數(shù)組上下界是常數(shù)、過程調(diào)用不允許遞歸、不允許動態(tài)建立數(shù)據(jù)實體。(2 )棧式分配適用于允許遞歸調(diào)用的程序設(shè)計語言 ；(3 )堆式分配對于允許程序在運行時為變量動態(tài)申請和釋放存儲 空間的語言，采用堆式分配是最有效的解決方案。3 .常見循環(huán)優(yōu)化都有哪些項目？不變運算外提；運算強度削弱；消除歸納變量；下標變量地址計算優(yōu)化4 .什么是活動記錄？它主要由哪些內(nèi)容構(gòu)成?一個過程的一次執(zhí)行所需信息的管理，是通過稱為 活動記錄 的連續(xù)存儲塊來實 現(xiàn)的。活動記錄的主要內(nèi)容有：（ 1 ） 臨時變量域 存放目標程序臨時變量的值；（ 2 ）局部數(shù)據(jù)域 存放過程本次執(zhí)行時的局部數(shù)據(jù)、簡單變量及數(shù)組內(nèi)情向量等；（ 3 ）