1、系名:姓名:學(xué)號(hào):考試日期:班級(jí):裝訂線下上裝訂線編譯原理考試試卷(A卷) 2009 2010學(xué)年第一 學(xué)期科目：編譯原理 計(jì)算機(jī)系_計(jì)算機(jī)科學(xué)與技術(shù) 專業(yè)_ _級(jí)_班題號(hào)一二三四總分得分閱卷人得分一、填空題（每空1分，共10分）1編譯程序的工作的過程一般可以劃分為詞法分析、_、_、_、_等幾個(gè)基本階段，同時(shí)還會(huì)伴有_和出錯(cuò)處理。2自上而下語(yǔ)法分析方法會(huì)面臨的主要問題有遞歸和_。3表達(dá)式a+（b*c+5）的逆波蘭式表示為_。4文法的屬性有_和_。5根據(jù)所涉及程序的范圍，優(yōu)化可分為局部?jī)?yōu)化、_和全局優(yōu)化三種。得分二、選擇題（每小題2分，共10分）1描述語(yǔ)言L=an bn|n1的文法為（ ）。AZ

2、:=Abb;A:=aA|a;B:=bB BZ:=Abb;A:=Aa|a B:=aBb|bCZ:Ab;A:=aAb|a DZ:=aAb;A:=ab|aAb|2以10結(jié)尾的二進(jìn)制數(shù)串為（ ）。A（0|1）*01 B（0|1）*10 C01（0|1）* D 10（0|1）*3一個(gè)句型中出現(xiàn)了某一產(chǎn)生式的右部，則此右部（ ）是該句型的句柄。 A一定 B不一定 C不可能 D上述沒有答案。4 程序的基本塊是指（ ）。A 一個(gè)子程序B 一個(gè)僅有一個(gè)入中和一個(gè)出的語(yǔ)句。C 一個(gè)沒有嵌套的程序段。D 一組順序執(zhí)行的程序段，僅有一個(gè)入口和一個(gè)出口。5請(qǐng)給出下面程序采用值傳遞和換名傳遞后a的值（ ）。 progra

3、m main(input,output) procedure p(x,y,z); begin y:=y+1; z:=a+x end; begin a:=2;b:=3; p(a+b,a,a); print a end.A2和8 B2和9 C7和9 D7和8得分三、判斷并改錯(cuò)(每小題2分，共10分)1文法的二義性和語(yǔ)言的二義性是兩個(gè)相同的概念。 2. DAG圖中運(yùn)算符，操作符可作為終端結(jié)點(diǎn)。3. NFA和DFA所含的終態(tài)結(jié)點(diǎn)可以是若干個(gè)。4. 存在一個(gè)優(yōu)先關(guān)系表就一定存在優(yōu)先函數(shù)與之對(duì)應(yīng)。5. 目標(biāo)代碼的生成與目標(biāo)語(yǔ)言和操作系統(tǒng)無(wú)關(guān)。得分四、分析題（共70分)1對(duì)于文法G：（10分）1） 寫出句型

4、b(Ma)b的最右推導(dǎo)并畫出語(yǔ)法樹。2）寫出上述句型的短語(yǔ)，直接短語(yǔ)和句柄。2構(gòu)造正規(guī)式 (0|1)*00 相應(yīng)的DFA并進(jìn)行化簡(jiǎn)。（15分） 3計(jì)算文法G(M)的每個(gè)非終結(jié)符的FIRST和FOLLOW集合，給出LL（1）分析表，并判斷該文法是否是LL(1)的，請(qǐng)說明理由。（20分）G(M)：M TBT Ba | eB Db | eT | eD d | e4給出賦值語(yǔ)句A:= -B*(C+D)的四元式表示形式。（5分)5設(shè)文法G(S)：(15分)1） 構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合；2） 構(gòu)造優(yōu)先關(guān)系表。3） 該文法是算法優(yōu)先文法嗎？ 6設(shè)有基本塊（5分）T1：2T2：10/TT3：SRT4：S