編譯原理習(xí)題答案某課本貌似是清華那本ch

1、編譯原理課后習(xí)題答案第九章第 9 章符號(hào)表第 1 題：根據(jù)你所了解的某個(gè) FORTRAN 語言的實(shí)現(xiàn)版本，該語言的名字作用域有哪幾種?答案：FORTRAN 中，名字作用域有四種：在 BLOCK DATA 塊中定義的標(biāo)識(shí)符，其作用域是整個(gè)程序。在COMMON 塊中定義的標(biāo)識(shí)符，其作用域是聲明了該COMMON 塊的所有例程（包括函數(shù)和過程）。在例程中定義的標(biāo)識(shí)符（包括啞變量），其作用域是聲明該標(biāo)識(shí)符的例程。在例程中用 SAVE 定義的標(biāo)識(shí)符，其作用域是聲明該標(biāo)識(shí)符的例程，且在退出該例程時(shí)，該標(biāo)識(shí)符的值仍保留（即內(nèi)部靜態(tài)量）。第 2 題：C 語言中規(guī)定變量標(biāo)識(shí)符的定義可分為 extern,exter

2、n static,auto,local static 和 register五種存儲(chǔ)類：(1)(2)(3)對(duì)五種存儲(chǔ)類所定義的每種變量，分別說明其作用域。試給出適合上述存儲(chǔ)類變量的內(nèi)存分配方式。符號(hào)表中登錄的存儲(chǔ)類屬性，在編譯過程中支持什么樣的語義檢查。答案：(1) extern 定義的變量，其作用域是整個(gè) C 語言程序。extern static 定義的變量，其作用域是該定義所在的 C 程序文件。auto 定義的變量，其作用域是該定義所在的例程。local static 定義的變量，其作用域是該定義所在的例程。且在退出該例程時(shí)，該變量的值仍保留。register 定義的變量，其作用域與 aut

3、o 定義的變量一樣。這種變量的值，在寄存器有條件時(shí)，可存放在寄存器中，以提高運(yùn)行效率。(2) 對(duì) extern 變量，設(shè)置一個(gè)全局的靜態(tài)公共區(qū)進(jìn)行分配。對(duì) extern static 變量，為每個(gè) C 程序文件，分別設(shè)置一個(gè)局部靜態(tài)公共區(qū)進(jìn)行分配。對(duì) auto 和 register 變量，設(shè)定它們?cè)谠摾痰膭?dòng)態(tài)區(qū)中的相對(duì)區(qū)頭的位移量。而例程動(dòng)態(tài)區(qū)在運(yùn)行時(shí)再做動(dòng)態(tài)分配。對(duì) local static 變量，為每個(gè)具有這類定義的例程，分別設(shè)置一個(gè)內(nèi)部靜態(tài)區(qū)進(jìn)行分配。(3) 實(shí)施標(biāo)識(shí)符變量重復(fù)定義合法性檢查，及引用變量的作用域范圍的合法性檢查。1盛威網(wǎng)（）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站編譯原理課后習(xí)題答案第九章

4、第 3 題：對(duì)分程序結(jié)構(gòu)的語言，為其符號(hào)表建立重名動(dòng)態(tài)下推鏈的目的是什么?概述編譯過程中重名動(dòng)態(tài)下推鏈的工作原理。答案：重名動(dòng)態(tài)下推鏈的目的是，保證在合法重名定義情況下，提供完整確切的符號(hào)表項(xiàng)，從而保證引用變量的上下文合法性檢查和非法重名定義檢查。其工作原理是：當(dāng)發(fā)生合法重名定義時(shí)，將上層重名表項(xiàng)下推到鏈中，而在符號(hào)標(biāo)中原重名表項(xiàng)處登錄當(dāng)前重名定義的符號(hào)屬性；在退出本層時(shí)，將最近一次下推的表項(xiàng)，回推登錄到符號(hào)表中原重名表項(xiàng)處。第 4 題：某 BASIC 語言的變量名字表示為字母開頭的字母或數(shù)字兩個(gè)字節(jié)的標(biāo)識(shí)符，該語言的符號(hào)表擬采用雜湊法組織，請(qǐng)為其設(shè)計(jì)實(shí)現(xiàn)一個(gè)有效散列的雜湊算法，并為解決散列沖

5、突，設(shè)計(jì)實(shí)現(xiàn)一個(gè)再散列算法。答案：可采用下列散列雜湊算法（設(shè)表長(zhǎng)為 N） 散列地址=MOD（+），N）。發(fā)生沖突時(shí)再散列的方法：在該沖突處開始，向下尋找第一個(gè)空表項(xiàng)，若找到則該表項(xiàng)地址為再散列地址；若找不到空表項(xiàng)，則循環(huán)到表頭開始，向下尋找第一個(gè)空表項(xiàng)，一直到發(fā)生沖突處為止，若找到空表項(xiàng)則該表項(xiàng)地址為再散列地址，否則表示符號(hào)表已滿，編譯系統(tǒng)給出符號(hào)表溢出信息，終止編譯。2盛威網(wǎng)（）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站編譯原理課后習(xí)題答案第九章附加題問題 1：利用 Pascal 的作用域規(guī)則，試確定在下面的 Pascal 程序中的名字 a 和 b 的每一次出現(xiàn)所應(yīng)用的說明。program m ( input,

6、output ) ; procedure n ( u, v, x, y : integer ) ;var m : record m, n : interger end ; n : record n, m : interger end ;beginwith m do begin m := u ; n:= v end ; with n do begin m := x ; n := y end ; writeln ( m.m, m.n, n.m, n.n )end ; beginm ( 1, 2, 3, 4 )end.答案：圖中用藍(lán)色數(shù)字下標(biāo)相應(yīng)標(biāo)明。program m1 ( input, outp

7、ut ) ; procedure n1( u, v, x, y : integer ) ;var m2 : record m3, n2 : interger end ; n3 : record n4, m4 : interger end ;beginwith m2 do begin m3 := u ; n2 := v end ; with n3 do begin m4 := x ; n4 := y end ; writeln ( m2.m3, m2.n2, n3.m4, n3.n4 )end ; beginm1 ( 1, 2, 3, 4 )end.問題 2：當(dāng)一個(gè)過程作為參數(shù)被傳遞時(shí)，我們假定

8、有以下三種與此相聯(lián)系的環(huán)境可以考慮，下面的 Pascal 程序是用來說明這一問題的。一種是詞法環(huán)境（lexical environment），如此這樣的一個(gè)過程的環(huán)境是由這一過程定義之處的各標(biāo)識(shí)符的聯(lián)編所構(gòu)成；一種是傳遞環(huán)境（passing environment），是由這一過程作為參數(shù)被傳遞之處的各標(biāo)識(shí)3盛威網(wǎng)（）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站編譯原理課后習(xí)題答案第九章符的聯(lián)編所構(gòu)成；另一種是活動(dòng)環(huán)境（activation environment），是由這一過程活動(dòng)之處的各標(biāo)識(shí)符的聯(lián)編所構(gòu)成。試考慮在第（11）行上的作為一個(gè)參數(shù)被傳遞的函數(shù) f。利用對(duì)于 f 的詞法環(huán)境、傳遞環(huán)境和活動(dòng)環(huán)境，在第（8）

9、行上的非局部量 m 將分別處在第（6）行、（10）行和（3）行上的 m 的說明的作用域中。圖示出每個(gè)過程的活動(dòng)記錄。試為此程序畫出活動(dòng)樹。試給出程序的輸出。program param ( inout, output ) ;(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)procedure b ( function h ( n : integer ) : integer ) ; var m : integer ;begin m := 3 ; writeln ( h ( 2 ) ) end b ; procedure c ;var m : integ

10、er ;function f ( n : integer ) : integer ; begin f := m + n end f ;procedure r ;var m : integer ;begin m := 7 ; b ( f ) end begin m := 0 ; r end c ;begin cend . r ;答案：（a）詞法環(huán)境4盛威網(wǎng)（）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站parama控制鏈訪問鏈c控制鏈訪問鏈mr控制鏈訪問鏈mb控制鏈訪問鏈mfn = 2控制鏈訪問鏈編譯原理課后習(xí)題第九章傳遞環(huán)境活動(dòng)環(huán)境param控制鏈鏈c控制鏈鏈mr控制鏈鏈b控制鏈鏈fn = 2控制鏈 鏈5盛威網(wǎng)（）專

11、業(yè)的計(jì)算機(jī)站parama控制鏈 鏈c控制鏈鏈r控制鏈m鏈b控制鏈鏈fn = 2控制鏈鏈編譯原理課后習(xí)題第九章（b）活動(dòng)樹param crb (f (2)（c）詞法環(huán)境：2；傳遞環(huán)境：9；活動(dòng)環(huán)境：5。問題 3：己知程序段：BEGINege i read(i);write(value=,func(i);. ENDegrocedure func(N)ege N； BEGINIF N=0 THEN func=1;ELSE IF N=1,THEN func=1；ELSE func=N*func(N-1) END求當(dāng)輸入 i=3 時(shí)，本程序執(zhí)行期間對(duì)運(yùn)行棧的分配圖。：param控制鏈鏈func控制鏈鏈N

12、=3func控制鏈鏈2func控制鏈鏈6盛威網(wǎng)（）專業(yè)的計(jì)算機(jī)站編譯原理課后習(xí)題第九章問題 4：某語言允許過程嵌套定義和遞歸調(diào)用(如 Pascal 語言)，若在棧式動(dòng)態(tài)分配中采用嵌套層次顯示表 display 解決對(duì)非局部變量的 10；”時(shí)運(yùn)行棧及 display 表的示意圖。 var x，y；PROCEDURE P；var a;PROCEDURE q；va b： BEGINqb：10； ENDq; PROCEDURE s;var c，d； PROCEDURE r;var e,f BEGINrcal q；END r； BEGINscal r； ENDs；BEGIN pcal s ENDp；問題

13、，試給出下列程序執(zhí)行到語句“b：BEGcall p；ainENDmain7盛威網(wǎng)（）專業(yè)的計(jì)算機(jī)站編譯原理課后習(xí)題第九章：8盛威網(wǎng)（）專業(yè)的計(jì)算機(jī)站編譯原理課后習(xí)題答案第九章問題 5：試問下面的程序?qū)⒂性鯓拥妮敵?？分別假定：傳值調(diào)用（call-by-value）；引用調(diào)用（call-by-reference）；復(fù)制恢復(fù)（copy-restore）；傳名調(diào)用（call-by-name）。program main ( input, output ) ; procedure p ( x, y, z ) ;beginy := y + 1 ;z := z + x ; end ;begina := 2 ;

14、b := 3 ;p ( a + b , a, a ) ; print aend.答案：傳地址：所謂傳地址是指把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù)。在過程段中每個(gè)形式參數(shù)都有一對(duì)應(yīng)的單元，稱為形式單元。形式單元將用來存放相應(yīng)的實(shí)在參數(shù)的地址。當(dāng)調(diào)用一個(gè)過程時(shí)，調(diào)用段必須領(lǐng)先把實(shí)在參數(shù)的地址傳遞到一個(gè)為被調(diào)用段可以拿得到的地方。當(dāng)程序控制轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段首先把實(shí)參地址捎進(jìn)自己相應(yīng)的形式單元中，過程體對(duì)形式參數(shù)的任何引用 1 或賦值都被處理成對(duì)形式單元的間接訪問。當(dāng)調(diào)用段工作完畢返回時(shí)，形式單元(它們都是指示器)所指的實(shí)在參數(shù)單元就持有所指望的值。傳結(jié)果：和“傳地址”相似(但不等價(jià))的另一

15、種參數(shù)傳遞力法是所謂“傳結(jié)果”。這種方法的實(shí)質(zhì)是，每個(gè)形式參數(shù)對(duì)應(yīng)有兩個(gè)申元，第 1 個(gè)單元存放實(shí)參的地址，第 2 個(gè)單元存放實(shí)參的值。在過程體中對(duì)形參的任何引用或賦值都看成是對(duì)它的第 2 個(gè)單元的直接訪問。但在過程工作完畢返回前必須把第 2 個(gè)單元的內(nèi)容行放到第 1 個(gè)單元所指的那個(gè)實(shí)參單元之中。傳值：所謂傳值，是一種簡(jiǎn)單的參數(shù)傳遞方法。調(diào)用段把實(shí)在參數(shù)的值計(jì)算出來并存放在一個(gè)被調(diào)用段可以拿得到的地方。被調(diào)用段開始丁作時(shí)，首先把這些值抄入形式中元中，然后就好像使用局部名一樣使用這些形式單元。如果實(shí)在參數(shù)不為指示器，那末，在被調(diào)用段中無法改變實(shí)參的值。傳名：所謂傳名，是一種特殊的形實(shí)參數(shù)結(jié)合方

16、式。解釋“傳名”參數(shù)的意義：過程調(diào)用的作用相當(dāng)于把被調(diào)用段的過程體抄到調(diào)用出現(xiàn)的地方，但把其中任一出現(xiàn)的形式參數(shù)都替換成相應(yīng)的實(shí)在參數(shù)(文字替換)。它與采用“傳地址”或“傳值”的方式所產(chǎn)生的結(jié)果均不相同。(a)2；(b)8；(c)7；(d)9。9盛威網(wǎng)（）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站編譯原理課后習(xí)題答案第九章問題 6：下面程序的結(jié)果是 120，但是如果把第 11 行的 abs(1)改成 1 的話，則程序結(jié)果是 1,分析為什么會(huì)有這樣不同的結(jié)果。int fact()static int i=5; if(i=0)return(i);elsei=i-1;return(i+abs(1)*fact();/*第

17、11 行*/main()printf(factor of 5=%dn,fact();答案：i 是靜態(tài)變量，所有地方對(duì) i 的操作都是對(duì)同一地址空間的操作，所以每次遞歸進(jìn)入 fact 函數(shù)后，上一層對(duì) i 的賦值仍然有效。值得注意的是，每次遞歸時(shí)，(i+abs(1)*fact()中 (i+abs(1)的值都先于 fact 算出。所以，第 1 次遞歸時(shí)，所求值為 5*fact,第 2 次遞歸時(shí)，所求值為 4*fact，第 3 次遞歸時(shí)，所求值為 3*fact，如此類推，第 5 次遞歸時(shí)所求值為 1*fact,而此時(shí) fact 值為 1。這樣一來，實(shí)質(zhì)上是求一個(gè)階乘函數(shù) 5*4*3*2*1，所以結(jié)果

18、為 120。之所以改動(dòng) abs(1)為 1 后會(huì)產(chǎn)生變化，這主要和編譯時(shí)的代碼生成策略有關(guān)。對(duì)于表達(dá)式(i+abs(1)*fact()，因兩個(gè)子表達(dá)式都有函數(shù)調(diào)用，因此編譯器先產(chǎn)生左子表達(dá)式代碼，后產(chǎn)生右子表達(dá)式代碼。當(dāng) abs(1)改成 1 后，那么左子表達(dá)式就沒有函數(shù)調(diào)用了，于是編譯器會(huì)先產(chǎn)生右子表達(dá)式代碼，這樣一來，每次遞歸時(shí)，(i+abs(1)*fact()如 c4)中(i+abs(1)的值都后于 fact 算出。第 1 次遞歸時(shí)，所求值為(i+1)*fact，第 2 次遞歸時(shí)，所求值為(i+1)*fact，第 3 次遞歸時(shí)，所求值為(i+1)*fact，如此類推，第 5 次遞歸時(shí)所求

19、值為(i+1)*fact，而此時(shí) fact 為 1，i 為 0。這樣每次遞歸時(shí)所求的實(shí)際都是 1*fact，最后輸出還是 1。因此有不問的結(jié)果。10盛威網(wǎng)（）專業(yè)的計(jì)算機(jī)學(xué)習(xí)網(wǎng)站編譯原理課后習(xí)題第九章問題 7：下面是一個(gè)c 語言程序及其運(yùn)行結(jié)果。從運(yùn)行結(jié)果看，函數(shù) FUNC 中 4 個(gè)局部變量 i1,j1， f1，e1 的地址間隔和它們類型的大小是一致的。而 4 個(gè)形式參數(shù) i，j，f，e 的地址間隔和它們類型的大小不一致，試分析不一致的原因。#includestdio.h FUNC(i,j,f,e) short i,j;float f,e；shor i1,j1 float f1,e1;i1=i;j1=j;f1=f;e1=e;prprf(Addrsses of i,j,f,e%ld %ld %ld %ldn,&i,&j,&f,&e); f(Addrsses of i1,j1,f1,e1%ld %ld %ld %ldn, &i1,&j1,&f1,&e1);prf(size of short,long,float,double%ld %ld %ld %ldn,sizeof(short),sizeof(),sizeof(long),sizeof(float),sizeof(double);main()s