Bài giảng Nguyên lý ngôn ngữ lập trình - Chương 5: Thực hiện chương trình con - Nguyễn Văn Hòa

1Chương 5: Thực hiện 
chương trỡnh con
Giảng viờn: Ph.D Nguyễn Văn Hũa
Khoa KT-CN-MT – ðH An Giang
2ðịnh nghĩa

 Trong NNLT, tỏc vụ gọi “call” và trả về (return) 
của chương trỡnh con ủược gọi chung là liờn kết 
chương trỡnh con “subprogram linkage”
3Nội dung chớnh của chương

 Giới thiệu chung về ngữ nghĩa của Call và Return

 Thực hiện chương trỡnh con ủơn giản

 Thực hiện chương trỡnh con với biến cục bộ ủộng 
Stack

 Chương trỡnh con lũng nhau (nested 
Subprograms)

 Khối (Blocks)

 Cài ủặt phạm vi ủộng
4Ngữ nghĩa của việc gọi (call) và trả 
về (return)

 Một số tỏc vụ cần thiết cho việc gọi chương trỡnh 
con
 Cơ chế truyền cỏc tham số (truyền tham trị, truyền quy 
chiếu, truyền kết quả, ...) 
 Cỏc biến cục bộ là static hay not static
 Lưu lại trạng thỏi hiện hành (execution status) của 
chương trỡnh gọi CTC
 Chuyển quyền ủiều khiển cho CTC
 Cung cấp cỏc truy xuất ủến cỏc biến khụng cục bộ
5Thực hiện CTC ủơn giản: Call

 Chương trỡnh con ủơn giản “simple”
 Khụng lũng nhau và cỏc biến là tĩnh (static)

 Cỏc tỏc vụ cú cần thiết
 Lưu hiện trạng thực thị của chương trỡnh gọi “caller”
 Thực hiện tiến trỡnh truyền tham số
 Chuyển ủịa chỉ trả về cho chương trỡnh con “callee”
 Chuyển quyền ủiều khiển cho chương trỡnh con 
“callee”
6Thực hiện CTC ủơn giản: Return

 Nếu sử dụng truyền trị-kết quả, thỡ di chuyển giỏ 
trị hiện hành của cỏc tham số hỡnh thức ủến từng 
tham số thực tương ứng

 Nếu là hàm, di chuyển giỏ trị của hàm ủến vị trớ 
mà caller cú thể lấy ủược

 Phục hồi lại trạng thỏi thực thi của caller

 Trả quyền ủiều khiển lại cho caller
7
 Cú 2 phần phõn biệt: phần code thực và phần 
noncode (biến cục bộ và dữ liệu cú thể bị thay 
ủổi)

 ðịnh dạng, hoặc layout, của phần noncode của 
một chương trỡnh thực thi con ủược gọi là bản 
hoạt ủộng (activation)

 Một thể hiện (instance) bản hoạt ủộng là mẫu cụ 
thể của bản hoạt ủộng (bao gồm dữ liệu hoạt 
ủộng của chương trỡnh con)
Thực hiện CTC ủơn giản: Parts
8Bản hoạt ủộng của chương trỡnh 
con ủơn giản
9Code và bản hoạt 
ủộng của chương 
trỡnh với chương 
trỡnh con ủơn giản
10
Cài ủặt CTC với biến cục bộ ủộng Stack

 Bản hoạt ủộng phức tạp
 Trỡnh biờn dịch phải sinh code ủể cấp phỏt và giải 
phúng một cỏch tường minh cho cỏc tham số cục bộ
 Phải hỗ trợ ủệ qui “recursion” (tạo ủồng thời nhiều thể 
hiện bản hoạt ủộng của một chương trỡnh con)
 ðệ qui yờu cầu nhiều thể hiện của bản hoạt ủộng, mỗi 
thể hiện của bản hoạt ủộng tương ứng với 1 một lần 
gọi ủệ qui
 Mỗi thể hiện cầu 1 bản copy cỏc tham số hỡnh thức, 
cỏc biến cục bộ cấp phỏt ủộng và ủịa chỉ trả về
11
Bản hoạt ủộng của NN với biến cục 
bộ ủộng Stack
12
Cài ủặt CTC với biến cục bộ ủộng 
Stack : Bản hoạt ủộng

 ðịnh dạng của bản hoạt ủộng là tĩnh, nhưng kớch 
thước của nú cú thể ủộng

 Liờn kết ủộng (dynamic link) trỏ ủến ủỉnh của bản 
hoạt ủộng của caller

 Bản hoạt ủộng ủược xỏc ủịnh ra một cỏch ủộng 
khi gọi chương trỡnh con

 Run-time stack
13
Vớ dụ: Hàm C
void sub(float total, int part)
{
int list[5];
float sum;
}
14
Vớ dụ khụng ủệ qui
void fun1(int x) {
int y;
...  2
fun3(y);
}
void fun2(float r) {
int s, t;
...  1
fun1(s);
}
void fun3(int q) {
...  3
}
void main() {
float p;
...
fun2(p);
}
Hàm main gọi fun2
Hàm fun2 gọi fun1
Hàm fun1 gọi fun3
15
Vớ dụ khụng ủệ qui
16
Dynamic Chain và Local Offset

 Tập hợp cỏc dynamic links trong stack tại một 
thời ủiểm nào ủú ủược gọi là dynamic chain, 
hoặc call chain

 Cỏc biến cục bộ cú thể ủược truy xuất thụng qua 
cỏc offset của nú trong bản hoạt ủộng. Offset này 
ủược gọi là local_offset

 Local_offset của một biến cục bộ cú thể ủược xỏc 
ủịnh bởi trỡnh biờn dịch ngay thời ủiểm dịch hoặc 
thời ủiểm thực thi
17
Vớ dụ với ủệ qui
int factorial (int n) {
<-----------------------------1
if (n <= 1) return 1;
else return (n * factorial(n - 1));
<-----------------------------2
}
void main() {
int value;
value = factorial(3);
<-----------------------------3
}
18
Bản hoạt ủộng của factorial
19
20
21
Chương trỡnh con lũng nhau

 Vài NNLT với phạm vi tĩnh (e.g., Fortran 95, 
Ada, JavaScript) dựng cỏc biến cục bộ ủộng stack
và cho phộp cỏc chương trỡnh con lũng vào nhau

 Cỏc biến bờn trong cỏc bản hoạt ủộng trong stack 
cú thể ủược truy xuất một cỏch khụng cục bộ

 Hai bước ủể tham chiếu cỏc biến khụng cục bộ:
 Tỡm kiếm thể hiện bản hoạt ủộng tương ứng
 Xỏc ủịnh offset của biến trong thể hiện ủú
22
ðịnh vị cỏc tham chiếu khụng cục bộ

 Tỡm Offset: khỏ dễ dàng

 Tỡm thể hiện bản hoạt ủộng tương ứng
 ðể ủảm bảo cú thể tham chiếu ủến cỏc biến khụng cục 
bộ thỡ cỏc biến này phải ủược cấp phỏt trong cỏc thể 
hiện bản hoạt ủộng trong stack
23

 Static chain là tập hợp cỏc static links liờn kết một 
vài bản hoạt ủộng trong stack

 Static chain là cỏch cài ủặt phổ biến trong cỏc NNLT 
hỗ trợ CTC lũng nhau

 Liờn kết tĩnh (static link) trong một thể hiện bản hoạt 
ủộng nào ủú của 1 CTC là 1 pointer trỏ ủến phần 
dưới cựng của thể hiện bản hoạt ủộng cha, liờn kết 
này dựng ủể truy xuất cỏc biến khụng cục bộ

 Chuỗi tĩnh (static chain) của một thể hiện bản hoạt 
ủộng nào ủú ủều phải kết nối với thể hiện bản hoạt 
ủộng của CTC tổ tiờn (ancestors)
Phạm vi tĩnh
24
VD chương trỡnh Pascal
program MAIN_2;
var X : integer;
procedure BIGSUB;
var A, B, C : integer;
procedure SUB1;
var A, D : integer;
begin { SUB1 }
A := B + C; <-----------------------1
end; { SUB1 }
procedure SUB2(X : integer);
var B, E : integer;
procedure SUB3;
var C, E : integer;
begin { SUB3 }
SUB1;
E := B + A: <--------------------2
end; { SUB3 }
begin { SUB2 }
SUB3;
A := D + E; <-----------------------3
end; { SUB2 }
begin { BIGSUB }
SUB2(7);
end; { BIGSUB }
begin
BIGSUB;
end; { MAIN_2 }
25
Stack ở vi trớ 1
Thứ tự gọi cỏc hàm như sau: 
MAIN_2 calls BIGSUB
BIGSUB calls SUB2
SUB2 calls SUB3
SUB3 calls SUB1
26

 Khối là vựng hay phạm vi hoạt ủộng cỏc biến do người 
dựng chỉ ủịnh 

 VD chương trỡnh C
{int temp;
temp = list [upper];
list [upper] = list [lower];
list [lower] = temp
}

 Thời gian tồn tại của temp trong VD trờn bắt ủầu ngay 
khi chương trỡnh bắt ủầu tiến vào khối

 Ưu ủiểm của việc dựng biến cục bộ như temp là biến 
temps khụng trở ngại nào nếu như cú 1 biến khỏc cựng 
tờn
Khối (blocks)
27
Cài ủặt khối

 Cú hai cỏch:
 Khối ủược xem như là cỏc tham số của chương trỡnh 
con mà nú ủược gọi tại ngay vị trớ của nú
– Mỗi khối cú 1 thể hiện bản hoạt ủộng, nú ủược tạo ra ngay 
thời ủiểm khối ủược thực thi
 Vỡ kớch thước lưu trữ cho 1 khối cú thể xỏc ủịnh 
trong suốt thời gian thực hiện khối, kớch thước này cú 
thể ủược cấp phỏt sau cỏc biến cục bộ trong bản hoạt 
ủộng
28
29
Cài ủặt phạm vi ủộng

 Truy xuất sõu (deep access): Cỏc tham chiếu 
khụng cục bộ cú thể ủược tỡm thấy trong cỏc bản 
hoạt ủộng hiện hữu trong cỏc liờn kết ủộng 
(dynamic chain)

 Truy xuất cạn (shallow access): tập trung cỏc biến 
cục bộ vào một nơi
 Mỗi biến cú 1 stack
 Central table xỏc ủịnh cỏc biến và chương trỡnh con
30
VD chương trỡnh
void sub3(){
int x,z;
x=u+z;
}
void sub2(){
int w,x;
}
void sub1(){
int v,w;
}
void main(){
int v,u;
}
31
Minh họa 
Deep access
main gọi sub2
sub2 gọi sub1
sub1 gọi sub2
sub2 gọi sub3
32
Minh họa Shallow Access
main gọi sub1 (A)
sub1 gọi sub1 
sub1 gọi sub2 (B)
sub2 gọi sub3 (C)