Bài giảng Chương trình dịch

d := v + u ADD R1, R0 
MOV R0, d 
R0 chứa d d trong R0 
d trong R0 và 
72 
trong bộ nhớ 
- Nội dung thảo luận: Sinh mã đích cho các biểu thức điều kiện và vòng lặp 
- Yêu cầu SV chuẩn bị 
Tìm hiểu về sinh mã đích cho các cấu trúc khác trong ngôn ngữ lập trình: 
khai báo, hàm… 
- Bài tập bắt buộc 
1. Chuyển các câu lệnh hoặc đoạn chương trình sau thành mã ba địa chỉ: 
1) a * - (b+c) 
2) đoạn chương trình C 
main () 
{ int i; int a[100]; 
 i=1; 
 while(i<=10) 
{ a[i]=0; 
 i=i+1;} 
} 
2. Dịch biểu thức : a * - ( b + c) thành các dạng : 
 a) Cây cú pháp. 
 b) Ký pháp hậu tố. 
 c) Mã lệnh máy 3 - địa chỉ. 
Trình bày cấu trúc lưu trữ biểu thức 
( a + b) * ( c + d ) + ( a + b + c) 
ở các dạng : a) Bộ tứ . b) Bộ tam. c) Bộ tam gián tiếp. 
3. Sinh mã trung gian (dạng mã máy 3 - địa chỉ) cho các biểu thức C đơn 
giản sau : 
 a) x = 1 b) x = y 
 c) x = x + 1 d) x = a + b * c 
 e) x = a / ( b + c) - d * ( e + f ) 
- Bài tập nâng cao 
4. Sinh mã trung gian (dạng mã máy 3 - địa chỉ) cho các biểu thức C sau: 
 a) x = a [i] + 11 b) a [i] = b [ c[j] ] 
 c) a [i][j] = b [i][k] * c [k][j] d) a[i] = a[i] + b[j] 
 e) a[i] + = b[j] 
5. Dịch lệnh gán sau thành mã máy 3 - địa chỉ : 
73 
 A [ i,j ] := B [ i,j ] + C [A[ k,l]] + D [ i + j ] 
- Tài liệu tham khảo 
1. Compilers : Principles, Technique and Tools. A.V. Aho, M. Lam, R. 
Sethi, J.D.Ullman. - Addison -Wesley 2nd Edition, 2007. Chương 7. 
2. Advanced Compiler Design and Implementation. S. Muchnick. 
Morgan-Kaufmann Publishers, 2007. Chương 6. 
3. Giáo trình chương trình dịch 2nd Edition. Phạm Hồng Nguyên. NXB 
ĐHQG Hà Nội, 2009. Chương 6. 
Câu hỏi ôn tập 
1. Các dạng mã máy đối tượng. 
2. Mã 3 địa chỉ là gì. Cho ví dụ minh họa. 
3. Anh\chị hãy trình bày giải thuật sinh mã đích. 
Bài giảng 09: Các vấn đề của trình biên dịch hiện đại 
Chương 9, mục: 
Tiết thứ: 43-45 Tuần thứ: 15 
- Mục đích yêu cầu 
Mục đích: Sau khi học xong bài này, sinh viên phải nắm được: Cách gọi 
và thực thi một chương trình; Cách tổ chức bộ nhớ và các chiến lược cấp phát – 
thu hồi bộ nhớ. 
Yêu cầu: Sinh viên phải nắm vững ít nhất một ngôn ngữ lập trình cấp cao 
như Pascal, C++, Java, v.v hoặc đã được học môn ngôn ngữ lập trình (phần đề 
cập đến các chương trình con). 
- Hình thức tổ chức dạy học: Lý thuyết, thảo luận, tự học, tự nghiên cứu 
- Thời gian: Giáo viên giảng: 2 tiết; Thảo luận và làm bài tập trên lớp: 1 tiết; 
Sinh viên tự học: 6 tiết. 
- Địa điểm: Giảng đường do P2 phân công. 
- Nội dung chính: 
8.1. Ngôn ngữ hướng đối tượng 
8.2. Run-Time Environment 
8.2.1. Chương trình con và cây hoạt động 
8.2.2. Ngăn xếp điều khiển 
8.2.3. Tầm vực của sự khai báo 
8.2.4. Liên kết tên 
74 
8.2.5. Một số vấn đề cần quan tâm khi viết chương trình dịch 
8.3. Bảng ký hiệu 
8.4. Quản lý bộ nhớ và địa chỉ 
8.5. Vấn đề tối ưu mã 
8.1. Ngôn ngữ hướng đối tượng 
8.2. Run-Time Environment 
8.2.1. Chương trình con và cây hoạt động 
Ðịnh nghĩa chương trình con là một sự khai báo nó. Dạng đơn giản nhất là 
sự kết hợp giữa tên chương trình con và thân của nó. 
Cây hoạt động: Trong quá trình thực hiện chương trình thì: 
 1. Dòng điều khiển là tuần tự: tức là việc thực hiện chương trình bao gồm 
một chuỗi các bước. Tại mỗi bước đều có một sự điều khiển xác định. 
 2. Việc thực hiện chương trình con bắt đầu tại điểm bắt đầu của thân 
chương trình con và trả điều khiển về cho chương trình gọi tại điểm nằm sau lời 
gọi khi việc thực hiện chương trình con kết thúc. 
• Thời gian tồn tại của một chương trình con p là một chuỗi các bước giữa 
bước đầu tiên và bước cuối cùng trong sự thực hiện thân chương trình con bao 
gồm cả thời gian thực hiện các chương trình con được gọi bởi p. 
• Nếu a và b là hai sự hoạt động của hai chương trình con tương ứng thì 
thời gian tồn tại của chúng tách biệt nhau hoặc lồng nhau. 
• Một chương trình con là đệ quy nếu một hoạt động mới có thể bắt đầu 
trước khi một hoạt động trước đó của chương trình con đó kết thúc. 
• Ðể đặc tả cách thức điều khiển vào ra mỗi hoạt động của chương trình 
con ta dùng cấu trúc cây gọi là cây hoạt động. 
1. Mỗi nút biểu diễn cho một hoạt động của một chương trình con. 
2. Nút gốc biểu diễn cho hoạt động của chương trình chính. 
3. Nút a là cha của b nếu và chỉ nếu dòng điều khiển sự hoạt động đó từ a 
sang b 
4. Nút a ở bên trái của nút b nếu thời gian tồn tại của a xuất hiện trước thời 
gian tồn tại của b. 
75 
8.2.2. Ngăn xếp điều khiển 
Dòng điều khiển một chương trình tương ứng với phép duyệt theo chiều 
sâu của cây hoạt động. Bắt đầu từ nút gốc, thăm một nút trước các con của nó và 
thăm các con một cách đệ quy tại mỗi nút từ trái sang phải. 
Hình sau trình bày nội dung của Stack đang lưu trữ đường đi từ nút q(2, 3) 
đến nút gốc. Các cạnh nét đứt thể hiện một nút đã pop ra khỏi Stack. 
8.2.3. Tầm vực của sự khai báo 
Ðoạn chương trình chịu ảnh hưởng của một sự khai báo gọi là tầm vực của 
khai báo đó. 
Trong một chương trình có thể có nhiều sự khai báo trùng tên ví dụ biến i 
trong chương trình sort. Các khai báo này độc lập với nhau và chịu sự chi phối 
bởi quy tắc tầm của ngôn ngữ. 
Sự xuất hiện của một tên trong một chương trình con được gọi là cục bộ 
(local) trong chương trình con ấy nếu tầm vực của sự khai báo nằm trong 
chương trình con, ngược lại được gọi là không cục bộ (nonlocal). 
8.2.4. Liên kết tên 
Trong ngôn ngữ của ngôn ngữ lập trình, thuật ngữ môi trường (enviroment) 
để chỉ một ánh xạ từ một tên đến một vị trí ô nhớ và thuật ngữ trạng thái (state) 
để chỉ một ánh xạ từ vị trí ô nhớ tới giá trị lưu trữ trong đó. 
76 
8.2.5. Một số vấn đề cần quan tâm khi viết chương trình dịch 
Các vấn đề cần đặt ra khi tổ chức lưu trữ và liên kết tên: 
1. Chương trình con có thể đệ quy không? 
2. Ðiều gì xảy ra cho giá trị của các tên cục bộ khi trả điều khiển từ hoạt 
động của một chương trình con. 
3. Một chương trình con có thể tham khảo tới một tên cục bộ không? 
4. Các tham số được truyền như thế nào khi gọi chương trình con. 
5. Một chương trình con có thể được truyền như một tham số? 
6. Một chương trình con có thể được trả về như một kết quả? 
7. Bộ nhớ có được cấp phát động không? 
8. Bộ nhớ có phải giải phóng một cách tường minh? 
8.3. Bảng ký hiệu 
Mục đích, nhiệm vụ: Thu thập các thông 
tin về tên; Sử dụng các thông tin về tên 
 Phân tích ngữ nghĩa: kiểm tra việc 
dùng các tên phải khớp với khai 
báo 
 Sinh mã: lấy kích thước, loại bộ 
nhớ phải cấp phát cho một tên 
 Các khối khác: để phát hiện và 
khắc phục lỗi 
Các yêu cầu với bảng kí hiệu: 
 phát hiện một tên cho trước có ở 
trong bảng hay không 
 thêm một tên mới vào bảng 
 lấy thông tin tương ứng với tên cho 
trước 
 thêm các thông tin mới vào một tên 
cho trước 
 xoá một tên hoặc nhóm tên trong bảng 
Thông tin đưa vào bảng ký hiệu: 
 Xâu ký tự tạo nên tên 
 Thuộc tính của tên 
 Các tham số, như số chiều của mảng 
 (Có thể) con trỏ đến tên cấp phát 
Phán têch tæì væûng
Phán têch ngæî
nghéa
Sinh maî trung gian
Sinh maî
Phán têch cuï phaïp
Quaín lyï baíng
kyï hiãûu
Chæång trçnh nguäön
Chæång trçnh âêch
Täúi æu maî
77 
8.4. Quản lý bộ nhớ và địa chỉ 
Bộ nhớ có thể chia ra để lưu trữ các phần: 
1. Mã đích. 
2. Ðối tượng dữ liệu. 
3. Bản sao của Stack điều khiển để lưu trữ hoạt động của chương trình con. 
Ðối với các vùng nhớ khác nhau trong tổ chức bộ nhớ, ta có các chiến lược 
cấp phát khác nhau: 
1. Cấp phát tĩnh cho tất cả các đối tượng dữ liệu tại thời gian dịch. 
2. Cấp phát sử dụng Stack cho bộ nhớ trong thời gian thực hiện. 
3. Ðối với vùng dữ liệu Heap sử dụng cấp phát và thu hồi dạng Heap. 
Gọi thực hiện chương trình con: 
Quy tắc tầm vực 
 Quy tắc tầm vực của ngôn ngữ sẽ xác định việc xử lý khi tham khảo 
đến các tên không cục bộ. 
 Quy tắc tầm vực bao gồm hai loại: Quy tắc tầm tĩnh và quy tắc tầm 
động. 
 Quy tắc tầm tĩnh (static - scope rule): Xác định sự khai báo áp dụng 
cho một tên bằng cách kiểm tra văn bản chương trình nguồn. Các 
ngôn ngữ Pascal, C và Ada sử dụng quy tắc tầm tĩnh với một quy 
định bổ sung: “tầm gần nhất”. 
 Quy tắc tầm động (dynamic- scope rule): Xác định sự khai báo có 
thể áp dụng cho một tên tại thời gian thực hiện bằng cách xem xét 
hoạt động hiện hành. Các ngôn ngữ Lisp, APL và Snobol sử dụng 
quy tắc tầm động. 
- Nội dung thảo luận: vấn đề cấp phát bộ nhớ và địa chỉ 
78 
- Nội dung tự học: Tìm hiểu về các kỹ năng tối ưu mã chương trình, kỹ năng tối 
ưu mã nguồn. 
- Bài tập bắt buộc 
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. 
2. 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 
.... 
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 
79 
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; 
- Bài tập nâng cao 
3. 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ó. 
- Tài liệu tham khảo 
1. Modern Compiler Implementation in C. A.W. Appel - Cambridge 
University Press, 1997. Chương 8. 
2. Giáo trình chương trình dịch 2nd Edition. Phạm Hồng Nguyên. NXB 
ĐHQG Hà Nội, 2009. Chương 7. 
- Câu hỏi ôn tập 
1. Các cách tổ chức bộ nhớ. 
2. Các chiến lược cấp phát – thu hồi bộ nhớ