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

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

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

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

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

5、突，設(shè)計實現(xiàn)一個再散列算法。答案：可采用下列散列雜湊算法（設(shè)表長為 N） 散列地址=MOD（+），N）。發(fā)生沖突時再散列的方法：在該沖突處開始，向下尋找第一個空表項，若找到則該表項地址為再散列地址；若找不到空表項，則循環(huán)到表頭開始，向下尋找第一個空表項，一直到發(fā)生沖突處為止，若找到空表項則該表項地址為再散列地址，否則表示符號表已滿，編譯系統(tǒng)給出符號表溢出信息，終止編譯。2盛威網(wǎng)（）專業(yè)的計算機學(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)一個過程作為參數(shù)被傳遞時，我們假定

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

9、行上的非局部量 m 將分別處在第（6）行、（10）行和（3）行上的 m 的說明的作用域中。圖示出每個過程的活動記錄。試為此程序畫出活動樹。試給出程序的輸出。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è)的計算機學(xué)習(xí)網(wǎng)站parama控制鏈訪問鏈c控制鏈訪問鏈mr控制鏈訪問鏈mb控制鏈訪問鏈mfn = 2控制鏈訪問鏈編譯原理課后習(xí)題第九章傳遞環(huán)境活動環(huán)境param控制鏈鏈c控制鏈鏈mr控制鏈鏈b控制鏈鏈fn = 2控制鏈 鏈5盛威網(wǎng)（）專

11、業(yè)的計算機站parama控制鏈 鏈c控制鏈鏈r控制鏈m鏈b控制鏈鏈fn = 2控制鏈鏈編譯原理課后習(xí)題第九章（b）活動樹param crb (f (2)（c）詞法環(huán)境：2；傳遞環(huán)境：9；活動環(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 時，本程序執(zhí)行期間對運行棧的分配圖。：param控制鏈鏈func控制鏈鏈N

12、=3func控制鏈鏈2func控制鏈鏈6盛威網(wǎng)（）專業(yè)的計算機站編譯原理課后習(xí)題第九章問題 4：某語言允許過程嵌套定義和遞歸調(diào)用(如 Pascal 語言)，若在棧式動態(tài)分配中采用嵌套層次顯示表 display 解決對非局部變量的 10；”時運行棧及 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è)的計算機站編譯原理課后習(xí)題第九章：8盛威網(wǎng)（）專業(yè)的計算機站編譯原理課后習(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ù)的地址傳遞給相應(yīng)的形式參數(shù)。在過程段中每個形式參數(shù)都有一對應(yīng)的單元，稱為形式單元。形式單元將用來存放相應(yīng)的實在參數(shù)的地址。當(dāng)調(diào)用一個過程時，調(diào)用段必須領(lǐng)先把實在參數(shù)的地址傳遞到一個為被調(diào)用段可以拿得到的地方。當(dāng)程序控制轉(zhuǎn)入被調(diào)用段之后，被調(diào)用段首先把實參地址捎進自己相應(yīng)的形式單元中，過程體對形式參數(shù)的任何引用 1 或賦值都被處理成對形式單元的間接訪問。當(dāng)調(diào)用段工作完畢返回時，形式單元(它們都是指示器)所指的實在參數(shù)單元就持有所指望的值。傳結(jié)果：和“傳地址”相似(但不等價)的另一

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

16、式。解釋“傳名”參數(shù)的意義：過程調(diào)用的作用相當(dāng)于把被調(diào)用段的過程體抄到調(diào)用出現(xiàn)的地方，但把其中任一出現(xiàn)的形式參數(shù)都替換成相應(yīng)的實在參數(shù)(文字替換)。它與采用“傳地址”或“傳值”的方式所產(chǎn)生的結(jié)果均不相同。(a)2；(b)8；(c)7；(d)9。9盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站編譯原理課后習(xí)題答案第九章問題 6：下面程序的結(jié)果是 120，但是如果把第 11 行的 abs(1)改成 1 的話，則程序結(jié)果是 1,分析為什么會有這樣不同的結(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)變量，所有地方對 i 的操作都是對同一地址空間的操作，所以每次遞歸進入 fact 函數(shù)后，上一層對 i 的賦值仍然有效。值得注意的是，每次遞歸時，(i+abs(1)*fact()中 (i+abs(1)的值都先于 fact 算出。所以，第 1 次遞歸時，所求值為 5*fact,第 2 次遞歸時，所求值為 4*fact，第 3 次遞歸時，所求值為 3*fact，如此類推，第 5 次遞歸時所求值為 1*fact,而此時 fact 值為 1。這樣一來，實質(zhì)上是求一個階乘函數(shù) 5*4*3*2*1，所以結(jié)果

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

19、值為(i+1)*fact，而此時 fact 為 1，i 為 0。這樣每次遞歸時所求的實際都是 1*fact，最后輸出還是 1。因此有不問的結(jié)果。10盛威網(wǎng)（）專業(yè)的計算機學(xué)習(xí)網(wǎng)站編譯原理課后習(xí)題第九章問題 7：下面是一個c 語言程序及其運行結(jié)果。從運行結(jié)果看，函數(shù) FUNC 中 4 個局部變量 i1,j1， f1，e1 的地址間隔和它們類型的大小是一致的。而 4 個形式參數(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