2006編譯原理試題

1、中國(guó)科學(xué)技術(shù)大學(xué)2005 2006學(xué)年第二學(xué)期考試試卷考試科目：編譯原理和技術(shù)得分： 學(xué)生所在系：姓名：學(xué)號(hào)：1、( 15 分)(a) 用正規(guī)式表示字母表a, b上，a不會(huì)相鄰的所有串。(b) 畫(huà)出一個(gè)最簡(jiǎn)的確定有限自動(dòng)機(jī)，它接受所有大于101的二進(jìn)制整數(shù)。2、( 10分)構(gòu)造下面文法的 LL(1)分析表。S > a B S | b A S | ；A > b A A | aB ； a B B | b 3、( 10分)下面的文法是二義文法S 、EE 一； while E do E | id := E | E + E | id | (E)請(qǐng)你為該語(yǔ)言重寫(xiě)一個(gè)規(guī)范的LR(1)文法，它為該

2、語(yǔ)言中的各種運(yùn)算體現(xiàn)通常的優(yōu)先級(jí)和結(jié)合規(guī)則。不需要證明你的文法是規(guī)范LR(1)的。4、( 10分)為下面文法寫(xiě)一個(gè)語(yǔ)法制導(dǎo)的定義，它完成一個(gè)句子的while-do最大嵌套層次的計(jì)算并輸出這個(gè)計(jì)算結(jié)果。S > EE ； while E do E | id := E | E + E | id | (E)5、( 15分)考慮一個(gè)類(lèi)似 Pascal的語(yǔ)言，其中所有的變量都是整型(不需要顯式聲明)，并且僅包含賦值語(yǔ)句、讀語(yǔ)句、寫(xiě)語(yǔ)句、條件語(yǔ)句和循環(huán)語(yǔ)句。下面的產(chǎn)生式定義了該語(yǔ)言的 語(yǔ)法(其中l(wèi)it表示整型常量；0P的產(chǎn)生式?jīng)]有給出，因?yàn)樗拖旅嬗懻摰膯?wèn)題無(wú)關(guān))。定義Stmt的兩個(gè)屬性：Def表示在

3、Stmt中一定會(huì)定值且在該定值前沒(méi)有引用的變量集 合，MayUse表示在Stmt中有引用且在該引用前可能沒(méi)有定值的變量集合。(a) 寫(xiě)一個(gè)語(yǔ)法制導(dǎo)定義或翻譯方案，它計(jì)算 Stmt的Def和MayUse屬性。(b) 基于上面的計(jì)算，程序可能未賦初值的變量集合從哪兒可以得到？可能未賦初值的變量是這樣定義的：若存在從程序開(kāi)始點(diǎn)到達(dá)變量a某引用點(diǎn)的一條路徑，在這條路徑上沒(méi)有對(duì)變量a賦值，則變量a屬于程序可能未賦初值的變量集合。Program Stmt Stmt > id := Exp Stmt > read (id )Stmt > write ( Exp )Stmt 、 Stmt ;

4、 StmtStmt > if ( Exp ) then begin Stmt end elsebegin Stmt endStmt > while ( Exp ) do begin Stmt endExp.idExp=litExp=Exp OP Exp6、( 15分)賦值語(yǔ)句 Ax, y:= z (其中A是105的數(shù)組)的注釋分析樹(shù)如下圖。請(qǐng)根據(jù)教材上734節(jié)的翻譯方案，把圖中的屬性值都補(bǔ)上(像圖 7.9那樣)，并且把每步歸約產(chǎn)生 的中間代碼寫(xiě)在相應(yīng)產(chǎn)生式的旁邊。E.place :=L.place :=Elist .place :=Elist. ndim :=L.place :=L

5、.offset :=L.offset :=Elist.place :=Elist. ndim :=E.place :=Elist .array :=Elist.array :=L.place :=L.offset :=E.place :=L.place := L .offset :=7、( 15分)通常，函數(shù)調(diào)用的返回值是簡(jiǎn)單類(lèi)型時(shí)，用寄存器傳遞函數(shù)值。當(dāng)返回值是結(jié)構(gòu)類(lèi)型時(shí)需要采用別的方式。下面是一個(gè)C語(yǔ)言文件和它在 x86/Linux上經(jīng)某版本GCC編譯器編譯生成的匯編代碼。(備注，該匯編碼略經(jīng)修改，以便于閱讀。該修改沒(méi)有影響結(jié)果。)(a) 請(qǐng)你分析這些代碼，總結(jié)出函數(shù)返回值是結(jié)構(gòu)類(lèi)型時(shí)，返

6、回值的傳遞方式。(b) 若m函數(shù)的語(yǔ)句 s = f(10)改成s.i = f(10).i + f(20).i + f(30).i，你認(rèn)為 m函數(shù)的局部存儲(chǔ)分配應(yīng)該怎樣修改，以適用該語(yǔ)句的計(jì)算。源文件return.c的內(nèi)容如下：fypedef sfrusong is 八sr(k)-Ong k八宀S s八s.i *recrn s 八30宀S s八s.i H 20八sufuun>H辛 recrn.ss><n-H_fi-e =recrn.c=CDxfg-ob- ffypefy functionf-push- %ebp3O<- %esp%ebp sub- S4esp3O<-

7、 8(ebp)y %eax mov- 12(ebp)y %edx mov- %edx4(ebp) 3O<- 4(ebp)y %edx mov- %ed><(eax) -eaverefsize h Ifg-ob- 3fype m- function3.push- %ebp mov- %esp%ebp sub- esp mov- S2Q 4(ebp) -ea- 4(ebp)y %eaxpushl $10pushl %eaxcall faddl $8, %espleaveret.size m, .-m.section .note.GNU-stack,"",pro

8、gbits.ident "GCC: (GNU) (Debian 8(、5分)把下面左邊的文件 file1.c 提交給編譯器，編譯器沒(méi)有報(bào)告任何錯(cuò)誤。 而把文件 file2.c 提交給編譯器，錯(cuò)誤報(bào)告如下：file2.c: 2: error: conflicting types for func 'file2.c: 1: error: previous declaration of func '試分析原因。(在這兩個(gè)文件中， 第1行都是函數(shù) func 的原型，第2行都是函數(shù) func 的定義， 函數(shù)體為空。 )file1.c file2.cint func(double); int func(double);int