編譯原理試題及參考答案

1、 / 16課程測(cè)試試題（04A 卷）I 、命題院（部）： 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院II、課程名稱：編譯原理III 、測(cè)試學(xué)期：2006 2007 學(xué)年度第1 學(xué)期IV 、測(cè)試對(duì)象：數(shù)計(jì)、國(guó)交學(xué)院 計(jì)科 專業(yè) 2004 級(jí)1、 2、國(guó)交 班、問卷頁(yè)數(shù)（A4） ：3 頁(yè)、答卷頁(yè)數(shù)（A4） ： 4 頁(yè)、考試方式：閉卷 （開卷、閉卷或課程小論文，請(qǐng)?zhí)顚懬宄?、問卷?nèi)容：（請(qǐng)老師在出題時(shí)安排緊湊，填空題象征性的留出一點(diǎn)空格，學(xué)生將所有的答案做在答題紙上的規(guī)定位置，并寫清楚大題、小題的題號(hào)）30 分， 30 個(gè)空，每空1 分）1、典型高級(jí)程序設(shè)計(jì)語(yǔ)言編譯系統(tǒng)的工作過程一般分為六個(gè)階段，即詞法分析、語(yǔ)法分析、

2、語(yǔ)義分析、中間代碼生成、 目標(biāo)代碼生成。編譯階段的兩種組合方式是組合法和按遍組合法，這兩種組合方式的主要參考因素都是的特征。Chomsky 將文法按其所表示語(yǔ)言的表達(dá)能力，由高往低分為四類：0 型， 1 型， 2 型，3 型文法。其中，2 型文法也稱，它的所有規(guī)則 都滿足： ， （VN VT） *且 ，僅當(dāng) = 時(shí)例外。 TOC o 1-5 h z 現(xiàn)代編譯系統(tǒng)多采用方法， 即在語(yǔ)法分析過程中根據(jù)各個(gè)規(guī)則所相聯(lián)的或所對(duì)應(yīng)的語(yǔ)義子程序進(jìn)行翻譯的辦法。該方法使用為工具來說明程序設(shè)計(jì)語(yǔ)言的語(yǔ)義。4、構(gòu)造與NFA M 等價(jià)的正規(guī)文法G 的方法如下：（ 1）對(duì)轉(zhuǎn)換函數(shù)f（A， a）=B 或 f（A， ）

3、=B ，改成形如或 的產(chǎn)生式；（ 2）對(duì)可識(shí)別終態(tài)Z，增加一個(gè)產(chǎn)生式：。5、代碼生成要考慮的主要問題：充分利用的問題、選擇的問題、選擇的問題。6、設(shè)有窮自動(dòng)機(jī)M=（K ， f， S， Z），若當(dāng) M 為 時(shí)，滿足z0 f（S， ） 且 z0 Z，或當(dāng) M 為 時(shí)，滿足f（S， ）=P Z，則稱符號(hào)串 *可被 M 所 。符號(hào)表中每一項(xiàng)對(duì)應(yīng)一個(gè)多元組。符號(hào)表項(xiàng)的組織可分為組織、組織、組織等。對(duì)于 A N 定義 A 的后續(xù)符號(hào)集：FOLLOW（A）=a|S= *uA， a T， 且 a，uT*，+;若， 則#FOLLOW（A） 。 也可以定義為：FOLLOW（A）=a|S=* Aa，a T。若有，則

4、規(guī)定# FOLLOW（A） ?；緣K的定義：一個(gè)基本塊是指程序中一個(gè)執(zhí)行的語(yǔ)句序列，其中只有一個(gè)入口和一個(gè)出口。入口是程序第一個(gè)語(yǔ)句或轉(zhuǎn)移語(yǔ)句的目標(biāo)語(yǔ)句，或轉(zhuǎn)移語(yǔ)句的后繼第一個(gè)語(yǔ)句。出口是程序或轉(zhuǎn)移語(yǔ)句。在基本塊范圍內(nèi)的優(yōu)化稱為。預(yù)測(cè)分析器由預(yù)測(cè)分析表、先進(jìn)后出棧（用來存放分析過程的語(yǔ)法符號(hào)）和 三部分組成。其中預(yù)測(cè)分析表是一個(gè)二維矩陣，其形式為MA ， a，其中A V N， a VT或 #。若有產(chǎn)生式A，使得a，則將A填入 MA ， a中。（書寫時(shí)，通常省略規(guī)則左部，只填） 。對(duì)所有的 MA ， a標(biāo)記為出錯(cuò)。二、簡(jiǎn)述題（共20 分， 4 個(gè)小題，每小題5 分）1、簡(jiǎn)述將NFA轉(zhuǎn)換為最小化D

5、FA的步驟。2、簡(jiǎn)述靜態(tài)存儲(chǔ)分配、棧式存儲(chǔ)分配和堆式存儲(chǔ)分配的特點(diǎn)和主要用途。3、以表達(dá)式a:=b*（-c）+b/（-d） 為例，簡(jiǎn)述常用的三種中間代碼表示形式。簡(jiǎn)述判別文法是否為L(zhǎng)L（1） 文法的步驟和將一個(gè)非LL（1） 文法轉(zhuǎn)換為L(zhǎng)L（1） 文法的方法。三、應(yīng)用題（共50 分）1、有文法GS： （12 分 ）S aAS|aA SbA|SS|ba證明 aabbaa是文法的一個(gè)句子。（3 分 ）構(gòu)造句子aabbaa的語(yǔ)法樹。（3 分 ）指出該句子的所有短語(yǔ)、直接短語(yǔ)和句柄。（6 分 ）2、對(duì)文法GE ： （15 分 ）E #E#E E+T|TT T*F|FF PF|PP （E）|i計(jì)算 GE

6、的 FIRSTVT和 LASTVT。 （5 分 ）構(gòu)造 GE 的算符優(yōu)先關(guān)系表, 并說明 GE 是否為算符優(yōu)先文法。（5 分 ）給出輸入串w=i+i# 的算符優(yōu)先分析過程。（5 分 ）3、對(duì)以下基本塊：（ 8 分）A： =5B： =R+rT0：=A+BT1：=2*AT2： =B+AT3： =A+AX1：=T1+T2X2：=T0*T3（ 1）畫出基本塊的DAG圖。（3 分 ）（ 2）根據(jù)DAG 結(jié)點(diǎn)原來的構(gòu)造順序重寫四元式。（2 分 ）（ 3）假設(shè)基本塊出口后只有X1， X2還被引用，試寫出優(yōu)化后的四元式序列。（3 分 ）4、對(duì)文法GS ：(15 分 )0)S S1)S A 2)S B 3)A

7、aAe4)A a 5)BbBd 6)B b試構(gòu)造GS 的 LR(0) 項(xiàng)目集規(guī)范族DFA。 (4 分 )試構(gòu)造GS 的SLR(1)分析表，并判斷它是否為SLR(1) 文法。 (4 分 )試用SLR( 1)方法分析輸入串a(chǎn)ae#。 (4 分 )(4)GS 是否為 LR(0) 、 LR(1) 和 LALR(1) 文法？為什么？(3 分 )課程測(cè)試試題（04B 卷）I 、命題院（部）： 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院II、課程名稱：編譯原理III 、測(cè)試學(xué)期：2006 2007 學(xué)年度第1 學(xué)期IV 、測(cè)試對(duì)象：數(shù)計(jì)、國(guó)交學(xué)院 計(jì)科 專業(yè) 2004 級(jí)1、 2、國(guó)交班、問卷頁(yè)數(shù)（A4） ：3 頁(yè)、答卷頁(yè)數(shù)（A

8、4） ： 4 頁(yè)、考試方式：閉卷 （開卷、閉卷或課程小論文，請(qǐng)?zhí)顚懬宄?、問卷?nèi)容：（請(qǐng)老師在出題時(shí)安排緊湊，填空題象征性的留出一點(diǎn)空格，學(xué)生將所有的答案做在答題紙上的規(guī)定位置，并寫清楚大題、小題的題號(hào)）30 分， 30 個(gè)空，每空1 分）1、典型編譯過程一般分為詞法分析、語(yǔ)法分析、語(yǔ)義分析、（并非所有的編譯程序都包含此階段）、代碼優(yōu)化、目標(biāo)代碼生成六個(gè)階段，其中詞法分析的任務(wù)是對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出（如標(biāo)識(shí)符等）符號(hào)； 為代碼生成階段收集類型信息，并進(jìn)行類型審查和違背語(yǔ)言規(guī)范的報(bào)錯(cuò)處理是的任務(wù)。2、文法是一些規(guī)則的有窮集合，它是以有窮規(guī)則集來刻劃無(wú)窮集合的工具。文法的四元

9、組表示G =（ VN， VT，P，S）中，元素VN， VT 分別是非空有限的。且二者交集為 ； P為產(chǎn)生式/規(guī)則集，是文法的核心部分；S VN， 是文法的開始符號(hào)（或識(shí)別符） ，它是一個(gè)非終結(jié)符，至少要在一條規(guī)則中作為出現(xiàn)。3、構(gòu)造（）項(xiàng)目集規(guī)范族的項(xiàng)目類型分為四種：形如A.a 的 、形如的待約項(xiàng)目、形如AB. 的歸約項(xiàng)目、形如S . 的。4、一個(gè)優(yōu)先關(guān)系矩陣對(duì)應(yīng)的優(yōu)先函數(shù)；所表示優(yōu)先關(guān)系唯一的矩陣不一定存在優(yōu)先函數(shù)； 當(dāng)兩個(gè)終結(jié)符對(duì)之間無(wú)優(yōu)先關(guān)系時(shí)，可以將相應(yīng)元素置出錯(cuò)信息，而使用卻無(wú)法識(shí)別這種情況，不能準(zhǔn)確指出出錯(cuò)位置。5、 在編譯程序中用符號(hào)表來存放語(yǔ)言中出現(xiàn)的有關(guān)的語(yǔ)義特征屬性信息。程

10、序設(shè)計(jì)語(yǔ)言中通用的標(biāo)識(shí)符屬性主要有如下幾種：符號(hào)名、符號(hào)的、符號(hào)的存儲(chǔ)類別、符號(hào)的、符號(hào)變量的存儲(chǔ)分配信息及數(shù)組的內(nèi)情向量等其它屬性。 TOC o 1-5 h z 6、如果文法G=(VN， VT，P， S)中不存在形如ABC的產(chǎn)生式，其中B、 C為非終結(jié)符，則稱之為。在此基礎(chǔ)上，如果a,b VT, a b,a b,a b 至 有一個(gè)成立，則稱之為。7、 分為三類：的機(jī)器語(yǔ)言代碼；的機(jī)器語(yǔ)言代碼；匯編語(yǔ)言(宏匯編)。8、在程序流中，一個(gè)循環(huán)必須具有以下性質(zhì)：1) ，即序列中任意兩點(diǎn)都可達(dá)，若只有一個(gè)結(jié)點(diǎn)，則有一條返回本身的回邊；2) ，即從序列外某結(jié)點(diǎn)，有一條有向邊指向它，或它為圖中首結(jié)點(diǎn)。9、

11、 LR 分析步驟：1 ) 置輸入指針ip 指向輸入串的第一個(gè)符號(hào)；令 S 是棧頂狀態(tài)，a 是ip 所指向的符號(hào);將 #壓入符號(hào)棧，將開始狀態(tài)0壓入狀態(tài)棧；2)根據(jù)分析表重復(fù)執(zhí)行如下過程：如果actionS， a=Sj，則把入符號(hào)棧，把入狀態(tài)棧，并使ip 指向下一個(gè)輸入符號(hào)；如果 actionS,a=r j，則從棧頂彈出第j 條規(guī)則右部串長(zhǎng)| | 個(gè)符號(hào)，把壓入符號(hào)棧， 將 壓入狀態(tài)棧，并輸出規(guī)則A； 如果 actionS,a=acc， 則分析成功，否則報(bào)錯(cuò)。10、過程( 函數(shù))是結(jié)構(gòu)化程序設(shè)計(jì)的主要手段。調(diào)用與被調(diào)用過程兩者之間的信息主要通過或參數(shù)來傳遞。參數(shù)分為，常用的參數(shù)傳遞方式有傳地址、

12、傳值、 傳名等。20 分， 4 個(gè)小題，每小題5 分)1、簡(jiǎn)述運(yùn)行目標(biāo)程序時(shí)所需空間的種類。2、簡(jiǎn)述算符優(yōu)先分析算法的步驟和算符優(yōu)先分析方法的優(yōu)、缺點(diǎn)。3、簡(jiǎn)述代碼優(yōu)化的概念和分類，并列舉出四種以上常用的代碼優(yōu)化技術(shù)。4、簡(jiǎn)述判別任意給定的一個(gè)上下文無(wú)關(guān)文法GS 是否為 LALR(1) 文法的過程。50 分)1、有文法GE： (16 分 )E T + E T T T * F F F ( E ) i(1)證明T+T*F+i 是文法的一個(gè)句型。(3 分 )(2)構(gòu)造型T+T*F+i 的語(yǔ)法樹。(3 分 )(3)指出該句型的所有短語(yǔ)、直接短語(yǔ)和句柄。(7 分 )(4)指出該句型的所有素短語(yǔ)和最左素短

13、語(yǔ)。(3 分 )2、將下列條件語(yǔ)句翻譯成四元式的中間代碼形式：(6 分 )if ab or cf then s1 else s23、有正規(guī)文法GS ：(12 分 )S aA|bBA bS|b B aS|a(1)構(gòu)造對(duì)應(yīng)的正規(guī)式R，使得L(R)=L(G) 。(3 分 )(2)構(gòu)造對(duì)應(yīng)的NFA 狀態(tài)圖，使得L(M)=L(R) 。(3 分 )(3)將所得NFA 確定化為DFA。(3 分 )(4)將所得DFA 最小化。(3 分 )4、對(duì)表達(dá)式文法GE ：(16 分 )E E - T T T T F F F ( E ) a(1)判斷GE是否為 LL(1) 文法。若不是，改造為L(zhǎng)L(1) 文法。 (8 分

14、 )(2)構(gòu)造預(yù)測(cè)分析表，并對(duì)輸入串w=a-aa#進(jìn)行預(yù)測(cè)分析。(8 分 )課程測(cè)試試題（03A 卷） 以下為教師填寫I 、命題院（部）： 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院II、課程名稱：編 譯 原 理III 、測(cè)試學(xué)期：2005 2006學(xué)年度第1 學(xué)期 TOC o 1-5 h z IV 、測(cè)試對(duì)象：數(shù)計(jì) 學(xué)院 計(jì)算機(jī)科學(xué)技術(shù)專業(yè) 2003 級(jí) 1、2、3 班、問卷頁(yè)數(shù)（A4） ：4 頁(yè)、答卷頁(yè)數(shù)（A4）：6頁(yè)、考試方式：閉卷 （開卷、閉卷或課程小論文，請(qǐng)?zhí)顚懬宄?、問卷?nèi)容：（請(qǐng)老師在出題時(shí)安排緊湊，填空題象征性的留出一點(diǎn)空格，學(xué)生將所有的答案做在答題紙上的規(guī)定位置，并寫清楚大題、小題的題號(hào)）一、填空

15、（ 30 分）將編譯過程的各階段劃分為前端或后端和將編譯程序分遍的主要參考因素都是（ ）和（ ）的特征。（ ）是一種語(yǔ)法分析程序的自動(dòng)構(gòu)造工具，用它可以直接構(gòu)造各種語(yǔ)言的語(yǔ)法分析器；而（）是一種詞法分析程序的自動(dòng)構(gòu)造工具，用它可以直接構(gòu)造各種語(yǔ)言的詞法分析器。假設(shè) GS是一個(gè)文法, 如有 S* x, 則稱 x是該文法G的（） ；文法 G產(chǎn)生的（ ）的全體稱為該文法所描述的語(yǔ)言。所謂 2 型文法就是指（）文法，若用G =（ VN， VT， P， S）表示它，則它要求G中的所有規(guī)則 都滿足： 是（ ） ，而 屬于（VN U VT） *。文法中形如U U的規(guī)則稱為（）規(guī)則；由不可達(dá)的非終結(jié)符或不可終

16、止的非終結(jié)符作為左部的規(guī)則稱為（） 規(guī)則。 在實(shí)用文法中一般不允許含有這兩類規(guī)則。 TOC o 1-5 h z 在用五元組表示的確定的有窮自動(dòng)機(jī)DFAM（ = K， V， F， S， Z）中，元素V表示字母表；元素S表示唯一的初態(tài)，它是狀態(tài)集K的一個(gè)元素；元素F表示（） ；元素 Z 表示終態(tài)集，它是狀態(tài)集K的一個(gè)（） 。語(yǔ)法分析方法分為自上而下與自下而上兩類，自上而下的分析方法方要有遞歸子程序分析法和（） ； 而自下而上的分析方法主要有（） 和 LR分析方法。LR（0） 項(xiàng)目集規(guī)范族中的項(xiàng)目可分為四類，它們是移進(jìn)項(xiàng)目、（） 、歸約項(xiàng)目和接受項(xiàng)目。其中，接受項(xiàng)目是（將非LL（1） 文法轉(zhuǎn)換為等價(jià)

17、的LL（1） 文法所采用的兩種方法是（） 和 （） 。但這兩種方法并不能保證所有的非LL（1） 文法都能轉(zhuǎn)換為等價(jià)的LL（1） 文法。10、通常局部?jī)?yōu)化是指基本塊內(nèi)的優(yōu)化，所謂基本塊是指程序中一順序執(zhí)行的語(yǔ)句序列，其中只有一個(gè)（）語(yǔ)句和一個(gè)（）語(yǔ)句。11、算符優(yōu)先分析時(shí)，在句型N1a1N2 ai-1 NiaiNi+1ai+1 ajNj+1aj+1 Nj+2中，尋找的最左素短語(yǔ)NiaiNi+1ai+1aj Nj+1 中的終結(jié)符應(yīng)滿足下優(yōu)先關(guān)系：（） 、 （） 、 （） 。12、 在編譯程序中符號(hào)表用來存放語(yǔ)言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，這些信息集中反映了標(biāo)識(shí)符的語(yǔ)義特征屬性。符號(hào)表的功能可

18、以歸結(jié)為三個(gè)主要方面，即（） 、作為上下文語(yǔ)義合法性檢查的依據(jù)和作為（）的依據(jù)。13、根據(jù)優(yōu)先關(guān)系矩陣計(jì)算優(yōu)先函數(shù)可用迭代法或優(yōu)先關(guān)系圖法，但先關(guān)系圖方法計(jì)算出來的優(yōu)先函數(shù)不一定有效，當(dāng)（）時(shí)，所得的優(yōu)先函數(shù)無(wú)效，這時(shí)也說明該優(yōu)先關(guān)系矩陣不存在優(yōu)先函數(shù)。14、當(dāng)一個(gè)過程調(diào)用其他過程時(shí)，調(diào)用過程和被調(diào)用過程之間的通信經(jīng)由非局部變量或者經(jīng)由參數(shù)傳遞，常用的參數(shù)傳遞方式有（） 、 （）等。15、現(xiàn)代很多編譯程序都采用（）翻譯方法，它是指在語(yǔ)法分析過程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)規(guī)則所對(duì)應(yīng)的語(yǔ)義子程序或語(yǔ)義動(dòng)作進(jìn)行翻譯的辦法。這種方法使用（）為工具來說明程序設(shè)計(jì)語(yǔ)言的語(yǔ)義。二、結(jié)合你所熟悉的一門高

19、級(jí)語(yǔ)言的編譯系統(tǒng)，簡(jiǎn)述典型編譯程序在各個(gè)工作階段的任務(wù)。（ 共 7 分 ）三、給定正規(guī)式R=（01|10） （01|10） * ，要求：（10 分 ）1、構(gòu)造對(duì)應(yīng)的正規(guī)文法G，使得L（G）=L（R） 。 （4 分 ）2、構(gòu)造對(duì)應(yīng)的NFA M狀態(tài)圖，使得L（M）=L（R）。（3 分 ）3、將所得NFA M確定化為DFA。（3 分 ）四、現(xiàn)有文法GE： （ 共 10分 ）E E+T|E-T|TT T*F|T/F|FF i|(E)1、證明： E-F*(i) 是文法的一個(gè)句型。(3 分 )2、構(gòu)造句型E-F*(i) 的語(yǔ)法推導(dǎo)樹。(2 分 )3、指出該句型所有短語(yǔ)、直接短語(yǔ)和句柄。(5 分 )五、任意

20、給定一個(gè)文法GS：(10 分 )1、給出判斷GS是否為 LL(1) 文法的步驟。(4 分 )2、如果GS是 LL(1) 文法，怎樣構(gòu)造它的預(yù)測(cè)分析表？(3 分 )3、怎樣根據(jù)預(yù)測(cè)分析表對(duì)給定的某個(gè)輸入串進(jìn)行預(yù)測(cè)分析？(3 分 )六、現(xiàn)有文法GE： (共 15分 )E E;D|DD D(T)|HH a|(E)T T*E|E1、計(jì)算GE的 FIRSTVT和 LASTVT； (4 分 )2、構(gòu)造GE的算符優(yōu)先關(guān)系表, 并說明 GE是否為算符優(yōu)先文法；(5 分 )給出輸入串(a*a)# 的算符優(yōu)先分析過程，并據(jù)此說明算符優(yōu)先分析方法的優(yōu)點(diǎn)和缺點(diǎn)。(6 分 )七、現(xiàn)有文法GS ：( 共 18分 ) TO

21、C o 1-5 h z 0)SSSL = RSRL* RLiRL1、構(gòu)造 GS 的 LR(0) 項(xiàng)目集規(guī)范族DFA，并據(jù)此判斷GS 是否為 LR(0) 文法或 SLR(1)文法。 (6分 )2、構(gòu)造 GS 的LR(1)項(xiàng)目集規(guī)范族DFA，并據(jù)此判斷GS是否為 LR(1)文法或LALR（1）文法。（6 分 ）3、給出相應(yīng)的LALR（1）分析表。（3 分 ）4、簡(jiǎn)述LR分析算法。（3 分 ）課程測(cè)試試題（03B 卷） 以下為教師填寫I 、命題院（部）： 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院II、課程名稱：編 譯 原 理III 、測(cè)試學(xué)期：2005 2006學(xué)年度第1 學(xué)期IV 、測(cè)試對(duì)象：數(shù)計(jì) 學(xué)院 計(jì)算機(jī)科學(xué)技

22、術(shù)專業(yè) 2003 級(jí) 1、 2、 3 班 TOC o 1-5 h z 、問卷頁(yè)數(shù)（A4） ：4 頁(yè)、答卷頁(yè)數(shù)（A4） ：6 頁(yè)、考試方式：閉卷 （開卷、閉卷或課程小論文，請(qǐng)?zhí)顚懬宄?、問卷?nèi)容：（請(qǐng)老師在出題時(shí)安排緊湊，填空題象征性的留出一點(diǎn)空格，學(xué)生將所有的答案做在答題紙上的規(guī)定位置，并寫清楚大題、小題的題號(hào)）一、判斷（15 分）1、編譯程序是一種語(yǔ)言翻譯程序，它將源語(yǔ)言程序翻譯成功能等價(jià)的目標(biāo)語(yǔ)言程序。所謂規(guī)則或產(chǎn)生式是指形如 或 := 的 （ , ）有序?qū)?，其中是字母表V的正閉包元素, 而 是字母表V的閉包元素。、設(shè)文法G=（VN，VT，P，S），若P 中的每一個(gè)規(guī)則都是AaB 或Aa，

23、其中A和 B是非終結(jié)符，而a 是終結(jié)符，則稱此文法G為正規(guī)文法或3 型文法。實(shí)用文法中不得含有形如U U的有害規(guī)則，也不得含有由不可達(dá)或不可終止的非終結(jié)符所構(gòu)成的多余規(guī)則。5、 對(duì)任意給定的一個(gè)正規(guī)式R， 都可以將它轉(zhuǎn)換為與之功能等價(jià)的正規(guī)文法，或與之功能等價(jià)的有窮自動(dòng)機(jī)。6、 LEX是一個(gè)用于構(gòu)造各種各樣語(yǔ)言的詞法分析程序；YACC是一個(gè)用于構(gòu)造各種各樣語(yǔ)言的語(yǔ)法分析程序。7、假設(shè)現(xiàn)有五元組表示的有窮自動(dòng)機(jī)M=（ K， V， F， S， Z） ，若M 是 NFA，則 S 表示初態(tài)，且S 具有唯一性，它是狀態(tài)集K 的一個(gè)元素。8、算符優(yōu)先分析方法和LR分析方法都是自下而上的分析方法，它們的分析

24、過程實(shí)際上就是規(guī)范歸約過程。9、 LR（0） 項(xiàng)目集規(guī)范族中的項(xiàng)目由兩部分構(gòu)成，一部分是心，即原來的LR（1）項(xiàng)目，另一部分是向前搜索符號(hào)集。10、所謂優(yōu)化實(shí)質(zhì)上是對(duì)代碼進(jìn)行等價(jià)變換，使得變換后的代碼運(yùn)行結(jié)果與變換前的代碼運(yùn)行結(jié)果相同，但運(yùn)行速度或占用的存儲(chǔ)空間加大。常用的優(yōu)化技術(shù)有刪除多余運(yùn)算、代碼外提、強(qiáng)度削弱、變換循環(huán)控制條件、合并已知變量與復(fù)寫傳播等。11、對(duì)一個(gè)不包含空規(guī)則的算符文法，如果文法中的任意兩個(gè)終結(jié)符構(gòu)成的符號(hào)對(duì)之間最多只有大于、小于和等于三種優(yōu)先關(guān)系中的一種成立，則稱該算符文法為算符優(yōu)先文法。12、目標(biāo)程序運(yùn)行時(shí)的動(dòng)態(tài)數(shù)據(jù)存儲(chǔ)區(qū)分為堆區(qū)和棧區(qū)，它用于存放可變數(shù)據(jù)以及管理過

25、程活動(dòng)的控制信息。13、在語(yǔ)法分析過程中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)規(guī)則所對(duì)應(yīng)的語(yǔ)義子程序或語(yǔ)義動(dòng)作進(jìn)行翻譯的辦法，稱為語(yǔ)法制導(dǎo)翻譯，它被現(xiàn)代很多編譯程序所采用。14、可歸前綴本身就是活前綴，它是包含句柄在內(nèi)的活前綴。15、符號(hào)表用來存放語(yǔ)言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，這些信息集中反映了標(biāo)識(shí)符的語(yǔ)義特征屬性。二、將表達(dá)式A:=B*（ C-D） /D：（ 共 9 分 ）3、翻譯成逆波蘭式的中間代碼形式。（2 分 ）4、翻譯成四元式的中間代碼形式。（4 分 ）5、將譯成的四元式用DAG表示。（3 分 ）三、現(xiàn)有文法GE： （ 共 12分 ）E E+T|E-T|TT T*F|T/F|FF i

26、|（E）6、證明：F+T*（E） 是文法的一個(gè)句型。（3 分 ）7、構(gòu)造句型F+T*（E） 的語(yǔ)法推導(dǎo)樹。（3 分 ）8、指出該句型所有短語(yǔ)、直接短語(yǔ)和句柄。(6 分 )四、給定正規(guī)式R=d(a|bc) *d，要求：(12 分 )4、構(gòu)造對(duì)應(yīng)的NFA M狀態(tài)圖，使得L(M)=L(R)。(4 分 )5、將所得NFA M確定化和最小化。(8 分 )五、現(xiàn)有文法GS： (共 16分 )S S; D|DD D(T)|HH m|(S)T T*S|S1、計(jì)算GS的FIRSTVT和LASTVT； (4 分 )2、構(gòu)造GS的算符優(yōu)先關(guān)系表, 并說明 GS是否為算符優(yōu)先文法；(6 分 )3、給出輸入串(m*m)

27、# 的算符優(yōu)先分析過程。(4 分 )4、根據(jù)分析過程總結(jié)算符優(yōu)先分析方法的優(yōu)缺點(diǎn)。(2 分 )六、已知GS：(18 分 )S (A)|a|bA A,S|S1、給出(a,(b,b) 的最左推導(dǎo)。(3 分 )2、判斷該文法是否為L(zhǎng)L(1) 文法。若是，直接給出它的預(yù)測(cè)分析表；若不是，先將其改寫為L(zhǎng)L(1) 文法，再給出它的預(yù)測(cè)分析表；(10 分 )3、給出輸入串(b,b)# 的分析過程，并說明該串是否為GS的句子。 (5 分 )七、對(duì)給定文法GS : ( 共 18 分 )0) S SS AS BA aAcA aB bBdB b5、構(gòu)造GS 的LR(0)項(xiàng)目集規(guī)范族DFA，并據(jù)此判斷GS 是否為 L

28、R(0)文法。 (6 分 )6、進(jìn)一步判斷GS 是否為SLR(1)文法，并給出對(duì)應(yīng)的SLR(1)分析表。 (6 分 )3、給出輸入串bbd#的 SLR(1)分析過程。(4 分 )4、 判斷 GS 是否為 LR(1)文法和LALR(1)文法。(2 分 )編譯原理課程測(cè)試試卷評(píng)分標(biāo)準(zhǔn)（數(shù)計(jì)學(xué)院04 計(jì)科 A卷）30 分， 30 個(gè)空，每空1 分）題號(hào)1234參考 答案代碼優(yōu)化、前后端、 源語(yǔ)言與目標(biāo)機(jī)器上下文無(wú)關(guān)文法、V N、 | |=| |語(yǔ)法制導(dǎo)翻譯、語(yǔ) 義動(dòng)作、屬性文法A aB、 A B、 Z題號(hào)5678參考 答案寄存器、計(jì)算機(jī)指令 系統(tǒng)、計(jì)算次序NFA、 DFA、接受（識(shí)別）線性、排序、散

29、列FIRST( ) 、 = 、 S=*A題號(hào)910參考 答案順序、最后一個(gè)語(yǔ)句、局部?jī)?yōu)化預(yù)測(cè)分析程SELECT（A）序、 、沒有值說明： 各個(gè)答案可有不同表達(dá)方式，只要意思相同即可。二、簡(jiǎn)述題參考答案（共20 分， 4 個(gè)小題，每小題5 分）第一步：將NFA 確定化。用造表法將NFA 確定化過程如下：（0）表的第0 行和第 0列作標(biāo)識(shí)行列的值。將 -closure（I）作為表中第1 行第 1 列。假定 =a1 ， a2， .an，設(shè)第 i 行第一列已確定狀態(tài)集為I，則置該行第i 列為 Iai，如 Iai 未曾在任何行第一列出現(xiàn)過，則將 Iai 加入下一空行i+1 的第一列，并在第 0 列標(biāo)記為

30、Ti+1 。反復(fù)重復(fù)第（1） 步，直至無(wú)新狀態(tài)出現(xiàn)為止。重新命名新狀態(tài)。（ 3 分）第二步：將DFA 最小化。DFA 最小化具體過程：用子集分割法將不含多余狀態(tài)的DFA分成一些不相交的子集，使得任何兩個(gè)不同的子集中的狀態(tài)都是可區(qū)別的，而相同子集中狀態(tài)是等價(jià)的。分割時(shí)，首先將DFA 狀態(tài)分成終態(tài)子集和非終態(tài)子集，再根據(jù)輸出弧所達(dá)到狀態(tài)的性質(zhì)逐步細(xì)分。（ 2 分）（ 1）靜態(tài)存儲(chǔ)分配的特點(diǎn)：編譯時(shí)刻確定存儲(chǔ)位置；訪問效率高。主要用途：子程序的目標(biāo)代碼段、全局?jǐn)?shù)據(jù)目標(biāo)（全局變量）。 （ 2 分）（ 2）棧（Stack ）式存儲(chǔ)分配的特點(diǎn)：嵌套調(diào)用次序、先進(jìn)后出、生存期限于本次調(diào)用、自動(dòng)釋放。用途：過

31、程的局部環(huán)境、活動(dòng)記錄。（ 1 分）（ 3）堆（Heap）式存儲(chǔ)分配的特點(diǎn)：將內(nèi)存空間分為若干塊，根據(jù)用戶要求分配；無(wú)法滿足時(shí)，調(diào)用無(wú)用單元收集程序?qū)⒈会尫诺膲K收集起來重新分配。主要用途：用于動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)：存儲(chǔ)空間的動(dòng)態(tài)分配和釋放。（ 2 分）(1)逆波蘭式：abc-*bd-/+:=。 ( 1 分)( 2)三元式：(- , c , _ ) (* , b , ) (- , d , _ )(/ , b , ) (+ , , ) (:= , ,a ) 。 ( 2分)( 3)四元式: (- , c , _ ,t1) (* , b ,t1 ,t2) (- , d , _ ,t3)(/ , b ,t3 ,

32、t4) (+ ,t2 ,t4 ,t5) (:= ,t5 ,_ , a) 。 ( 2 分)（ 1）判別步驟：先畫出各非終結(jié)符能否推導(dǎo)出 的情況表；然后，用定義法或關(guān)系圖法計(jì)算FIRST、 FOLLOW 集；再計(jì)算各規(guī)則的SELECT 集；最后，根據(jù)同一個(gè)左部的規(guī)則其 SELECT 集是否相交來判斷給定文法是否為L(zhǎng)L（1） 文法。 （ 3分）（ 2）將非LL（1） 文法轉(zhuǎn)換成LL（1） 文法的兩種主要方法：提取左公共因子、消除左遞歸。 （ 2 分）50 分）1、 （ 1）證明（3 分 ）：因?yàn)榇嬖谕茖?dǎo)序列S=aAS=aSbAS=aabAS=aabbaS=aabbaa，S=*aabbaa 成立，所以

33、，是文法的一個(gè)句子。（ 2）語(yǔ)法樹（3 分） ：（ 3）句型分析（6 分） ：將句型改寫為a1a2b1b2a3a4，則：該句型相對(duì)于S 的短語(yǔ)：a1a2b1b2a3a4和a4；相對(duì)于A 的短語(yǔ)：a2b1b2a3和 b2a3；對(duì)于Sa的直接短語(yǔ)：a2，a4；相對(duì)于Aba的直接短語(yǔ)：b2a3；句柄：a2。（2） 構(gòu)造 GE 的算符優(yōu)先關(guān)系表如下：（4 分 ）2、 （1） 計(jì)算 GE 的 FIRSTVT和 LASTVT集如下：（5 分 ）由上表可知GE 是算符優(yōu)先文法（1 分 ） 。（3） 輸入串 w=i+i# 的算符優(yōu)先分析過程如下：（5 分 ）（ 1）基本塊的DAG圖如下：（3 分 ）（2 分

34、）2）根據(jù)DAG 結(jié)點(diǎn)原來的構(gòu)造順序重寫四元式如下：A： =5T1=10T3=10B： =R+rT0： =A+BT2： =T0X1： =T0+T1X2： =T0*T1假設(shè)基本塊出口后只有X1， X2還被引用，則通過重新命名臨時(shí)變量的基本塊保結(jié)構(gòu)變換，可將基本塊的四元式代碼進(jìn)一步優(yōu)化為：(3 分 )C： =R+rD： =5+CX1： =D+10X2： =D*103)A aAe0)S S1)S A2)S B4)A a 5)BbBd 6)B b(1)GS 的 LR(0) 項(xiàng)目集規(guī)范族DFA如下：(4 分 )(2) 由于GS 是 SLR(1) 文法( 1 分) 。GS 的 SLR(1)分析表如下：(3

35、 分 )用 SLR( 1)方法分析輸入串a(chǎn)ae#過程如上右表所示：(4 分 )由于 GS LR(0) 項(xiàng)目集規(guī)范族DFA中 I 4、 T5中都包含有移進(jìn)歸約沖突，所以GS 不是 LR(0) 文法，由于GS 是 SLR(1)文法故一定是LR(1) 和 LALR(1)文法。 (3 分 )編譯原理課程測(cè)試試卷評(píng)分標(biāo)準(zhǔn)(數(shù)計(jì)學(xué)院04 計(jì)科 B 卷)30 分， 30 個(gè)空，每空1 分)題號(hào)1234參考 答案中間代碼生成、單詞、語(yǔ)義分析句子、非終結(jié)符號(hào)集和 終結(jié)符集、左部移進(jìn)項(xiàng)目、A.B 、 接受項(xiàng)目不唯一、優(yōu)先矩 陣、優(yōu)先函數(shù)題號(hào)5678參考 答案標(biāo)識(shí)符、類型、作用 域和可視性、算符文法、多、算符優(yōu) 先

36、文法目標(biāo)代碼、已定位、 可重定位強(qiáng)連通、有且只有一個(gè)入口結(jié)點(diǎn)題號(hào)910參考 答案符號(hào)a、 狀態(tài)j、 歸約得到的非終結(jié)符A、 gotoS,a的值j全局變量、形參和實(shí)參說明： 各個(gè)答案可有不同表達(dá)方式，只要意思相同即可。二、簡(jiǎn)述題參考答案（共20 分， 4 個(gè)小題，每小題5 分）運(yùn)行目標(biāo)程序時(shí)所需空間分為兩種容納目標(biāo)代碼的空間和目標(biāo)代碼運(yùn)行時(shí)的數(shù)據(jù)空間。 （ 2 分）目標(biāo)代碼運(yùn)行時(shí)的數(shù)據(jù)空間中某些部分無(wú)法在編譯時(shí)確定存儲(chǔ)位置，它主要包括：用戶所定義的變量和常量所需空間、中間結(jié)果及參數(shù)傳遞所需的臨時(shí)單元、調(diào)用過程時(shí)的連接單元、I/O 操作所需緩沖區(qū)。（ 3分）（ 1）算符優(yōu)先分析算法的步驟：（ 3

37、分）設(shè)單元 a 中存放當(dāng)前輸入符，S 為一個(gè)符號(hào)棧，則：將當(dāng)前輸入符存放到a 中，將#入符號(hào)棧。將棧頂?shù)谝粋€(gè)終結(jié)符b 與 a 比較。 如果b a， 而 b= #且棧中只剩一個(gè)非終結(jié)符時(shí)，則成功；否則a 入棧；如果b a,則 a入棧；如果b a,在棧頂尋找最左素短語(yǔ)，并將最左素短語(yǔ)歸約為一個(gè)非終結(jié)符；如果文法中找不到相應(yīng)規(guī)則，則出錯(cuò)；重復(fù) （2） 至成功或失敗。（ 2）算符優(yōu)先分析方法的優(yōu)、缺點(diǎn)：（ 2 分）由于只考慮終結(jié)符之間的優(yōu)先關(guān)系確定句柄，所以效率高；由于去掉了單非終結(jié)符之間的歸約，有可能將錯(cuò)誤的句子識(shí)別為正確的，只適用于表達(dá)式的語(yǔ)法分析。3、所謂優(yōu)化實(shí)質(zhì)上是對(duì)代碼進(jìn)行等價(jià)變換，使得變換

38、后的代碼運(yùn)行結(jié)果與變換前的代碼運(yùn)行結(jié)果相同，但運(yùn)行速度或占用的存儲(chǔ)空間加大。（ 1 分）代碼優(yōu)化按階段分中間代碼優(yōu)化和目標(biāo)代碼優(yōu)化，按程序范圍分為局部基本塊優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。（ 2 分）常用的優(yōu)化技術(shù)有刪除多余運(yùn)算、代碼外提、強(qiáng)度削弱、變換循環(huán)控制條件、合并已知變量與復(fù)寫傳播等。（ 2 分）4、判別任意給定的一個(gè)上下文無(wú)關(guān)文法GS是否為 LALR（1） 文法的過程：（1）將GS 加入一條規(guī)則：S SGS拓廣為GS，然后構(gòu)造GS的 LR（0） 項(xiàng)目集規(guī)范族 DFA。 檢查 DFA 的項(xiàng)目集中有無(wú)移進(jìn) 歸約沖突或歸約 歸約沖突，若無(wú)， 則 GS是 LR（0） 文法，也是LALR（1） 文法

39、。 （ 1 分）（ 2） 如果 DFA 的項(xiàng)目集中有無(wú)移進(jìn) 歸約沖突或歸約 歸約沖突，通過考慮歸約項(xiàng)目左部非終結(jié)符的FOLLOW 集能夠解決這兩類沖突，則GS 是 SLR（1）文法，也是LALR（1）文法。 （ 2 分） TOC o 1-5 h z （ 3）如果通過考慮歸約項(xiàng)目左部非終結(jié)符的FOLLOW 集還有不能夠解決的移進(jìn) 歸約沖突，通過考慮后跟符號(hào)來構(gòu)造GS 的 LR（1） 項(xiàng)目集規(guī)范族DFA。如果沖突可以解決，則 GS 是 LR（1） 文法。 進(jìn)一步合并LR（1） 項(xiàng)目集規(guī)范族中同心集，如果依然不產(chǎn)生歸約 歸約沖突，則GS 是 LALR（1） 文法。 （ 3 分）三、應(yīng)用題參考答案（共50 分）1、 （ 1）證明 （3 分 ）：因?yàn)榇嬖谕茖?dǎo)序列：E=T+E=T+T+E=T+T*F+E=T+T*F+T=T+T*F+F=T+T*F+i