2004－2005學(xué)年第二學(xué)期考試試卷

考試科目：編譯原理得分：

學(xué)生所在系：姓名：學(xué)號(hào)：

1．（15分）

(a) 字母表S = { ( , ) }上的語言{ ( ), (( )( )),((( ))), ( )( )( )( )( )}是不是正規(guī)語言？為什么？

(b) 正規(guī)式 (0 | 1)^* 和( (e | 0)1^* )^*是否等價(jià)，說明理由。

(a) 語言{ ( ), (( ) ( )), ((( ))), ( ) ( ) ( ) ( ) ()}是正規(guī)語言，因?yàn)樵撜Z言只包括有限個(gè)句子，它可以用正規(guī)式定義如下：

( ) | (( )( )) | ((( ))) | ( ) ( ) ( ) ( ) ( )

(b) 我們分析正規(guī)式( (e | 0) 1^* )^*表示的語言。可以看出正規(guī)式(e| 0) 1^*描述的語言是集合{e, 1, 11, 111, …, 0, 01, 011, 0111,…}，它含長度為1的兩個(gè)串0和1。那么，(0 | 1)^* 所描述的語言是( (e | 0)1^* )^* 所描述的語言的子集，因?yàn)?0 | 1)^*表示字母表{0, 1}上所有串的集合，因此( (e | 0) 1^* )^*所描述的語言不可能再有更多的句子，因而也是表示字母表{0, 1}上所有串的集合。

活前綴的DFA見下圖。請(qǐng)根據(jù)這個(gè)DFA來構(gòu)造該文法的SLR(1)分析表，并說明該文法為什么不是SLR(1)文法。

分析表如下。因?yàn)橛袃商幱幸七M(jìn)－歸約沖突，所以該文法不是SLR(1)文法。

注：Fallow(A) = {a, c}

3．（10分）現(xiàn)有字母表S={ a}，寫一個(gè)和正規(guī)式a^*等價(jià)的上下文無關(guān)文法，要求所寫的文法既不是LR文法，也不是二義文法。

滿足條件的一個(gè)文法如下：

S ® a S a | a | e

4．（20分）

(a) 下面的文法定義語言L = { aⁿbⁿc^m | m, n ³1}。寫一個(gè)語法制導(dǎo)定義，其語義規(guī)則的作用是：對(duì)不屬于語言L的子集L₁= {aⁿbⁿcⁿ | n ³ 1}的句子，打印出錯(cuò)信息。

S ® DCD ® a D b | abC ® C c | c

(b) 語句的文法如下：

S ® id := E | if E then S | while Edo S | begin S ; S end | break

寫一個(gè)翻譯方案，其語義動(dòng)作的作用是：若發(fā)現(xiàn)break不是出現(xiàn)在循環(huán)語句中，及時(shí)報(bào)告錯(cuò)誤。

(a) 語法制導(dǎo)的定義如下：

S ® DCif D.length ¹ C.length then print (“error”)

D ® abD.length := 1

D ® a D₁bD.length := D₁.length + 1

C ®cC.length := 1

C ® C₁cC.length := C₁.length + 1

(b) 翻譯方案如下：

S¢ ® {S.loop := false}S

S ® id := E

S ® if E then {S₁.loop :=S.loop}S₁

S ® while E do {S₁.loop :=true}S₁

S ® begin {S₁.loop := S.loop}S₁ ;{S₂.loop := S.loop}S₂end

S ® break{if not S.loop then print(“error”) }

5．（5分）C程序設(shè)計(jì)的教材上說，可以用兩種形式表示字符串：其一是用字符數(shù)組存放一個(gè)字符串，另一種是用字符指針指向一個(gè)字符串。教材上同時(shí)介紹了這兩種形式的很多共同點(diǎn)和不同點(diǎn)，但是有一種可能的區(qū)別沒有介紹。下面是一個(gè)包含這兩種形式的C程序：

char c1[]=“good!”;

char *c2=“good!”;

main()

{

c1[0]= ‘G’;

printf(“c1=%sn”, c1);

c2[0]= ‘G’;

printf(“c2=%sn”, c2);

}

該程序在X86/Linux機(jī)器上運(yùn)行時(shí)的信息如下：

c1=Good!

Segmentation fault (core dumped)

請(qǐng)問，出現(xiàn)Segmentation fault的原因是什么？

6．（15分）下面是一個(gè)C語言程序：

long f1( i )

long i;

{

return(i*10);

}

long f2(long i)

{

return(i*10);

}

main()

{

printf(“f1 = %d, f2 = %dn”, f1(10.0), f2(10.0) );

}

其中函數(shù)f1和f2僅形式參數(shù)的描述方式不一樣。該程序在X86/Linux機(jī)器上的運(yùn)行結(jié)果如下：

f1 = 0, f2 = 100

請(qǐng)解釋為什么用同樣的實(shí)在參數(shù)調(diào)用這兩個(gè)函數(shù)的結(jié)果不一樣。

7．（10分）下面是一個(gè)C語言程序和在X86/Linux機(jī)器上編譯（未使用優(yōu)化）該程序得到的匯編代碼（為便于理解，略去了和討論本問題無關(guān)的部分，并改動(dòng)了一個(gè)地方）。

(a)為什么會(huì)出現(xiàn)一條指令前有多個(gè)標(biāo)號(hào)的情況，如.L2和.L4，還有.L5、.L3和.L1？從控制流語句的中間代碼結(jié)構(gòu)加以解釋。

(b) 每個(gè)函數(shù)都有這樣的標(biāo)號(hào).L1，它的作用是什么，為什么本函數(shù)沒有引用該標(biāo)號(hào)的地方？

main()

{

long i,j;

if ( j )

i++;

else

while ( i ) j++;

}

main:

pushl�p――將老的基地址指針壓棧

movl%esp,�p――將當(dāng)前棧頂指針作為基地址指針

subl$8,%esp――為局部變量分配空間

cmpl $0,-8(�p)

je .L2

incl -4(�p)

jmp .L3

.L2:

.L4:

cmpl $0,-4(�p)

jne .L6

jmp .L5

.L6:

incl -8(�p)

jmp .L4

.L5:

.L3:

.L1:

leave――和下一條指令一起完成恢復(fù)老的基地址指針，將棧頂

ret――指針恢復(fù)到調(diào)用前參數(shù)壓棧后的位置，并返回調(diào)用者

8．（5分）cc是UNIX系統(tǒng)上C語言編譯命令，-l是連接庫函數(shù)的選擇項(xiàng)。兩個(gè)程序員分別編寫了函數(shù)庫libuser1.a和libuser2.a。當(dāng)用命令

cc test.c-luser1.a -luser2.a

編譯時(shí)，報(bào)告有重復(fù)定義的符號(hào)。（備注：庫名中的lib在命令中省略。該命令和命令cc test.c libuser1.alibuser2.a的效果是一致的）。而改用命令

cc test.c-luser2.a -luser1.a

時(shí)，能得到可執(zhí)行程序。試分析原因。

9．（5分）根據(jù)教材上所介紹的方法，C++中的對(duì)象聲明語句應(yīng)如何翻譯成C語句？如教材圖11.11（舊教材的圖10.11）程序中的

Point _center;

應(yīng)怎樣翻譯？

2005年編譯原理和技術(shù)試題參考答案

1． (a) 語言{ ( ), (( ) ( )), ((( ))), ( ) ( ) () ( ) ( )}是正規(guī)語言，因?yàn)樵撜Z言只包括有限個(gè)句子，它可以用正規(guī)式定義如下：

( ) | (( )( )) | ((( ))) | ( ) ( ) ( ) ( ) ( )

(b) 我們分析正規(guī)式( (e | 0) 1^* )^*表示的語言。可以看出正規(guī)式(e| 0) 1^*描述的語言是集合{e, 1, 11, 111, …, 0, 01, 011, 0111,…}，它含長度為1的兩個(gè)串0和1。那么，(0 | 1)^* 所描述的語言是( (e | 0)1^* )^* 所描述的語言的子集，因?yàn)?0 | 1)^*表示字母表{0, 1}上所有串的集合，因此( (e | 0) 1^* )^*所描述的語言不可能再有更多的句子，因而也是表示字母表{0, 1}上所有串的集合。

2．分析表如下。因?yàn)橛袃商幱幸七M(jìn)－歸約沖突，所以該文法不是SLR(1)文法。

注：Fallow(A) = {a, c}

3．滿足條件的一個(gè)文法如下：

S ® a S a | a | e

4． (a) 語法制導(dǎo)的定義如下：

S ® DCif D.length ¹ C.length then print (“error”)

D ® abD.length := 1

D ® a D₁bD.length := D₁.length + 1

C ®cC.length := 1

C ® C₁cC.length := C₁.length + 1

(b) 翻譯方案如下：

S¢ ® {S.loop := false}S

S ® id := E

S ® if E then {S₁.loop :=S.loop}S₁

S ® while E do {S₁.loop :=true}S₁

S ® begin {S₁.loop := S.loop}S₁ ;{S₂.loop := S.loop}S₂end

S ® break{if not S.loop then print(“error”) }

5．c1是字符數(shù)組，c1[]=“good!”看成是對(duì)這個(gè)數(shù)組的元素逐個(gè)地賦值。c2是字符指針，它所指向的“good!”看成是一個(gè)字符串常量，常量的值不允許修改，因此編譯器把這個(gè)字符串常量分配在只讀數(shù)據(jù)區(qū)。

當(dāng)執(zhí)行賦值c2[0]= ‘G’時(shí)，試圖對(duì)只讀數(shù)據(jù)區(qū)賦值，因此報(bào)告錯(cuò)誤。

6．歷史上，C語言中有參函數(shù)定義的一般形式是：

類型標(biāo)識(shí)符 函數(shù)名（形式參數(shù)列表）

形式參數(shù)聲明

對(duì)于這種形式的聲明，C語言編譯器是不做實(shí)在參數(shù)和形式參數(shù)的個(gè)數(shù)和類型是否一致的檢查的。如本題中函數(shù)f1的聲明是這種形式。

現(xiàn)在，ANSI新標(biāo)準(zhǔn)允許使用另一種方法聲明形式參數(shù)，即在函數(shù)名后的括號(hào)中列出形式參數(shù)的同時(shí)，聲明形式參數(shù)的類型。本題中函數(shù)f2的聲明是這種形式。C語言編譯器對(duì)于這種形式的函數(shù)聲明是要進(jìn)行實(shí)在參數(shù)和形式參數(shù)的個(gè)數(shù)和類型是否一致的檢查的。

因此，在編譯函數(shù)調(diào)用f2(10.0)時(shí)，會(huì)把浮點(diǎn)數(shù)10.0轉(zhuǎn)換成整數(shù)10，并產(chǎn)生將整數(shù)10壓棧的指令。因此函數(shù)調(diào)用f2(10.0)的結(jié)果是100。

而在編譯函數(shù)調(diào)用f1(10.0)時(shí)，會(huì)把浮點(diǎn)數(shù)10.0轉(zhuǎn)換成雙精度型（參見《編譯原理習(xí)題精選》第5.8題），并產(chǎn)生將該雙精度型數(shù)壓棧的指令。雙精度型數(shù)占8個(gè)字節(jié)。它低地址的4個(gè)字節(jié)看成整數(shù)時(shí)正好是0。因此函數(shù)調(diào)用f1(10.0)的結(jié)果是0（參見http://staff.ustc.edu.cn/~yiyun上2003年編譯原理試題第7題）。

7．(a) 條件語句和循環(huán)語句的中間代碼結(jié)構(gòu)如下：

if (E) then S₁ elseS₂while (E) do S

E的代碼L4: E的代碼

假轉(zhuǎn)L2真轉(zhuǎn) L6

S₁的代碼轉(zhuǎn) L5

轉(zhuǎn)L3L6: S的代碼

L2:S₂的代碼轉(zhuǎn) L4

L3:L5:

用這種代碼結(jié)構(gòu)，當(dāng)while語句作為條件語句的S₂時(shí)，就會(huì)出現(xiàn)題目所給的這種情況。

(b) .L1標(biāo)號(hào)定義的入口是返回調(diào)用者時(shí)該執(zhí)行的指令，在函數(shù)內(nèi)部有return語句時(shí)就會(huì)跳轉(zhuǎn)到.L1。

8．這是基于下面幾點(diǎn)原因。

1．兩個(gè)函數(shù)庫libuser1.a和libuser2.a都定義了某個(gè)函數(shù)或某個(gè)置初值的外部變量，把它簡(jiǎn)稱為a。

2．test.c引用a。

3．test.c還引用libuser2.a的其它某個(gè)函數(shù)或外部變量，把它簡(jiǎn)稱為b。在libuser2.a中，a和b在同一個(gè)目標(biāo)文件中。

4．在libuser1.a中，含a的那個(gè)目標(biāo)文件不含b。

進(jìn)一步的解釋如下。

由于test.c引用a和b，用第二種次序連接時(shí)，a和b的定義在libuser2.a都能找到，所以不會(huì)再把libuser1.a中含a定義的目標(biāo)文件連接進(jìn)來。而用第一種次序連接時(shí)，先把libuser1.a中含a定義的目標(biāo)文件連接進(jìn)來，然后還需要把libuser2.a中含b定義的目標(biāo)文件連接進(jìn)來，引起把a(bǔ)的定義也要帶進(jìn)來，因?yàn)樵趌ibuser2.a中a和b的定義在同一個(gè)目標(biāo)文件中。由此造成要連接a的兩個(gè)定義。

9．C++語言中類的對(duì)象聲明不加翻譯就成了C語言中相應(yīng)結(jié)構(gòu)類型的變量聲明，不管對(duì)象聲明出現(xiàn)在程序中的什么地方。

備注：由于C++語言中一個(gè)類的所有非靜態(tài)屬性構(gòu)成一個(gè)C語言的結(jié)構(gòu)類型，并且類的名字就作為結(jié)構(gòu)類型的名字，因此上面的語句不做任何修改，_center自然就成了Point結(jié)構(gòu)類型的變量。所要注意的是，還應(yīng)該根據(jù)Point類中構(gòu)造函數(shù)的參數(shù)置初值的情況，來給_center適當(dāng)?shù)仂o態(tài)置初值。

愛華網(wǎng)本文地址 » http://www.klfzs.com/a/25101017/329355.html