編譯原理自測(cè)(一、二、三)及答案

編譯原理自測(cè)(一、二、三)及答案編譯原理自測(cè)(一、二、三)及答案/編譯原理自測(cè)(一、二、三)及答案編譯原理自測(cè)一是非題(下列各題，你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打“√”，錯(cuò)的打“×”。每題1分,共5分)

1、算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。正確

2、數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。.正確

3、僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無(wú)用的。正確

4、每個(gè)文法都能改寫為L(zhǎng)L(1)文法。不正確

5、對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。不正確填空題從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為（執(zhí)行性）語(yǔ)句和（說(shuō)明性）語(yǔ)句兩大類。

2、掃描器的任務(wù)是從（源程序）中識(shí)別出一個(gè)個(gè)（單詞符號(hào)）。

3、所謂最右推導(dǎo)是指：(任何一步αβ都是對(duì)α中最右非終結(jié)符進(jìn)行替換的)。

4、語(yǔ)法分析最常用的兩類方法是（自上而下）和（自下而上）分析法。

5、一個(gè)上下文無(wú)關(guān)文法所含四個(gè)組成部分是(一組終結(jié)符號(hào)，一組非終結(jié)符號(hào)、一個(gè)開始符號(hào)、一組產(chǎn)生式)。

6、所謂語(yǔ)法制導(dǎo)翻譯方法是(為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序，并在語(yǔ)法分析的同時(shí)執(zhí)行這些子程序)。

7、符號(hào)表中的信息欄中登記了每個(gè)名字的有關(guān)的性質(zhì)，如（類型、種屬、？）等等。

8、一個(gè)過程相應(yīng)的DISPLAY表的內(nèi)容為（現(xiàn)行活動(dòng)記錄）。

9、常用的兩種動(dòng)態(tài)存貯分配辦法是（棧式）動(dòng)態(tài)分配和（堆式）動(dòng)態(tài)分配。

10、產(chǎn)生式是用于定義(語(yǔ)法范疇)的一種書寫規(guī)則。名詞解釋1．遍－－指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。2．無(wú)環(huán)路有向圖(DAG)－－如果有向圖中任一通路都不是環(huán)路，則稱廬有向圖為

無(wú)環(huán)路有向圖，簡(jiǎn)稱DAG。3．語(yǔ)法分析－－按文法的產(chǎn)生式識(shí)別輸入的符號(hào)串是否為一個(gè)句子的分析過程。4．短語(yǔ)－－令G是一個(gè)文法。S劃文法的開始符號(hào)，假定αβδ是文法G的一個(gè)句型，如果有SαAδ且AB，則稱β是句型αβ相對(duì)非終結(jié)符A的短語(yǔ)。5．后綴式－－一種把運(yùn)算量寫在前面，把算符寫在后面的表示表達(dá)式的方法。編譯原理自測(cè)二是非題(下列各題，你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打“√”，錯(cuò)的打“×”。每題1分,共5分)

1、一個(gè)LL(1)文法一定是無(wú)二義的。.正確

2、逆波蘭法表示的表達(dá)式亦稱前綴式。.不正確

3、目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。.正確

4、正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。.正確

5、一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。不正確二、填空題

1、語(yǔ)法分析是依據(jù)語(yǔ)言的（語(yǔ)法）規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語(yǔ)言的（語(yǔ)義）規(guī)則進(jìn)行的。2、程序語(yǔ)言的單詞符號(hào)一般可以分為（基本字、標(biāo)識(shí)符、常量、算符、界符）等等。3、語(yǔ)法分析器的輸入是（單詞符號(hào)串），其輸出是（語(yǔ)法單位）4、所謂自上而下分析法是指（從開始符號(hào)出發(fā)，向下推導(dǎo)，推出句子）。5、如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹，則稱這個(gè)文法是（二義的）。6、對(duì)于文法G，僅含終結(jié)符號(hào)的句型稱為（句子）。7、逆波蘭式ab+c+d*e-所表達(dá)式為（）。8、一個(gè)名字的屬性包括（類型）和（作用域）。9、對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用（靜態(tài)存儲(chǔ)分配）策略，PASCAL采用（動(dòng)態(tài)存儲(chǔ)分配）策略。10、所謂優(yōu)化是指（對(duì)程序進(jìn)行各種等價(jià)變換，使得從變換后的程序出發(fā)，能生成更有效的目標(biāo)代碼）。三、名詞解釋1．詞法分析器——指執(zhí)行詞法分析的程序。2．語(yǔ)法——一組規(guī)則，用它可以形成和產(chǎn)生一個(gè)合式的程序3．最右推導(dǎo)——指對(duì)于一個(gè)推導(dǎo)序列中的每一步直接推導(dǎo)，被替換的總是當(dāng)前

符號(hào)串中的最右非終結(jié)符號(hào)。4．語(yǔ)法制導(dǎo)翻譯——在語(yǔ)法分析過程中，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序

進(jìn)行翻譯的辦法叫做語(yǔ)法制導(dǎo)翻譯。5．基本塊——指程序中一個(gè)順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口，一個(gè)出

口，入口即第一個(gè)語(yǔ)句。出口即最后一個(gè)語(yǔ)句。編譯原理自測(cè)三一選擇題(每空2分,共20分)

1、文法G產(chǎn)生的⑴的全體是該文法描述的語(yǔ)言。D

A.句型B.終結(jié)符集C.非終結(jié)符集D.句子

2、若文法G定義的語(yǔ)言是無(wú)限集，則文法必然是⑵：A

A.遞歸的B.前后文無(wú)關(guān)的C.二義性的D.無(wú)二義性的

3、Chomsky定義的四種形式語(yǔ)言文法中，0型文法又稱為⑶A文法；1型文法又稱為⑷C文法；2型語(yǔ)言可由⑸G識(shí)別。

A.短語(yǔ)結(jié)構(gòu)文法B.前后文無(wú)關(guān)文法C.前后文有關(guān)文法D.正規(guī)文法

E.圖靈機(jī)F.有限自動(dòng)機(jī)G.下推自動(dòng)機(jī)

A.短語(yǔ)結(jié)構(gòu)文法B.前后文無(wú)關(guān)文法C.前后文有關(guān)文法D.正規(guī)文法

E.圖靈機(jī)F.有限自動(dòng)機(jī)G.下推自動(dòng)機(jī)

A.短語(yǔ)結(jié)構(gòu)文法B.前后文無(wú)關(guān)文法C.前后文有關(guān)文法D.正規(guī)文法

E.圖靈機(jī)F.有限自動(dòng)機(jī)G.下推自動(dòng)機(jī)

4、一個(gè)文法所描述的語(yǔ)言是⑹A；描述一個(gè)語(yǔ)言的文法是⑺B。

A.唯一的B.不唯一的C.可能唯一,可能不唯一

A.唯一的B.不唯一的C.可能唯一,可能不唯一

5、數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的⑻A的信息

A.維數(shù)B.類型C.維上下界D.各維的界差

6、在下述的編譯方法中，自底向上的方法有⑼F，自頂向下的分析方法有⑽A。

①簡(jiǎn)單優(yōu)先分析②算符優(yōu)先分析③遞歸下降分析④預(yù)測(cè)分析技術(shù)

⑤LR（K）分析⑥SLR（k）分析⑦LL（k）分析⑧LALR（K）分析

A.③④⑦B.③④⑧C.①②⑧D.③④⑤⑥⑦

E.①②⑤⑥⑦F.①②⑤⑥⑧

A.③④⑦B.③④⑧C.①②⑧D.③④⑤⑥⑦

E.①②⑤⑥⑦F.①②⑤⑥⑧二、簡(jiǎn)答題1．LL（1）分析法對(duì)文法有哪些要求？對(duì)于G中的每個(gè)產(chǎn)生式A→γ1|γ2|…|γm，其各候選式均應(yīng)滿足：

（1）不同的候選式不能推出以同一終結(jié)符號(hào)打頭的符號(hào)串，即FIRST(γi)∩FIRST(γj)=φ（1≤i，j≤m；i≠j）

（2）若有γjε，則其余候選式γi所能推出的符號(hào)串不能以FOLLOW(A)中的終結(jié)符號(hào)開始，即有

FIRST(γi)∩FOLLOW(A)=φ（i≤1,2,…,m；i≠j）2．常見的存儲(chǔ)分配策略有幾種？它們都適合于什么性質(zhì)的語(yǔ)言？有三種分配存儲(chǔ)空間的方式：

（1）靜態(tài)分配若在編譯階段就能確定源程序中各個(gè)數(shù)據(jù)實(shí)體的存儲(chǔ)空間大小，則可以采用較簡(jiǎn)單的靜態(tài)存儲(chǔ)管理。適合靜態(tài)管理的語(yǔ)言應(yīng)具備條件：數(shù)組上下界是常數(shù)、過程調(diào)用不允許遞歸、不允許動(dòng)態(tài)建立數(shù)據(jù)實(shí)體。

（2）棧式分配適用于允許遞歸調(diào)用的程序設(shè)計(jì)語(yǔ)言；

（3）堆式分配對(duì)于允許程序在運(yùn)行時(shí)為變量動(dòng)態(tài)申請(qǐng)和釋放存儲(chǔ)空間的語(yǔ)言，采用堆式分配是最有效的解決方案。3．常見循環(huán)優(yōu)化都有哪些項(xiàng)目？不變運(yùn)算外提；運(yùn)算強(qiáng)度削弱；消除歸納變量；下標(biāo)變量地址計(jì)算優(yōu)化。4．什么是活動(dòng)記錄？它主要由哪些內(nèi)容構(gòu)成？一個(gè)過程的一次執(zhí)行所需信息的管理，是通過稱為活動(dòng)記錄的連續(xù)存儲(chǔ)塊來(lái)實(shí)

現(xiàn)的?；顒?dòng)記錄的主要內(nèi)容有：

（1）臨時(shí)變量域存放目標(biāo)程序臨時(shí)變量的值；

（2）局部數(shù)據(jù)域存放過程本次執(zhí)行時(shí)的局部數(shù)據(jù)、簡(jiǎn)單變量與數(shù)組內(nèi)情向量等；

（3）機(jī)器狀態(tài)域