編譯原理試卷B

1、密 封線內(nèi)不要答題姓 名 學(xué) 號 班 級 平頂山工學(xué)院20082009學(xué)年第二學(xué)期期末考試（查）編譯原理試題（b卷） 供 計算機(jī)科學(xué)與技術(shù) 專業(yè) 0614061/2/3 班使用 2009年5月題 號一二三四五六七總 分得 分閱卷人本套試卷共4頁一、填空題：（每空1分，共10分）1、符號表項的組織常采用線性法、二分法和（ ）。2、整個編譯過程可以劃分成五個階段：（ ）、語法分析階段、（ ）、（ ）和目標(biāo)代碼生成階段。3、對于文法g，僅含終結(jié)符號的句型稱為（ ）。4、逆波蘭式ab+c+d*e-所表達(dá)式為（ ）。5、語言翻譯常用的兩種形式是（ ）和（ ）。6、詞法分析器輸出的是單詞符號，語法分析器輸

2、出的是（ ）。二、選擇題：（每空2分，共10分）1、3型文法是（ ），（ ）是語法分析使用的文法。a短語文法 b.上下文有關(guān)文法 c.上下文無關(guān)文法 d.正規(guī)文法2、語法分析是依據(jù)語言的（ ）規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的（ ）規(guī)則進(jìn)行的。 a語法， 推導(dǎo) b語義，產(chǎn)生式 c語法， 語義 d推導(dǎo)， 產(chǎn)生式3、錯誤“變量類型聲明不一致”將在（ ）階段發(fā)現(xiàn)。a詞法分析 b.語法分析 c.語義分析 d.目標(biāo)代碼生成4、下列（ ）不是數(shù)據(jù)空間的使用方法和管理方法a靜態(tài)存儲分配 b.棧式動態(tài)存儲分配 c.堆式動態(tài)存儲分配 d.段頁式存儲分配三、計算題：（每題6分，共24分）1、對給定正規(guī)表達(dá)式b*

3、(dad) (bab)+構(gòu)造其nfa m。2、試給出下列語句的四元式序列：if (a0b5) x1,1=1; else x3,20; 其中，x是1020的數(shù)組(每維下界為1)且按行存放；一個數(shù)組元素占用兩個字節(jié)，機(jī)器按字節(jié)編址。密 封線內(nèi)不要答題姓 名 學(xué) 號 班 級 3、已知文法ge為： etet tft*f f(e)i 試確定tt*fi的最左素短語。4、對文法gs sa|(t)tt，s|s (1) 給出(a,(a,a)的最左推導(dǎo)。四、證明題（每題8分，共16分）1、試證明文法g(e，o,（,）,*,v,d,p,e)，其中p為： eeoe(e)vdo* 是二義性文法。2、文法 ee+ee*ee/eee(e) i試證明該文法是算符文法，但不是算符優(yōu)先文法。密 封線內(nèi)不要答題姓 名 學(xué) 號 班 級 五、綜合題（第1小題10分，第2、3小題各15分）1、對下圖的流圖：(1) 求出流圖中各結(jié)點(diǎn)n的必經(jīng)結(jié)點(diǎn)集d(n)； (2) 求出流圖中的回邊；(3) 求出流圖中的循環(huán)。2、文法g3: sab ab|aa ba （1）求出各非終結(jié)符n的firstvt(n)和lastvt(n),構(gòu)造包括語句