編譯原理復(fù)習(xí)題

1、填空題 1按Chomsky分類法，文法按照_規(guī)則定義的形式_進(jìn)行分類。 2詞法分析基于_正則_文法進(jìn)行，即識(shí)別的單詞是該類文法的句子。 3分析句型時(shí)，應(yīng)用算符優(yōu)先分析技術(shù)時(shí)，每步被直接歸約的是_最左素短語_，而應(yīng)用LR分析技術(shù)時(shí)，每步被直接歸約的是_句柄_。 4掃描器是_詞法分析器_，它接受輸入的_源程序_，對(duì)源程序進(jìn)行_詞法分析_并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語法分析器使用。5 一個(gè)文法能用有窮多個(gè)規(guī)則描述無窮的符號(hào)串集合（語言）是因?yàn)槲姆ㄖ写嬖谟衉遞歸_定義的規(guī)則。 6 語義分析階段所生成的與源程序等價(jià)的中間表示形式可以有_逆波蘭_、_四無式表示_與_三元式表示_等。7

2、編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義分析,中間代碼生成,代碼優(yōu)化等幾個(gè)基本階段,同時(shí)還會(huì)伴有_表格處理_和 _出錯(cuò)處理_。 8從功能上說，程序語言的語句大體可分為_執(zhí)行性_語句和_說明性_語句兩大類。 9計(jì)算機(jī)執(zhí)行用高級(jí)語言編寫的程序主要有兩種途徑：_解釋_和_編譯_。 10一個(gè)LR分析器包括兩部分：一個(gè)總控程序和_一張分析表_。 11語法分析基于_上下文無關(guān)_文法進(jìn)行，即識(shí)別的是該類文法的句子。語法分析的有效工具是_語法樹_。 12在使用高級(jí)語言編程時(shí),首先可通過編譯程序發(fā)現(xiàn)源程序的全部_語法_錯(cuò)誤和語義部分錯(cuò)誤。13編譯方式與解釋方式的根本區(qū)別在于_是否生成目標(biāo)代碼_。

3、14 遞歸下降法不允許任一非終極符是直接_左_遞歸的。 15局部優(yōu)化是在_基本塊_范圍內(nèi)進(jìn)行的一種優(yōu)化。 16一個(gè)典型的編譯程序中，不僅包括_詞法分析_、_語法分析_、_中間代碼生成_、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。 17語法分析器的輸入是_單詞符號(hào)串_，其輸出是_語法單位_。 18自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行_直接歸約_ ，力求歸約到文法的_開始符號(hào)_。 19產(chǎn)生式是用于定義_語法成分_的一種書寫規(guī)則。 20對(duì)編譯程序而言,輸入數(shù)據(jù)是_源程序_, 輸出結(jié)果是_目標(biāo)程序_。21 若源程序是用高級(jí)語言編寫的,

4、_目標(biāo)程序_是機(jī)器語言程序或匯編程序,則其翻譯程序稱為 _編譯程序_ 。 22一個(gè)句型中的最左簡單短語稱為該句型的_句柄_。 23語法分析是依據(jù)語言的_語法_規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的_語義_規(guī)進(jìn)行的。 24自頂向下的語法分析方法的基本思想是：從文法的_開始符號(hào)_開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行_直接推導(dǎo)_，試圖推導(dǎo)出文法的_句子_，使之與給定的輸入串_匹配_。 25常用的參數(shù)傳遞方式有_傳地址_，傳值和傳名。 26對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為 _語義規(guī)則_ 。 27掃描器的任務(wù)是從_源程序_中識(shí)別出一個(gè)個(gè)_單詞符號(hào)_。 28一個(gè)名字

5、的屬性包括_類型_和_作用域_。 29語法分析最常用的兩類方法是_自上而下_和_自下而上_分析法。 30自上而下分析法采用_移進(jìn)_、歸約、錯(cuò)誤處理、_接受_等四種操作。一、選擇1.將編譯程序分成若干個(gè)“遍”是為了B. 使程序的結(jié)構(gòu)更加清晰。A. 提高程序的執(zhí)行效率B. 使程序的結(jié)構(gòu)更加清晰C. 利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率D. 利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率2.正規(guī)式 MI 和 M2 等價(jià)是指_C. M1 和 M2 所識(shí)別的語言集相等 A. MI 和 M2 的狀態(tài)數(shù)相等B. Ml 和 M2 的有向弧條數(shù)相等。C. M1 和 M2 所識(shí)別的語言集相等 D. Ml 和 M2 狀

6、態(tài)數(shù)和有向弧條數(shù)相等3.中間代碼生成時(shí)所依據(jù)的是 _C語義規(guī)則。A語法規(guī)則 B詞法規(guī)則 C語義規(guī)則 D等價(jià)變換規(guī)則4.一個(gè)編譯程序中，不僅包含詞法分析，_A語法分析_，中間代碼生成，代碼優(yōu)化， 目標(biāo)代碼生成等五個(gè)部分。A語法分析 B文法分析 C語言分析 D解釋分析 5.語法分析器則可以發(fā)現(xiàn)源程序中的_D語法錯(cuò)誤_。A語義錯(cuò)誤 B語法和語義錯(cuò)誤C錯(cuò)誤并校正 D語法錯(cuò)誤6.解釋程序處理語言時(shí) , 大多數(shù)采用的是_B先將源程序轉(zhuǎn)化為中間代碼 , 再解釋執(zhí)行_方法。A源程序命令被逐個(gè)直接解釋執(zhí)行B先將源程序轉(zhuǎn)化為中間代碼 , 再解釋執(zhí)行C先將源程序解釋轉(zhuǎn)化為目標(biāo)程序 , 再執(zhí)行D以上方法都可以7.如果

7、L(M1)=L(M2)，則M1與M2( A等價(jià) )A等價(jià) B都是二義的C都是無二義的 D它們的狀態(tài)數(shù)相等8.有限狀態(tài)自動(dòng)機(jī)能識(shí)別(C正規(guī)文法 )A上下文無關(guān)文法 B上下文有關(guān)文法C正規(guī)文法 D短語文法9.由文法的開始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號(hào)序列是(C句型 )A短語 B句柄 C句型 D句子10.產(chǎn)生正規(guī)語言的文法為(D3型 )A0型 B1型 C2型 D3型11.任何算符優(yōu)先文法(D可能有若干個(gè) )優(yōu)先函數(shù)A有一個(gè) B沒有 C有若干個(gè) D可能有若干個(gè)12.采用自上而下分析，必須( C消除回溯 )A消除左遞歸 B消除右遞歸C消除回溯 D提取公共左因子13.在規(guī)范歸約中，用(B句柄 )來刻畫可

8、歸約串。A直接短語 B句柄 C最左素短語 D素短語14.如果文法是無二義的，那么規(guī)范歸約是指( B最右推導(dǎo)的逆過程 )A最左推導(dǎo)的逆過程 B最右推導(dǎo)的逆過程C規(guī)范推導(dǎo) D最左歸約的逆過程15.使用間接三元式表示法的主要目的(A便于優(yōu)化處理 )A便于優(yōu)化處理 B便于表的修改C節(jié)省存儲(chǔ)空間 D生成中間代碼更容易16.文法 G 所描述的語言是_(C由文法的開始符號(hào)推出的所有終極符串)_的集合。A. 文法 G 的字母表 V 中所有符號(hào)組成的符號(hào)串B文法 G 的字母表 V 的閉包 V* 中的所有符號(hào)串C由文法的開始符號(hào)推出的所有終極符串D. 由文法的開始符號(hào)推出的所有符號(hào)串17.文法分為四種類型，即 0

9、 型、1 型、2 型、3 型。其中 3 型文法是_B正則文法 _。 A. 短語文法B正則文法 C上下文有關(guān)文法 D上下文無關(guān)文法18. 一個(gè)上下文無關(guān)文法 G 包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一 組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組 _D產(chǎn)生式_。A句子 B句型 C單詞 D產(chǎn)生式19.通常一個(gè)編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目 標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括_C表格處理和出錯(cuò)處理_。A模擬執(zhí)行器 B解釋器C表格處理和出錯(cuò)處理 D符號(hào)執(zhí)行器20.一個(gè)句型中的最左_B簡單短語 _稱為該句型的句柄。A短語 B簡單短語 C素短語 D終結(jié)符號(hào)21.若一個(gè)文法是遞歸

10、的，則它所產(chǎn)生的語言的句子_A是無窮多個(gè) _。A是無窮多個(gè) B. 是有窮多個(gè)C是可枚舉的 D個(gè)數(shù)是常量22.詞法分析器用于識(shí)別_C單詞 _。A句子 B句型 C單詞 D產(chǎn)生式23.在自底向上的語法分析方法中，分析的關(guān)鍵是_A. 尋找句柄 _。A. 尋找句柄 B. 尋找句型 C. 消除遞歸 D. 選擇候選式24.在 LR 分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型_C. 活前綴 _的 DFA 狀態(tài)。A. 句柄 B. 前綴 C. 活前綴 D. LR(0) 項(xiàng)目25.若文法 G 定義的語言是無限集，則文法必然是 _A遞歸的 _A遞歸的 B前后文無關(guān)的C二義性的 D無二義性的26.四種形式語言文法中，1

11、 型文法又稱為 _A短語結(jié)構(gòu)文法 _文法。A短語結(jié)構(gòu)文法 B前后文無關(guān)文法C前后文有關(guān)文法 D正規(guī)文法27._B中間代碼生成_和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。A語法分析 B中間代碼生成C詞法分析 D目標(biāo)代碼生成28._B解釋程序和編譯程序_是兩類程序語言處理程序。A高級(jí)語言程序和低級(jí)語言程序 B解釋程序和編譯程序C編譯程序和操作系統(tǒng)D系統(tǒng)程序和應(yīng)用程序29.文法分為四種類型，即 0 型、1 型、2 型、3 型。其中 2 型文法是_D上下文無關(guān)文法_。A. 短語文法 B正則文法C上下文有關(guān)文法 D上下文無關(guān)文法30._ABASIC語言 _是一種典型的解釋型語言。ABASIC語言 BC語言

12、 CFORTRAN語言DPASCAL語言 31.與編譯系統(tǒng)相比，解釋系統(tǒng)_D比較簡單 , 可移植性好 , 執(zhí)行速度慢_。A比較簡單 , 可移植性好 , 執(zhí)行速度快B比較復(fù)雜 , 可移植性好 , 執(zhí)行速度快C比較簡單 , 可移植性差 , 執(zhí)行速度慢D比較簡單 , 可移植性好 , 執(zhí)行速度慢32.用高級(jí)語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫_B目標(biāo)程序_。A源程序 B目標(biāo)程序 C連接程序 D解釋程序 33.把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由_A編譯器_完成的。A編譯器 B匯編器C解釋器 D預(yù)處理器 34.如果文法 G 是無二義的，則它的任何句子_A最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同

13、_。A最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同 B最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同 C最左推導(dǎo)和最右推導(dǎo)必定相同D可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語法樹相同 35.構(gòu)造編譯程序應(yīng)掌握_D以上三項(xiàng)都是_。A源程序 B目標(biāo)語言C編譯方法 D以上三項(xiàng)都是36.四元式之間的聯(lián)系是通過_B臨時(shí)變量_實(shí)現(xiàn)的。A指示器 B臨時(shí)變量C符號(hào)表 D程序變量37.表達(dá)式( A B)(CD)的逆波蘭表示為_BA BCD_。A. ABCD BA BCDCAB CD DA B CD38.優(yōu)化可生成_D運(yùn)行時(shí)間短且占用存儲(chǔ)空間小_的目標(biāo)代碼。A運(yùn)行時(shí)間較短B占用存儲(chǔ)空間較小C運(yùn)行時(shí)間短但占用內(nèi)存空間大 D運(yùn)行時(shí)

14、間短且占用存儲(chǔ)空間小39.下列_C刪除多余運(yùn)算 _優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。A. 強(qiáng)度削弱 B刪除歸納變量C刪除多余運(yùn)算 D代碼外提40.編譯程序使用_B說明標(biāo)識(shí)符的過程或函數(shù)的靜態(tài)層次_區(qū)別標(biāo)識(shí)符的作用域。 A. 說明標(biāo)識(shí)符的過程或函數(shù)名B說明標(biāo)識(shí)符的過程或函數(shù)的靜態(tài)層次C說明標(biāo)識(shí)符的過程或函數(shù)的動(dòng)態(tài)層次 D. 標(biāo)識(shí)符的行號(hào)41.編譯程序絕大多數(shù)時(shí)間花在_D表格管理_ 上。 A出錯(cuò)處理 B詞法分析 C目標(biāo)代碼生成 D表格管理42.編譯程序是對(duì)_D高級(jí)語言的翻譯_。A匯編程序的翻譯 B高級(jí)語言程序的解釋執(zhí)行C機(jī)器語言的執(zhí)行 D高級(jí)語言的翻譯43.在規(guī)范歸約中，用_B句柄_來刻畫可歸約串。

15、A直接短語B句柄C最左素短語D素短語44.間接三元式表示法的優(yōu)點(diǎn)為_A采用間接碼表，便于優(yōu)化處理_。A采用間接碼表，便于優(yōu)化處理 B節(jié)省存儲(chǔ)空間，不便于表的修改C便于優(yōu)化處理，節(jié)省存儲(chǔ)空間 D節(jié)省存儲(chǔ)空間，不便于優(yōu)化處理45.基本塊內(nèi)的優(yōu)化為_B刪除多余運(yùn)算，刪除無用賦值_。A. 代碼外提，刪除歸納變量 B刪除多余運(yùn)算，刪除無用賦值C強(qiáng)度削弱，代碼外提 D循環(huán)展開，循環(huán)合并46.在目標(biāo)代碼生成階段，符號(hào)表用_D地址分配_。A目標(biāo)代碼生成B語義檢查 C語法檢查 D地址分配47.堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守_D. 任意_原則。A. 先請(qǐng)先放 B先請(qǐng)后放C后請(qǐng)先放 D. 任意48.文法 G 產(chǎn)

16、生的_D. 句子_ 的全體是該文法描述的語言。A. 句型B. 終結(jié)符集C. 非終結(jié)符集D. 句子49.一個(gè)文法所描述的語言是_A. 唯一的_ A. 唯一的B. 不唯一的C. 可能唯一,D. 可能不唯一50.描述一個(gè)語言的文法是_B. 不唯一的_ 。A. 唯一的B. 不唯一的C. 可能唯一D. 可能不唯一51.數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的_A. 維數(shù)_的信息A. 維數(shù)B. 類型C. 維上下界D. 各維的界差52.兩個(gè)有窮自動(dòng)機(jī)等價(jià)是指它們的 C所識(shí)別的語言相等 。A狀態(tài)數(shù)相等 B有向弧數(shù)相等C所識(shí)別的語言相等D狀態(tài)數(shù)和有向弧數(shù)相等53.設(shè)a,b,c為文法的終結(jié)符，且有優(yōu)先關(guān)系aºb

17、和bºc，則 D選項(xiàng)A、B和C都不一定成立 。A必有aºc B必有cºa C必有bºa D選項(xiàng)A、B和C都不一定成立54.生成中間代碼時(shí)所依據(jù)的是 C語義規(guī)則 。A語法規(guī)則 B詞法規(guī)則 C語義規(guī)則 D等價(jià)變換規(guī)則55.基本塊 A只有一個(gè)入口語句和一個(gè)出口語句 A只有一個(gè)入口語句和一個(gè)出口語句 B有一個(gè)入口語句和多個(gè)出口語句C有多個(gè)入口語句和一個(gè)出口語句 D有多個(gè)入口語句和多個(gè)出口語句56.若a為終結(jié)符，則A a.ab為_A. 移進(jìn)項(xiàng)目_A. 移進(jìn)項(xiàng)目 B. 歸約項(xiàng)目 C. 接受項(xiàng)目 D. 后繼項(xiàng)目57.同心集的合并不會(huì)產(chǎn)生_C. 移進(jìn)/移進(jìn)沖突_A. 二

18、義沖突 B. 移進(jìn)/歸約沖突C. 移進(jìn)/移進(jìn)沖突 D. 歸約/歸約沖突58.在程序運(yùn)行前就確定所需的數(shù)據(jù)空間的存儲(chǔ)分配方法是_A. 靜態(tài)的A. 靜態(tài)的 B. 動(dòng)態(tài)的 C. 棧式的 D. 堆式的59. B. 1型文法也稱為上下文有關(guān)文法。A. 0 B. 1 C. 2 D. 360.確定有限自動(dòng)機(jī)的化簡是要實(shí)現(xiàn) _A. 狀態(tài)最少化 _ 。A. 狀態(tài)最少化 B. 轉(zhuǎn)換函數(shù)確定化C. 符號(hào)最少化 D. 邊的最少化61.局部優(yōu)化是對(duì) D. 基本塊 進(jìn)行的優(yōu)化。A. 表達(dá)式 B. 部分代碼 C. 循環(huán)體 D. 基本塊62.由文法的開始符推導(dǎo)產(chǎn)生的文法符號(hào)序列是 C. 句型 。A. 短語 B. 句柄 C.

19、句型 D. 句子63._D. 3_型文法也稱為正規(guī)文法。A. 0 B. 1 C. 2 D. 364._D. 含有公共左因子的_文法不是LL(1)的。A. 遞歸 B. 右遞歸 C. 2型 D. 含有公共左因子的65.同心集合并可能會(huì)產(chǎn)生的新沖突為 D. 歸約/歸約 。A. 二義 B. 移進(jìn)/移進(jìn) C. 移進(jìn)/歸約 D. 歸約/歸約66.過程的DISPLAY表記錄了 B. 過程的嵌套層次 。A. 過程的連接數(shù)據(jù) B. 過程的嵌套層次C. 過程的返回地址 D. 過程的入口地址67.代碼優(yōu)化時(shí)所依據(jù)的是 C. 等價(jià)變換規(guī)則 。A. 語法規(guī)則 B. 詞法規(guī)則 C. 等價(jià)變換規(guī)則 D. 語義規(guī)則68.編譯

20、原理各階段工作都涉及 B. 表格管理 A. 詞法分析 B. 表格管理 C. 語法分析 D. 語義分析69.正則表達(dá)式R1和R2等價(jià)是指 C. R1和R2代表同一正則集 A. R1和R2都是定義在一個(gè)字母表上的正則表達(dá)式B. R1和R2中使用的運(yùn)算符相同C. R1和R2代表同一正則集D. R1和R2代表不同正則集70.在以下的語法分析中， D. 算符優(yōu)先分析 特別適合于表達(dá)式的分析。A. LR分析B. LL(1)分析C. 遞歸下降分析D. 算符優(yōu)先分析71.在語法制導(dǎo)翻譯中不采用拉鏈回填技術(shù)的語句是 B. 賦值語句 。A. 跳轉(zhuǎn)語句 B. 賦值語句 C. 條件語句 D. 循環(huán)語句72.在屬性文法

21、中，終結(jié)符只具有 D. 綜合 屬性。A. 傳遞 B. 繼承 C. 抽象 D. 綜合73.不可能是目標(biāo)代碼的是( D中間代碼 )A匯編指令代碼 B可重定位指令代碼C絕對(duì)指令代碼 D中間代碼74.詞法分析器的輸入是( B源程序 )A單詞符號(hào)串 B源程序C語法單位 D目標(biāo)程序75.詞法分析應(yīng)遵循(C構(gòu)詞規(guī)則)A語義規(guī)則 B語法規(guī)則C構(gòu)詞規(guī)則 D等價(jià)變換規(guī)則76.詞法分析器的輸出結(jié)果是(C單詞的種別編碼和屬性值 )A單詞的種別編碼 B單詞在符號(hào)表中的位置C單詞的種別編碼和屬性值 D單詞屬性值 判斷題 1“ 用高級(jí)語言書寫的源程序都必須通過編譯, 產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行 ”這種說法。( ×

22、 )1編譯過程中，語法分析器的任務(wù)是分析單詞是怎樣構(gòu)成的。 (× )22型文法一定是3型文法。 （× ）33型文法一定是2型文法。 ( )4LR 法是自頂向下語法分析方法。 (×)5LR 分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。 ( ) 6LR 分析技術(shù)無法適用二義文法。 ( × )7LR 分析器的任務(wù)就是產(chǎn)生 LR 分析表。 ( ) 8r 和 s 分別是正規(guī)式，則有 L(r|s)=L(r)L(s)。( × ) 9編譯程序是對(duì)高級(jí)語言程序的解釋執(zhí)行。( × ) 10編譯程序與具體的機(jī)器有關(guān),與具體的語言無關(guān)

23、。 ( × ) 12并不是每個(gè)文法都能改寫成LL(1)文法。 ( )13采用三元式實(shí)現(xiàn)三地址代碼時(shí)，不利于對(duì)中間代碼進(jìn)行優(yōu)化。 ( ）14產(chǎn)生式是定義語法范疇的一種書寫規(guī)則。()15產(chǎn)生式是用于定義詞法成分 的一種書寫規(guī)則。 ( × )16程序語言的語言處理程序是一種應(yīng)用軟件。( × ) 17詞法分析作為單獨(dú)的一遍來處理較好。 ( × )18從一個(gè)句型到另一個(gè)句型的推導(dǎo)過程是唯一的。( × )19遞歸下降法不允許任一非終極符是直接左遞歸的。 () 20遞歸下降分析法是一種自下而上分析法。 ( × )21遞歸下降分析法是自頂向上分析方法

24、。( )22對(duì)任何正規(guī)式e，都存在一個(gè)DFA M，滿足L(M)=L(e)。()23對(duì)任意一個(gè)右線性正規(guī)文法G，都存在一個(gè)DFA M，滿足L(G)= L(M)。()24對(duì)于數(shù)據(jù)空間的存貯分配， FORTRAN 采用動(dòng)態(tài)貯存分配策略。 ( × )25二義文法不是上下文無關(guān)文法。( × )26分析作為單獨(dú)的一遍來處理較好。 ( × )27符號(hào)表中的信息欄中登記了每個(gè)名字的 屬性和特征等有關(guān)信息 ，如類型、種屬、所占 單元大小、地址等等。 ( × )28歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。 ( )29計(jì)算機(jī)高級(jí)語言翻譯成低級(jí)語言只有解釋一種方式。(×) 3

25、0甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系 統(tǒng)功能完全相同。 ( )31簡單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。 (×) 32僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無用的。 ( )33進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對(duì)提高目標(biāo)代碼的效率將起更大作用。 (×)34靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。 ( × ) 35兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。 (× )36每個(gè)過程的活動(dòng)記錄的體積在編譯時(shí)可靜態(tài)確定。 （ ）37每個(gè)基本塊可用一個(gè)DAG表示。 （ ）38每個(gè)基本塊只有一個(gè)入口和一個(gè)出口。 (

26、)39每個(gè)文法都能改寫為 LL(1) 文法。 () 40目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。 ( )41逆波蘭表示法表示表達(dá)式時(shí)無須使用括號(hào)。 ( )42逆波蘭法表示的表達(dá)式亦稱后綴式 。 ( )43逆波蘭法表示的表達(dá)試亦稱前綴式。 (× )44確定的的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正集()45確定有限自動(dòng)機(jī)以及非確定有限自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。 ()46如果文法G是無二義的，那么規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。()47如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的。 ( )48若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該

27、句型的句柄。( × )49設(shè)R和S分別是字母表上的正規(guī)式，則有L(R|S)=L(R)L(S)。 ()50樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。 ( × )51數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。 ( × )52算符優(yōu)先分析法每次都是對(duì)句柄進(jìn)行歸約。 (× )53算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 (×) 54同心集的合并有可能產(chǎn)生新的“移進(jìn)”/ “歸約” 沖突 (×)55文法是描述語言的語法結(jié)構(gòu)的形式規(guī)則。()56削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。 ( )57序中的表達(dá)式語句在語

28、義翻譯時(shí)不需要回填技術(shù)。 ( ) 58要構(gòu)造行之有效的自上而下的分析器，則必須消除左遞歸。(× )59一個(gè) LL(l)文法一定是無二義的。 ( × ) 60一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。 ( )61一個(gè)句型的直接短語是唯一的。 （× ）62一個(gè)句型一定句子。 (× )63一個(gè)確定有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。 (× )64一個(gè)上下文無關(guān)文法的開始符，可以是終結(jié)符或非終結(jié)符。(× )65一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。 ( )66一個(gè)優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。 (× )67一個(gè)有限狀態(tài)

29、自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。( × ) 68一個(gè)語義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。 ( × )69一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。(× )70語法分析時(shí)必須先消除文法中的左遞歸 。 (×)71在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。(×)72在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。 ( × )73在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。 ( × )74自底而上語法分析方法的主要問題是候選式的選擇。 (×)75自動(dòng)機(jī)M1和M2的狀態(tài)數(shù)不

30、同，則二者必不等價(jià)。 (× )76自上而下分析法是一種“移進(jìn)歸約”法。(× )77自下而上的分析法是一種“移進(jìn)歸約”法。()78綜合屬性是用于 “ 自上而下 ” 傳遞信息。( × )簡答題1語法分析的主要任務(wù)是什么？常分為哪二類方法？ 答：任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列組合成各類語法短語 .常分為：自頂而下，自底而上二類方法。2編譯程序大致有哪幾種開發(fā)技術(shù)？ 答：（1）自編譯（2）交叉編譯 （3）自展 （4）移植：3編譯程序的實(shí)現(xiàn)應(yīng)考慮的問題有那些？ 答：編譯程序的實(shí)現(xiàn)應(yīng)考慮：開發(fā)周期、目標(biāo)程序的效率、可移植性、可調(diào)試性、可維護(hù)性、可擴(kuò)充性等。5編譯過程中可進(jìn)

31、行的優(yōu)化如何分類？ 答：依據(jù)優(yōu)化所涉及的程序范圍，可以分為：局部優(yōu)化、循環(huán)優(yōu)化和全局優(yōu)化。6對(duì)下列錯(cuò)誤信息，請(qǐng)指出可能是編譯的哪個(gè)階段（詞法分析、語法分析、語義分析、代碼生成）報(bào)告的。（1） else 沒有匹配的if（2） 數(shù)組下標(biāo)越界（3） 使用的函數(shù)沒有定義（4） 在數(shù)中出現(xiàn)非數(shù)字字符 答：（1） 語法分析（2） 語義分析（3） 語法分析（4） 詞法分析7何謂代碼優(yōu)化？進(jìn)行優(yōu)化所需要的基礎(chǔ)是什么？ 答：對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前代碼運(yùn)行結(jié)果相同，而運(yùn)行速度加快或占用存儲(chǔ)空間減少，或兩者都有。優(yōu)化所需要的基礎(chǔ)是在中間代碼生成之后或目標(biāo)代碼生成之后。8何謂翻譯程序、編

32、譯程序和解釋程序？ 答：翻譯程序是指將用某種語言編寫的程序轉(zhuǎn)換成另一種語言形式的程序的程序，如編譯程序和匯編程序等。編譯程序是把用高級(jí)語言編寫的源程序轉(zhuǎn)換（加工）成與之等價(jià)的另一種用低級(jí)語言編寫的目標(biāo)程序的翻譯程序。解釋程序是解釋、執(zhí)行高級(jí)語言源程序的程序。9寄存器分配的原則是什么？ 答：寄存器分配的原則是：(1) 當(dāng)生成某變量的目標(biāo)代碼時(shí)，盡量讓變量的值或計(jì)算結(jié)果保留在寄存器中，直到寄存器不夠分配時(shí)為止。(2) 當(dāng)?shù)交緣K出口時(shí)，將變量的值存放在內(nèi)存中，因?yàn)橐粋€(gè)基本塊可能有多個(gè)后繼結(jié)點(diǎn)或多個(gè)前驅(qū)結(jié)點(diǎn)，同一個(gè)變量名在不同前驅(qū)結(jié)點(diǎn)的基本塊內(nèi)出口前存放的寄存器可能不同，或沒有定值，所以應(yīng)在出口前把

33、寄存器的內(nèi)容放在內(nèi)存中，這樣從基本塊外入口的變量值都在內(nèi)存中。(3) 對(duì)于在一個(gè)基本塊內(nèi)后邊不再被引用的變量所占用的寄存器應(yīng)盡早釋放，以提高寄存器的利用效率。10什么是語法制導(dǎo)翻譯？中間代碼通常有哪幾種主要形式？ 答：由一個(gè)源語言、一個(gè)目標(biāo)語言和一組翻譯規(guī)則組成，遮住規(guī)則可將任何源語言符號(hào)串翻譯成對(duì)應(yīng)的目標(biāo)語言。主要形式: 三元式、 四元式 、逆波蘭式11為什么在代碼生成時(shí)要考慮充分利用寄存器？ 答：因?yàn)楫?dāng)變量值存在寄存器時(shí)，引用的變量值可直接從寄存器中取，減少對(duì)內(nèi)存的存取次數(shù)，這樣便可提高運(yùn)行速度。因此如何充分利用寄存器是提高目標(biāo)代碼運(yùn)行效率的重要途徑。12計(jì)算機(jī)執(zhí)行用高級(jí)語言編寫的程序有哪

34、些途徑?它們之間的主要區(qū)別是什么? 答：計(jì)算機(jī)執(zhí)行用高級(jí)語言編寫的程序主要途徑有兩種，即解釋與編譯。像Basic 之類的語言，屬于解釋型的高級(jí)語言。它們的特點(diǎn)是計(jì)算機(jī)并不事先對(duì)高級(jí)語言進(jìn)行全盤翻譯，將其變?yōu)闄C(jī)器代碼，而是每讀入一條高級(jí)語句，就用解釋器將其翻譯為一條機(jī)器代碼，予以執(zhí)行，然后再讀入下一條高級(jí)語句，翻譯為機(jī)器代碼，再執(zhí)行，如此反復(fù)?？偠灾沁叿g邊執(zhí)行。像C，Pascal 之類的語言，屬于編譯型的高級(jí)語言。它們的特點(diǎn)是計(jì)算機(jī)事先對(duì)高級(jí)語言進(jìn)行全盤翻譯，將其全部變?yōu)闄C(jī)器代碼，再統(tǒng)一執(zhí)行，即先翻譯，后執(zhí)行。從速度上看，編譯型的高級(jí)語言比解釋型的高級(jí)語言更快。13決定目標(biāo)代碼的因素有哪

35、些？ 答：決定目標(biāo)代碼的因素主要取決于具體的機(jī)器結(jié)構(gòu)、指令格式、字長及寄存器的個(gè)數(shù)和種類，并與指令的語義和所用操作系統(tǒng)、存儲(chǔ)管理等都密切相關(guān)。又由于目標(biāo)代碼的執(zhí)行效率在很大程度上依賴于寄存器的使用，所以目標(biāo)代碼與寄存器的分配算法也有關(guān)。14一個(gè)典型的編譯程序通常由哪些部分組成？各部分的主要功能是什么？ 答：一個(gè)典型的編譯程序通常包含 8 個(gè)組成部分，它們是詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、中間代碼優(yōu)化程序、目標(biāo)代碼生成程序、表格管理程序和錯(cuò)誤處理程序。15最常用的代碼優(yōu)化技術(shù)有哪些？ 答：1. 刪除多余運(yùn)算2. 代碼外提 3. 強(qiáng)度削弱 4. 變換循環(huán)控制條 5. 合

36、并已知量與復(fù)寫傳播 6. 刪除無用賦值二義文法1. 已知文法 GS: ，證明文法GS為二義文法。解：證明： 由文法GS：SaSb|Sb|b，對(duì)句子aabbbb對(duì)應(yīng)的兩棵語法樹為：因此，文法GS為二義文法。 2. 已知文法GS： 答： 對(duì)于串a(chǎn)bc (1)S=>Ac=>abc (2)S=>aB=>abc 即存在兩不同的最右推導(dǎo)。所以，該文法是二義的3. 設(shè)有文法GS: , 證明文法GS為二義文法。答：因?yàn)槲姆℅【S】存在句子aa有兩個(gè)不同的最左推導(dǎo)：所以文法GS是二義性的：S=>SaS=>SaSaS=>aSaS=>aaS=>aa=S=>

37、SaS=>aS=>aSaS=>aaS=>aa4已知文法GP：, 證明文法GP為二義文法。答：解答：因?yàn)槲姆ù嬖诰湫蚮bfbf，此句型有兩棵不同的語法樹，5 已知文法GP：, 證明文法GP為二義文法。答：對(duì)于文法G定義的句子i+i*i，有兩棵不同的語法樹：語言變文法：1. 構(gòu)造產(chǎn)生語言的上下文無關(guān)文法。答： SAB A  aAbb B   cB 2. 構(gòu)造產(chǎn)生語言的上下文無關(guān)文法。 答：S  AB A    aA  B &#

38、160;  bBcc  3. 構(gòu)造產(chǎn)生語言的上下文無關(guān)文法。 答：S  aSb  aS    4. 構(gòu)造產(chǎn)生語言的上下文無關(guān)文法。答：S  aSd  A  D S  aSd  A  D D  aDc  B D  aDc  B5. 構(gòu)造產(chǎn)生語言的上下文無關(guān)文法。問題1：給出下述文法

39、所對(duì)應(yīng)的正規(guī)式：1答： S->0A | 1B ->01S | 01 | 10S | 1 - >(01|10)S | (01|10) -> (01|10) (01|10)*2. 答： GS:S->dA A->a|aB B->aB|a|b|bC C->bC|b3.4.5：已知文法GA，寫出它定義的語言描述GA: 答：GA定義的語言由 0、1符號(hào)串組成，串中 0 和1 的個(gè)數(shù)相同.將下面的語句翻譯成四元式序列：1. 【解答】  該語句的四元式序列如下(其中E1、E2和E3分別對(duì)應(yīng)ACBD、A1和AD，并且關(guān)系運(yùn)算符優(yōu)先級(jí)高）100&