Trình biên dịch - Chương 7: Môi trường thời gian thực hiện

trỏ tới nó (ví dụ 7.8a, 7.8c) 
 Trường hợp 2: j >= i: Ghi giá trị cũ của d[i] vào mẩu tin kích hoạt mới và đặt d[i] 
trỏ vào mẩu tin cuối. (ví dụ 7.8b và 7.8d) 
5. Tầm động 
 Với khái niệm tầm động, một hoạt động mới kế thừa sự liên kết đã tồn tại của một 
tên không cục bộ. Tên không cục bộ a trong hoạt động của chương trình được gọi 
tham khảo đến cùng một ô nhớ như trong hoạt động của chương trình gọi. Ðối với tên 
cục bộ thì một liên kết mới được thiết lập tới ô nhớ trong mẩu tin hoạt động mới. 
 d[1] 
 d[2] 
 d[3] 
s 
q(1,9) 
saved d[2] 
q(1,3) 
saved d[2] 
p(1,3) 
saved d[3] 
(c) 
 d[1] 
 d[2] 
 d[3] 
s 
q(1,9) 
saved d[2] 
q(1,3) 
saved d[2] 
p(1,3) 
saved d[3] 
e(1,3) 
saved d[2] 
(d) 
 158
 Ví dụ 7.9: Xét chương trình: 
 (1) program dynamic (input, output); 
(2) var r : real; 
(3) procedure show; 
(4) begin write(r : 5 : 3); end; 
(5) procedure small; 
(6) var r : real; 
(7) begin r := 0.125; show; end; 
(8) begin 
(9) r := 0.25; 
(10) show, small, writeln; 
(11) end; 
Hình 7.16 - Kết quả chương trình tùy thuộc vào tầm động hay tầm tĩnh được sử dụng 
 Kết quả thực hiện chương trình: 
• Dưới tầm tĩnh; 
0.250 0.250 
• Dưới tầm động: 
0.250 0.125 
 Khi show được gọi tại dòng 10 trong chương trình chính thì 0.250 được in ra vì r 
của chương trình chính được sử dụng. Tuy nhiên khi show được gọi tại dòng 7 trong 
small thì 0.125 được in ra vì r của chương trình con small được sử dụng. Cơ chế tầm 
động sử dụng liên kết điều khiển để tham khảo tên không cục bộ. 
Show được gọi tại dòng 10 
tham khảo r= 0.25 
Dynamic 
r = 0.25 
show 
control link 
Dynamic 
r = 0.25 
small 
control link 
r = 0.125 
show 
control link 
Show được gọi tại dòng 7 
tham khảo r = 0.125 
 159
Hình 7.17 - Sử dụng liên kết điều khiển để tham khảo các tên không cục bộ 
V. TRUYỀN THAM SỐ 
 Khi một chương trình con gọi một chương trình con khác thì phương pháp thông 
thường để giao tiếp giữa chúng là thông qua tên không cục bộ và thông qua các tham 
số của chương trình được gọi. 
 Ví dụ 7.10: Ðể đổi hai giá trị a[i] và a[j] cho nhau ta dùng 
(1) procedure exchange(i,j : integer); 
(2) var x : integer; 
(3) begin 
(4) x := a[i]; a[i] := a[j]; a[j] := x; 
(5) end; 
 trong đó mảng a là tên không cục bộ và i,j là các tham số. 
 Có rất nhiều phương pháp truyền tham số như: 
- Truyền bằng giá trị (Transmision by value, call- by-value) 
- Truyền bằng tham khảo (Transmision by name, call- by-name)... 
 Ở đây chúng ta xét hai phương pháp phổ biến nhất: 
1. Truyền bằng giá trị 
 Là phương pháp đơn giản nhất của truyền tham số được sử dụng trong C và Pascal. 
Truyền bằng giá trị được xử lý như sau: 
1. Tham số hình thức được xem như là tên cục bộ do đó ô nhớ của các tham số 
hình thức nằm trong mẩu tin kích hoạt của chương trình được gọi. 
2. Chương trình gọi đánh giá các tham số thực tế và đặt các giá trị của chúng 
vào trong ô nhớ của tham số hình thức. 
2. Truyền tham chiếu (truyền địa chỉ hay truyền vị trí) 
 Chương trình gọi truyền cho chương trình được gọi con trỏ tới địa chỉ của mỗi một 
tham số thực tế. 
 Ví dụ 7.11: 
 (1) program reference (input, output) 
(2) var i: integer; 
(3) a: array[0...10] of integer; 
(4) procedure swap(var x, y: integer); 
(5) var temp : integer; 
(6) begin 
(7) temp := x; 
 160
(8) x := y; 
(9) y := temp; 
(10) end; 
(11) begin 
(12) i := 1; a[1] := 2; 
(13) swap(i,a[1]); 
(14) end; 
Hình 7.18 - Chương trình Pascal với thủ tục swap 
 Với lời gọi tại dòng (13) ta có các bước sau: 
1. Copy địa chỉ của i và a[ i] vào trong mẩu tin hoạt động của swap thành arg1, 
arg2 tương ứng với x, y. 
2. Ðặt temp bằng nội dung của vị trí được trả về bởi arg1 tức là temp := 1. 
Bước này tương ứng lệnh temp := x trong dòng (7) của swap. 
3. Ðặt nội dung của vị trí được trỏ bằng arg1 bởi giá trị của vị trí được trả bởi 
arg2, tức là i := a[1]. Bước này tương ứng lệnh x := y trong dòng (8) của 
swap. 
4. Ðặt nội dung của vị trí được trỏ bởi arg2 bởi giá trị của temp. Tức là a[1] := 
i. Bước này tương ứng lệnh y := temp. 
VI. BẢNG KÝ HIỆU 
 Chương trình dịch sẽ sử dụng bảng ký hiệu để lưu trữ thông tin về tầm vực và mối 
liên kết của các tên. Bảng ký hiệu được truy xuất nhiều lần mỗi khi một tên xuất hiện 
trong chương trình nguồn. 
 Có hai cơ chế tổ chức bảng ký hiệu là danh sách tuyến tính và bảng băm. 
1. Cấu trúc một ô của bảng ký hiệu 
 Mỗi ô trong bảng ký hiệu tương ứng với một tên. Ðịnh dạng của các ô này thường 
không giống nhau vì thông tin lưu trữ về một tên phụ thuộc vào việc sử dụng tên đó. 
Thông thường một ô được cài đặt bởi một mẩu tin. Nếu muốn có được sự đồng nhất 
của các mẩu tin ta có thể lưu thông tin bên ngoài bảng ký hiệu, trong mỗi ô của bảng 
chỉ chứa các con trỏ trỏ tới thông tin đó, 
 Trong bảng ký hiệu cũng có thể có lưu các từ khóa của ngôn ngữ. Nếu vậy thì 
chúng phải được đưa vào bảng ký hiệu trước khi bộ phân tích từ vựng bắt đầu. 
2. Vấn đề lưu trữ lexeme của danh biểu 
 Các danh biểu trong các ngôn ngữ lập trình thường có hai loại: Một số ngôn ngữ 
quy định độ dài của danh biểu không được vượt quá một giới hạn nào đó. Một số khác 
không giới hạn về độ dài. 
 161
 Trường hợp danh biểu bị giới hạn về độ dài thì chuỗi các ký tự tạo nên danh biểu 
được lưu trữ trong bảng ký hiệu. 
 s o r t 
 a 
 r e a d a r r a y 
 i 
Name Attribute 
Hình 7.19 - Bảng ký hiệu lưu giữ các tên bị giới hạn độ dài 
 Trường hợp độ dài tên không bị giới hạn thì các Lexeme được lưu trong một mảng 
riêng và bảng ký hiệu chỉ giữ các con trỏ trỏ tới đầu mỗi Lexeme 
Name Attribute 
Hình 7.20 - Bảng ký hiệu lưu giữ các tên không bị giới hạn độ dài 
3. Tổ chức bảng ký hiệu bằng danh sách tuyến tính 
 Cấu trúc đơn giản, dễ cài đặt nhất cho bảng ký hiệu là danh sách tuyến tính của các 
mẩu tin. Ta dùng một mảng hoặc nhiều mảng tương đương để lưu trữ tên và các thông 
tin kết hợp với chúng. Các tên mới được đưa vào trong danh sách theo thứ tự mà 
chúng được phát hiện. Vị trí của mảng được đánh dấu bởi con trỏ available chỉ ra một 
ô mới của bảng sẽ được tạo ra. 
 Việc tìm kiếm một tên trong bảng ký hiệu được bắt đầu từ available đến đầu bảng. 
Trong các ngôn ngữ cấu trúc khối sử dụng quy tắc tầm tĩnh. Thông tin kết hợp với tên 
có thể bao gồm cả thông tin về độ sâu của tên. Bằng cách tìm kiếm từ available trở về 
đầu mảng chúng ta đảm bảo rằng sẽ tìm thấy tên trong tầng gần nhất. 
s o r t eos a eos r e a d a r r a y eos i eos 
SymTable 
Lexeme 
id1 
info 1
id2 
info2
 162
...
Hình 7.21 - Danh sách tuyến tính các mẩu tin 
4. Tổ chức bảng ký hiệu bằng bảng băm 
 Kỹ thuật sử dụng bảng băm để cài đặt bảng ký hiệu thường được sử dụng vì tính 
hiệu quả của nó. Cấu tạo bao gồm hai phần; bảng băm và các danh sách liên kết. 
 0 
9 
20 
32 
210 
CP m 
match 
last action ws 
Hình 7.22 - Bảng băm có kích thước 211 
 1. Bảng băm là một mảng bao gồm m con trỏ. 
 2. Bảng danh biểu được chia thành m danh sách liên kết, mỗi danh sách liên kết 
được trỏ bởi một phần tử trong bảng băm. 
 Việc phân bổ các danh biểu vào danh sách liên kết nào do hàm băm (hash 
function) quy định. Giả sử s là chuỗi ký tự xác định danh biểu, hàm băm h tác động lên 
s trả về một giá trị nằm giữa 0 và m- 1 h(s) = t => Danh biểu s được đưa vào trong 
danh sách liên kết được trỏ bởi phần tử t của bảng băm. 
 Có nhiều phương pháp để xác định hàm băm. 
 Phương pháp đơn giản nhất như sau: 
1. Giả sử s bao gồm các ký tự c1, c2, c3, ..., ck. Mỗi ký tự cho ứng với một số 
nguyên dương n1, n2, n3,...,nk; lấy h = n1 + n2 +...+ nk. 
2. Xác định h(s) = h mod m 
 163
BÀI TẬP CHƯƠNG VII 
7.1. Hãy dùng quy tắc tầm vực của ngôn ngữ Pascal để xác định tầm vực ý nghĩa của 
các khai báo cho mỗi lần xuất hiện tên a, b trong chương trình sau. Output của chương 
trình là các số nguyên từ 1 đến 4. 
 Program a ( input, output); 
 Procedure b ( u, v, x, y : integer); 
 Var a : record a, b : integer end; 
 b : record a, b : integer end; 
 begin 
 With a do begin a := u ; b := v end; 
 With b do begin a := x ; b := y end; 
 Writeln ( a.a, a.b, b.a, b.b ); 
 end; 
 Begin 
 B ( 1, 2, 3, 4) 
 End. 
7.2. Chương trình sau sẽ in ra giá trị như thế nào nếu giả sử thông số được truyền 
bằng: 
 a) trị 
 b) quy chiếu 
 c) trị - kết quả 
 d) tên 
 Program main ( input, output); 
 Procedure p ( x, y, z ); 
 begin 
 y := y + 1; 
 z := z + x; 
 end; 
 Begin 
 a := 2 ; 
 b := 3 ; 
 p (a +b ; a, a ) 
 print a 
 164
 End. 
7.3. Cho đoạn chương trình trong Algol như sau : 
 begin ... 
 Procedure A ( px); procedure px { tham số hình thức px là thủ tục } 
 begin 
 procedure B ( pz); procedure pz { tham số hình thức pz là thủ tục } 
 begin 
 .... 
 pz; 
 .... 
 end; 
 B (px); 
 end; 
 procedure C; 
 begin 
 procedure D; 
 begin ... end; 
 A(D); 
 end; 
 C; 
 end. 
Hãy giải thích quá trình thực thi của chương trình trên, các bước truyền tham số 
(giải thích bằng hình ảnh của Stack). 
7.4. Cho đoạn chương trình sau: 
 var a, b : integer; 
 Procedure AB 
 Var a, c : real; 
 k, l : integer; 
 procedure AC 
 Var x, y : real; 
 b : array [ 1 .. 10] of integer; 
 begin 
 165
 .... 
 end; 
 begin 
 .... 
 end; 
 begin 
 .... 
 end. 
Hãy xây dựng bảng ký hiệu thao các phương pháp sau: 
a) Danh sách tuyến tính 
b) Băm (hash), nếu giả sử ta có kết quả của hàm biến đổi băm như sau: 
 a = 3; b = 4; c = 4; k = 2; l = 3; 
 x = 4; y = 5; AB = 2; AC = 6; 
7.5. Cho đoạn chương trình sau: 
 Program baitap; 
 Var a : real; 
 procedure sub1 ; 
 Var x, y : real; 
 begin 
 .... 
 end; 
 procedure sub2 (t :integer); 
 Var k : integer; 
 procedure sub3 ; 
 Var m : real; 
 begin 
 .... 
 end; 
 procedure t; 
 Var x, y : real; 
 begin 
 .... 
 end; 
 166
 begin 
 .... 
 end. 
Hãy vẽ bảng ký hiệu cho từng chương trình con có con trỏ trỏ đến bảng ký hiệu 
của chương trình bị gọi và có con trỏ trỏ ngược lại bảng ký hiệu của chương trình gọi 
nó. 
 167