Giáo trình Xây dựng chương trình dịch - Chương VII: Môi trường thời gian thực hiện

Nội dung text: Giáo trình Xây dựng chương trình dịch - Chương VII: Môi trường thời gian thực hiện

1. CHƯƠNG VII MÔI TRƯỜNG THỜI GIAN THỰC HIỆN Nội dung chính: Trước khi xem xét vấn đề sinh mã được trình bày ở các chương sau, chương này trình bày một số vấn đề liên quan đến việc gọi thực hiện chương trình con, các chiến lược cấp phát bộ nhớ và quản lý bảng ký hiệu. Cùng một tên trong chương trình nguồn có thể biểu thị cho nhiều đối tượng dữ liệu trong chương trình đích. Sự biểu diễn của các đối tượng dữ liệu tại thời gian thực thi được xác định bởi kiểu của nó. Sự cấp phát và thu hồi các đối tượng dữ liệu được quản lý bởi một tập các chương trình con ở dạng mã đích. Việc thiết kế các chương trình con này được xác định bởi ngữ nghĩa của chương trình nguồn. Mỗi sự thực thi của một chương trình con được gọi là một mẩu tin kích hoạt. Nếu một chương trình con đệ quy, một số mẩu tin kích hoạt có thể tồn tại cùng một thời điểm. Mỗi ngôn ngữ lập trình đều có quy tắc tầm vực để xác định việc xử lý khi tham khảo đến các tên không cục bộ. Tùy vào ngôn ngữ, nó cho phép một chương trình chứa các chương trình con lồng nhau hoặc không lồng nhau; Cho phép gọi đệ quy hoặc không đệ quy; Cho phép truyền tham số bằng giá trị hay tham chiếu Vì thế, khi thiết kế một chương trình ở dạng mã đích ta cần chú ý đến các yếu tố này. Mục tiêu cần đạt: Sau khi học xong chương 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ớ. Kiến thức cơ bản: Sinh viên phải biết một số 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). Tài liệu tham khảo: [1] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing Company, 1986. [2] Modern Compiler Implementation in C - Andrew W. Appel - Cambridge University Press, 1997. I. CHƯƠNG TRÌNH CON 1. Ðịnh nghĩa chương trình con Ðị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ó. Ví dụ 7.1: Chương trình Pascal đọc và sắp xếp các số nguyên 142
2. 2. 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. Ví dụ 7.2: Xét chương trình sort nói trên - Bắt đầu thực hiện chương trình. - Vào readarray. - Ra khỏi readarray. - Vào quicksort(1,9). - Vào partition(1,9) - Ra khỏi partition(1,9) // giả sử trả về 4 - Vào quicksort(1,3) - . . . - Ra khỏi quicksort(1,3). - Vào quicksort(5,9); - - Ra khỏi quicksort(5,9). - Sự thực hiện kết thúc. 144
3. 4. 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). 5. 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 đó môi trường trạng thái tên ô nhớ giá trị Hình 7.5 - Hai ánh xạ từ tên tới giá trị Môi trường khác trạng thái: một lệnh gán làm thay đổi trạng thái nhưng không thay đổi môi trường. Khi một môi trường kết hợp vị trí ô nhớ s với một tên x ta nói rằng x được liên kết tới s. Sự kết hợp đó được gọi là mối liên kết của x. Liên kết là một bản sao động (dynamic counterpart) của sự khai báo. Chúng ta có sự tương ứng giữa các ký hiệu động và tĩnh: Ký hiệu tĩnh Bản sao động Ðịnh nghĩa chương trình con Sự hoạt động cuả chương trình con Sự khai báo tên Liên kết của tên Tầm vực của sự khai báo Thời gian tồn tại của liên kết Hình 7.6 - Sự tương ứng giữa ký hiệu động và tĩnh 6. Các vấn đề cần quan tâm khi làm 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. 146
4. Hình 7.7 - Phân chia bộ nhớ trong thời gian thực hiện cho mã đích và các vùng dữ liệu khác 2. Mẩu tin hoạt động Thông tin cần thiết để thực hiện một chương trình con được quản lý bằng cách dùng một mẩu tin hoạt động bao gồm một số trường như sau : Giá trị trả về Các tham số th ực tế Liên kết điều khiển Liên kết truy nhập Trạng thái máy Dữ liệu cục bộ Giá trị tạm thời Hình 7.8 - Mẩu tin hoạt động tổng quát Ý nghĩa các trường như sau: 1. Giá trị tạm thời: được lưu giữ trong quá trình đánh giá biểu thức. 2. Dữ liệu cục bộ: Lưu trữ dữ liệu cục bộ trong khi thực hiện chương trình con. 3. Trạng thái máy: lưu giữ thông tin về trạng thái của máy trước khi một chương trình con được gọi. Thông tin máy bao gồm bộ đếm chương trình và thanh ghi lệnh mà nó sẽ phục hồi khi điều khiển trả về từ chương trình con 4. Liên kết truy nhập: tham khảo tới dữ liệu không cục bộ được lưu trong các mẩu tin hoạt động khác. 5. Liên kết điều khiển: trỏ tới mẩu tin hoạt động của chương trình gọi. 6. Các tham số thực tế: được sử dụng bởi các chương trình gọi để cho chương trình được gọi. Thông thường các tham số được lưu trong thanh ghi chứ không phải trong mẩu tin hoạt động. 7. Giá trị trả về: được dùng bởi chương trình được gọi để trả về cho chương trình gọi một giá trị. Trong thực tế giá trị này thường được trả về trong thanh ghi. III. CHIẾN LƯỢC CẤP PHÁT BỘ NHỚ Ðố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. 148
5. s s a: array r q(1,9) q(1,9) i: integer p(1,9) q(1,3) q(1,3) i: integer q(1,0) q(2,3) p(1,3) q(2,3) i: integer Hình 7.9 - Sự cấp phát và lọai bỏ các mẩu tin kích hoạt Bộ nhớ cho dữ liệu cục bộ trong mỗi lần gọi một chương trình con được chứa trong mẩu tin kích hoạt cho lần gọi đó. Như vậy các tên cục bộ được liên kết với bộ nhớ trong mỗi một hoạt động, bởi vì một mẩu tin kích hoạt được push vào Stack khi có một lời gọi chương trình con. Dữ liệu của các biến cục bộ sẽ bị xóa bỏ khi sự thực hiện chương trình con kết thúc. Giả sử thanh ghi top đánh dấu đỉnh của Stack. Tại thời gian thực hiện một mẩu tin kích hoạt có thể được cấp phát hoặc thu hồi bằng cách tăng hoặc giảm thanh ghi top bằòng kích thước của mẩu tin kích hoạt. Gọi thực hiện chương trình con Gọi chương trình con được thực hiện bởi lệnh gọi trong mã đích - lệnh gọi cấp phát một mẩu tin kích hoạt và đưa thông tin vào cho các trường - lệnh trở về sẽ phục hồi các trạng thái máy để chương trình gọi tiếp tục thực hiện Tham số và giá trị trả về Liên kết và trạng thái máy Mẩu tin kích hoạt của chương trình gọi Dữ liệu tạm và cục bộ Trách nhiệm của Tham số và trị trả về chương trình gọi Liên kết và trạng thái máy Mẩu tin kích hoạt của chương trình bị gọi top_sp Dữ liệu tạm và cục bộ Trách nhiệm của chương trình bị gọi Hình 7.10 - Phân chia công việc giữa chương trình gọi và chương trình bị gọi 150
6. Liên kết điều khiển Con trỏ tới A Mẩu tin kích hoạt của p Con trỏ tới B Con trỏ tới C Mảng A Mảng B Các mảng của p Mảng C Liên kết điều khiển Mẩu tin kích hoạt cho q được gọi bởi p top_sp Các mảng của q top Hình 7.11 - Truy xuất các mảng được cấp phát động 3. Cấp phát Heap Chiến thuật cấp phát sử dụng Stack không đáp ứng được các yêu cầu sau: 1. Giá trị của tên cục bộ được giữ lại khi hoạt động của chương trình con kết thúc. 2. Hoạt động của chương trình bị gọi tồn tại sau chương trình gọi. Các yêu cầu trên đều không thể cấp phát và thu hồi theo cơ chế LIFO (Last - In, First - Out) tức là tổ chức theo Stack. Heap là khối ô nhớ liên tục được chia nhỏ để có thể cấp phát cho các mẩu tin kích hoạt hoặc các đối tượng dữ liệu khác. Sự khác nhau giữa cấp phát Stack và Heap là ở chỗ mẩu tin cho một hoạt động được giữ lại khi hoạt động đó kết thúc. 152
7. Ngôn ngữ cấu trúc khối sử dụng quy tắc tầm tĩnh. Tầm của một khai báo được cho bởi quy tắc tầm gần nhất (most closely nested). 1. Một khai báo tại đầu một khối xác định một tên cục bộ trong khối đó. Bất kỳ một tham khảo tới tên trong thân khối được xem xét như là một tham khảo tới dữ liệu cục bộ trong khối nếu nó tồn tại. 2. Nếu một tên x được tham khảo trong thân một khối B và x không được khai báo trong B thì x được xem như là một sự tham khảo tới sự khai báo trong B’ là khối nhỏ nhất chứa B. Nếu trong B’ không có một khai báo cho x thì lại tham khảo tới B’’ là khối nhỏ nhất chứa B’. 3. Nếu một khối chứa định nghĩa các khối khác thì mọi khai báo trong các khối con hoàn toàn bị che dấu đối với khối ngoài. Cấu trúc khối có thể cài đặt bằng cách sử dụng cơ chế cấp phát Stack. Khi điều khiển đi vào một khối thì ô nhớ cho các tên được cấp phát và chúng bị thu hồi khi điều khiển rời khỏi khối. 3. Tầm tĩnh với các chương trình con không lồng nhau Quy tắc tầm tĩnh của ngôn ngữ C đơn giản hơn so với Pascal và các định nghĩa chương trình con trong C không lồng nhau. Một chương trình C là một chuỗi các khai báo biến và hàm. Nếu có một sự tham khảo không cục bộ đến tên a trong một hàm nào đó thì a phải được tham khảo bên ngoài tất cả các hàm. Tất cả các tên khai báo bên ngoài hàm đều có thể được cấp phát tĩnh. Vị trí các ô nhớ này được biết tại thời gian dịch do đó một tham khảo tới tên không cục bộ trong thân hàm được xác định bằng địa chỉ tuyệt đối. Các tên cục bộ trong hàm nằm trong mẩu tin hoạt động trên đỉnh Stack và có thể xác định bằng cách sử dụng địa chỉ tương đối. 4. Tầm tĩnh với các chương trình con lồng nhau. Trong ngôn ngữ Pascal các chương trình con có thể lồng nhau nhiều cấp. Ví dụ 7.5: Xét chương trình (1) program sort(input, output); (2) var a: array [0 10] of integer; (3) x : integer; (4) procedure readarray; (5) var y : integer; (6) begin a end; {readarray} (7) procedure exchange(i,j:integer); (8) begin (9) x:= a[i]; a[i] := a[j]; a[j] := x; (10) end; {exchange} (11) procedure quicksort(m,n:integer); (12) var k,v: integer; 154
8. s s a,x a,x q(1,9) q(1,9) accessq(1,9) link access link accessk,v k,v link q(1,3) q(1,3)k,v access link access link k,v k,v p(1,3) p(1,3) access link access link i,j i,j (c) e(1,3) access link (d) Hình 7.14 - Liên kết truy xuất cho phép tìm kiếm ô nhớ của các tên không cục bộ Liên kết truy xuất của s rỗng vì s không có bao đóng. Liên kết truy xuất của một mẩu tin kích hoạt của một chương trình con bất kỳ đều trỏ đến mẩu tin kích hoạt của bao đóng của nó. Giả sử chương trình con p có độ lồng sâu np tham khảo tới một tên không cục bộ a có độ lồng sâu na cần hạ hai cấp Từ p(1,3) hạ một cấp đến q(1,3) theo liên kết truy xuất. Từ q(1,3) hạ một cấp đến s theo liên kết truy xuất đến s là nơi a được khai báo. 156
9. s d[1] s d[1] d[2] q(1,9) d[2] q(1,9) d[3] saved d[2] d[3] saved d[2] q(1,3) q(1,3) saved d[2] saved d[2] (c) (d) p(1,3) p(1,3) saved d[3] saved d[3] e(1,3) saved d[2] Hình 7.15 - Sử dụng display khi các chương trình con không được truyền như các tham số (a): Tình trạng trước khi q(1,3) bắt đầu, quicksort có độ lồng sâu cấp 2, d[2] được gửi cho mẩu tin kích hoạt của quicksort khi nó bắt đầu. Giá trị của d[2] được lưu trong mẩu tin kích hoạt của q(1,9). (b): Khi q(1,3) bắt đầu d[2] trỏ tới mẩu tin kích hoạt mức ứng với q(1,3), giá trị của d[2] lại được lưu trong mẩu tin này. Giá trị này là cần thiết để phục hồi display cũ khi điều khiển trả về cho q(1,9). Như vậy khi một mẩu tin kích họat mới được đẩy vào Stack thì: - Lưu giá trị của d[i] vào mẩu tin đó. - Ðặt d[i] trỏ tới mẩu tin đó. Khi một mẩu tin được pop khỏi Stack thì d[i] được phục hồi. Giả sử một chương trình con có độ lồng sâu cấp j gọi một chương trình con có độ lồng sâu cấp i. Có hai trường hợp xảy ra phụ thuộc chương trình con được gọi có được định nghĩa trong chương trình gọi hay không. Trường hợp 1: j i = j+1: thêm ô nhớ d[i], cấp phát mẩu tin kích hoạt cho chương trình con i, ghi d[i] vào trong đó và đặt d[i] 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. 158
10. 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
11. 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. Name Attribute s o r t a r e a d a r r a y i 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 SymTable Lexeme s o r t eos a eos r e a d a r r a y eos i eos 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. id1 info 1 id2 162 info2
12. 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
13. 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