陳維魁 博士 wkchen@pchome.com.tw 儒林圖書公司 第六章 領域與範圍 陳維魁 博士 wkchen@pchome.com.tw 儒林圖書公司.

Presentation on theme: "陳維魁 博士 wkchen@pchome.com.tw 儒林圖書公司 第六章 領域與範圍 陳維魁 博士 wkchen@pchome.com.tw 儒林圖書公司."— Presentation transcript:

1 陳維魁 博士 wkchen@pchome.com.tw 儒林圖書公司
第六章 領域與範圍 陳維魁 博士 儒林圖書公司

2 大綱 基本概念 可見性 靜態領域法與動態領域法 領域的間隙 區域性資料及其處理方法 活動記錄 顯示堆疊 動態領域法的實作 精選習題

3 基本概念 資料控制的意義 參用環境（referencing environment）
程式執行到一個區塊時，對當時資料存取的管制及資料流向的控制即稱為資料控制 參用環境（referencing environment） 當呼叫程式呼叫副程式時會產生一個參用環境

4 基本概念 參用環境建立的過程 將實際參數（actual parameter）的資訊傳給型式參數（formal parameter）
副程式建立區域變數 當程式流程轉移給副程式時，首先會先參用自己的區域環境，若區域環境處找不到變數的定義，再到呼叫程式處引用非區域變數 假如副程式又呼叫了另一個副程式，此時將產生另一個參用環境 由副程式返回呼叫程式時，參用環境將回復成原來狀況 呼叫程式執行時無法引用副程式內的區域變數

5 可見性 (visibility) 某段程式可參用的變數對該程式而言即為可見(visible)，反之即為不可見
program visibility; var x : integer; procedure A (p : integer); begin end; procedure B (q : integer); begin end; procedure C (r : integer); begin end; begin ... end. 根據左側程式可得以下的區塊圖： 對主程式而言x是可見；p，q，r非可見 對副程式A而言x，p為可見，而q，r非可見 對副程式B而言x，q為可見，而p，r非可見 對副程式C而言x，r為可見，而p，q非可見

6 領域與範圍 領域(scope) (空間) 範圍(extend) (生命週期) 對程式設計師來說，“領域”其實就是指一段空間
代表一段程式本文 範圍(extend) (生命週期) 代表在某段時間內，變數會與儲存其值的儲存體做繫結的動作 對程式設計師來說，“領域”其實就是指一段空間 一個變數的“領域”其實是指這個變數在這段程式內是可被引用的(reference)

7 靜態領域法與動態領域法 靜態領域法 在區塊中未定義的變數，根據程式的結構，在程式中包含其區塊的上一層區塊處尋找此變數是否在此區塊內定義
若找到變數的宣告則變數即是在此區塊內定義 若未找到則繼續往外層尋找直到變數第一次宣告處為止 若搜尋完整個程式仍未找到變數之宣告，則該變數即為未定義之變數

8 Procedure Big var x,y:integer; z:real; procedure SUB1 var x:real; begin x:real; x:=y*z+a; 靜態領域時 y,z是依照哪個宣告 end; procedure SUB2 var y:real; begin y:=2.5; SUB1(); begin y:=2; z:=2.0; SUB2;

9 靜態領域法與動態領域法 動態領域法 又稱為流動繫結法(fluid binding)
變數的型態會在目前的區塊中尋找；尋找的順序為“副程式被呼叫的反順序”

10 實際範例一 就右側採用靜態領域法的程式中，指出每個區塊中所有界定的變數及其性質 A 只看到X B 看到X real Y real
C X int Y int D X int Y real E X int Y int Z real

11 實際範例二 請列出列號6，9，13，16，程式執行時，所能使用的變數名稱及其資料型態， 以「變數名稱：資料型態」表示
6 WXY real Z int 9 VW int XY real Z int 13 XYZ int 16 XZ char Y int 1.PROCEDURE A; 2.VAR X, Y, Z : INTEGER; PROCEDURE B; 5. VAR W, X, Y : REAL; PROCEDURE C; VAR V, W : INTEGER; END {C} END {B} PROCEDURE D; 15. VAR X, Z : CHAR; END {D} END {A}

12 實際範例三 右側的程式 (1) 採取靜態領域，副程式A所列印的x之值為何？ 採取動態領域，副程式A所列印的x之值為何？
靜態:程序A沒有定義x變數，往上一層在main 找到，因此x=5 動態:先從main呼叫B，進入B程序之後再呼叫A，所以x=10 program MAIN； var x:integer; procedure A; begin writeln('x=',x) end; {of procedure A} procedure B; Var x: integer; begin x:=10; A end; {of procedure B} begin {of main} x:=5; B end.

13 領域的間隙 定義 採用靜態領域法的情況下，不正常的否定先前變數的宣告即稱為領域的間隙(hole in scope) 靜態領域是以上層宣告為主

14 領域的間隙範例 program hole_in_scope; var x:real; procedure A; begin x:=x × x ; write(x) end; procedure B； var x:integer; begin A end; begin B end. 在副程式B中，變數x宣告為整數，而在B中呼叫了副程式A，但在主程式中變數x宣告為實數，由靜態領域法可知此時x須使用的型態為實數。此種不正常的否定先前變數宣告的現象即稱之為領域的間隙

15 區域性資料 某個區域內所能引用的資料即稱為區域性資料 區域性資料僅適用某個區域內

16 區域性資料處理方法 保留法(retention)
當副程式結束其執行動作時，會將副程式內區域變數的值保留；當副程式再次被呼叫時會沿用該保留的值做為程式執行之依據 如，Fortran、C、C++、Java及Cobol 採用靜態儲存區配置法(static storage allocation)，也就是在編譯時將記憶體的空間配置給區域變數使用

17 區域性資料處理方法 清除法(deletion)
當副程式結束其執行動作時，會將副程式內區域變數的值清除，因此每次呼叫該副程式時其區域變數的初值是固定的 如，Pascal、Ada、Lisp、APL、C、C++、Java與SNOBOL 採用動態儲存區配法(dynamic storage allocation)，也就是在執行時將記憶體的空間配置給區域變數使用

18 範例 試就右側之程式段分別以清除法及保留法各別說明執行結果為何？ 保留: 程序A呼叫B，P=5
,P:=P+5 P=10, 第二次呼叫B,此時P=10,再執行P:=P+5 P=15 清除:程序A呼叫B，P=5, P:=P+5 P=10, 第二次呼叫B,此時P恢復初始值5，再執行P:=P+5 P=10 procedure B; var P:integer=5; begin write(P); P:=P+5; write(P); end;{B} procedure A; begin … B; … B; end;{A}

19 靜態領域的可見度 靜態領域的可見度，除了本身區域的變數，再加上所有上層領域中可見的變數集合

20 Program example; var a,b:integer; … procedure sub1; var x,y:integer; begin ->(1) x,y in sub1, a,b in example end; procedure sub2; var x:integer; procedure sub3; ->(2) x in sub3, a,b in example sub2的x隱藏 ->(3) x in sub2, a,b in example ->(4) a,b in example end

21 動態領域的可見度 本身區域宣告的變數之外，加上所有尚未終結的程序所宣告的變數

22 Void sub1 { int a,b; ….->(1) a,b in sub1; c in sub2; d in main } Void sub2{ int b,c; …->(2) b,c in sub2; d in main sub1(); Void main(){ int c,d; …->(3) c,d in main sub2();

23 具名常數 用一個名稱當作識別字 優點:1 增加程式的可讀和可靠性，如PI=3.1415 優點2提高程式的維護性 如 program
優點2提高程式的維護性 如 program type intarray=[1..100] of integer; realarray=[1..100] of real; for 1 to 100 如果資料增加到150，程式要改很多部分

24 Program const listlen=100; type intarray=array[1..listlen] of integer; realarray=array[1..listlen] of real; for index:=1 to listlen 資料量修改時，只要更改常數值

25 具名常數的分類 1. 值是常數且靜態繫結 Pascal const size=100; 2. 值是常數運算式且靜態繫結 Modula-2
Length=2*size+1; 3. 值為運算式且動態繫結 LENGTH:const integer:=2*size+1

26 活動記錄 活動記錄(activation record)主要是用在副程式呼叫時
每次作副程式呼叫時就會產生一個相對應的活動記錄，其內記錄了副程式在執行的過程中所有可能參用的資訊 活動記錄的內容 靜態鏈、動態鏈、返回位址、型式參數、區域變數、算術運算暫存值、參數傳遞暫存值、函數傳回值及符號資料 符號的資料主要是記錄此區段所宣告的副程式的名稱及標記(label) 靜態鏈(static link)是指活動記錄的一個欄位，副程式的靜態鏈會指向包含其區塊的活動記錄 動態鏈(dynamic link)也是活動記錄的一個欄位，副程式的動態鏈會指向呼叫它的副程式的活動記錄

27 活動記錄範例 執行時程式段被呼叫的先後順序為： DemoR  S  P  Q
program Demo ; procedure P; begin procedure Q; begin end;{of Q} Q; end;{of P} procedure R; begin procedure S; begin P; end;{of S} S; end;{of R} begin R; end.{of demo} 執行時程式段被呼叫的先後順序為： DemoR  S  P  Q

28 顯示堆疊 顯示(display)堆疊是在採用靜態領域法時，尋找變數在何處定義的方法
顯示的內容是由許多指標組成，這些指標指向目前區塊的活動記錄及包含目前區段之所有區段的活動記錄

29 顯示堆疊範例 procedure main; procedure A; procedure B; …. end B; end A; procedure C; procedure D; … end D; procedure E; … end E; end C; end main; Main C  D  E

30 動態領域法的實作 動態領域法的實作方式有二種 深存取(deep access) 淺存取(shallow access)

31 範例 Main begin real x,y,z; procedure P; real i,j,k; procedure Q;
real a,b,x,s; R; end Q; Q; end P; procedure R; real b,c,k,s,t; end R; P; End main;

32 深存取 呼叫順序 main ->P -> Q -> R Main 的參用環境 P的參用環境 Q的參用環境 R的參用環境
X real, y real, z real P的參用環境 X real, y real, z real i real, j real, k real Q的參用環境 a real, b real, x real s real R的參用環境 a real, b real, x real s real b real c real k real s real t real

33 淺存取 main x y z i j k a b s c T 1 main 隱藏堆疊 empty P x y z i j k a b s c
main 隱藏堆疊 empty P x y z i j k a b s c T 1 main P empty

34 Q x y z i j k a b s c T 1 Q main P X main R x y z i j k a b s c T 1 Q main P R X K b S main P Q

35 練習 假設區段結構中的靜態巢狀樹如下所示：則 (a) 在B的程式段中 (b) 在F的程式段中 可以調用那些程式單元？

36 Ans (a) B可呼叫的程式單元為A，B，C，D。 (b) F可呼叫的程式單元為A，B，E，F，G。

37 習題 一個變數(variable)，觀念上可分為以下六個成份：變數名稱(name)，所佔空間地址，此空間可儲存資料的型態(type)此空間所儲存的值(value)，其領域(scope)，及其生命期間(life time)。 (1)試解釋在C的程序執行時，在什麼狀況下同一個次程序的同一個變數名稱會代表不同的空間地址；而在什麼狀況下，不同的變數名稱會代表同空間地址。 (2)試簡述以下語言變數的生命週期(其佔有的空間，何時開始存在，何時停止存在)。Pascal local variables，C的static variables，Pascal的pointer variable所指的空間。

38 Ans (1) a. 遞迴呼叫(recursive call)。 b. 別名(aliasing)。
(2) a. Pascal的local variables：動態儲存區配置。 b. C的static variables：程式執行過程中始終完整存在。 c. Pascal的pointer variable：執行new()時開始存在，而執行dispose()時停止存在。

39 練習 在一個程式中，變數為何要區分為「local」與「global」？如果變數只能宣告是local而不能是global，有沒有什麼優缺點？反之，如果變數只能宣告是global而不能是local，有沒有什麼優缺點？

40 Ans (1) 變數區分為local與global的主要理由是讓程式設計師較易區分變數等級使程式設計的工作更為容易。
a. 優點： (i)保密性高。 (ii)不須考慮資料共用的問題。 (iii)程式結構較單純。 (iv)程式易除錯。 (v)程式易維護。 b. 缺點： (i)程式設計的彈性較低。 (ii)無法達到資料共用之目的。 (3) 只能宣告global變數： a. 優點： (i)程式設計的彈性較大。 (ii)可製作較複雜的程式。 (iii)可達到資料共用的目的。 b. 缺點： (i)保密性較差。 (ii)須考慮資料共用的問題。 (iii)程式結構較複雜。 (iv)程式較不易維護。

41 練習 試比較何謂： (a) 懸置引用(dangling reference)。 (b) 懸置else(dangling else)。
(c) 懸置標記引用(dangling label reference)。

42 Ans (a)懸置引用：懸置引用是指指標變數欲引用(reference)一個已經不存在的記憶體空間稱之。
(b)懸置else： 若有以下敘述：if 條件A then if 條件 B then E1 else E2 由於無法確定else將與那個if敘述結合，這種現象就稱為懸置else。 (c)懸置標記引用：若欲引用某個已經離開其領域的標記(label)，則稱此現象為懸置標記引用。

43 練習 試說明保留法與清除法的優點。

44 Ans (1) 保留法優點： a. 副程式中區域變數的值可被保留，所以前後二次執行的關連性較大。 b. 效率較高。 (2) 清除法優點：
(1) 保留法優點： a. 副程式中區域變數的值可被保留，所以前後二次執行的關連性較大。 b. 效率較高。 (2) 清除法優點： a. 副程式中區域變數的值在離開該副程式時不被保留，所以可節省記憶體空間，即程式不被執行時不會佔據記憶體空間。 b. 可用於遞迴副程式。 理由： 因為遞迴呼叫的特點在於執行時才會知道呼叫幾次，也就是在執行時才知道需要多少記憶體空間，因此只有動態儲存區配置法(dynamic storage allocation)才能支援遞迴呼叫，所有只有清除法提供遞迴呼叫功能。

45 練習 試分別說明根據：(a)靜態領域法 (b)動態領域法，下列程式所得到的結果分別為何？
program scope; var test: boolean; 　　　procedure A; 　　　begin 　　　　writeln(test) 　　　end; 　　　procedure B; 　　　var test:boolean; 　　　begin 　　　　test:=true; 　　　　A 　　　end; begin 　　　test:=false; 　　　B end.

46 Ans (a) 靜態領域法結果為false。 (b) 動態領域法結果為true。

47 練習 下面程式是用像pascal (pascal-like)的語言所寫，如分別用靜態及動態領域處理變數的範圍，請問程式執行後，所印出來的值各為何？ program main； var x : integer; procedure sub1; begin /* sub1 */ writeln('x=',x) end; /* sub1 */ procedure sub2; var x: integer; begin /* sub2 */ x:=10; sub1 end; /* sub2 */ begin /* main */ x:=5; sub2 end. /* main */

48 Ans 靜態領域結果為x=5 動態領域結果為x=10

49 練習 考慮下的Pascal程式： Program Main; Var a: integer; Procedure One; Begin writeln(`a=`,a); End; Procedure Two; Var a: integer; Begin a:=88; One; End; Begin a:=77; Two; End. (一) 如果使用靜態領域(static scoping)，則會輸出何值？為甚麼 (二) 如果使用動態領域(dynamic scoping)，則會輸出何值？為甚麼？

50 Ans 靜態範圍結果為a=77 動態範圍結果為a=88

51 練習 假設下列程式採用靜態領域規則,並使用顯示(display)方法來存全域變數。請繪出當此程式呼叫副程式P並進入P後的執行時期堆疊及顯示堆疊關係圖。 procedure A procedure B procedure P begin end P; procedure C begin call P end C; begin call C; end B; begin call B end;

52 Ans 呼叫順序如下： A B C P

53 練習 請繪出下列程式執行過程中，中央堆疊之變化。請同時繪出靜態鏈(static chain pointers)及動態鏈(dynamic chain pointers)。其中副程式C假設被遞迴呼叫一次就返回(return)。 Program A Procedure B; Procedure C; Call C; end; Call C; end; Call B; end．

54 Ans 執行順序如下： A B C C

55 練習 考慮以下程式： program P; var x, y: integer; procedure A (var Z : integer); var x : integer; begin x:=1; B; Z := x end A; procedure B; begin x := x + 1 end B; begin x:=5; A(y); write(y) end． 假如用(1) static scoping？(2) dynamic scoping？則程式印出結果為何？

56 Ans (1) 靜態領域法結果為y=1 (2) 動態領域法結果為y=2

57 考慮下列程式： program p; var X,Y : integer; procedure A; begin x:=x+3; end; procedure B(var Z : integer); var x : integer begin x:=10;A;z:=x end; begin x:=5;B(y); write(y) end． (1) 畫出當程序A被調用時，中央堆疊(central stack)的情況，並標示動態鏈(dynamic chain)和靜態鏈(static chain)。 (2) 假設使用 a.動態範圍規則(dynamic scope rule)則程式印出的結果為何？ b.靜態範圍規則(static scope rule)則程式印出的結果為何？

58 Ans (1) 執行順序為： P B A a. 動態範圍規則 b. 靜態範圍規則： 5 x z y 10 : = x + 3 (在 A
中執行) 13 := x write(y)

59 練習 Program main; 靜態領域和動態領域的輸出X var x:real; procedure sub1;
begin writeln(“x=”,x) end; procedure sub2; begin x:=3.6 sub1 end x:=6.3 sub2

60 Ans 靜態領域 X=6.3 動態領域 X=3.6

61 練習 靜態領域和動態領域的sub1 的XYZ Procedure confuse x,y,z:integer; procedure sub1
begin end; procedure sub2 x:integer; sub1; sub2;

62 Ans 靜態領域sub1的x,y由confuse z由sub1 動態領域的x由sub2, y由confuse, z由sub1