Giáo trình Xây dựng chương trình dịch - Chương VI: Kiểm tra kiểu

Nội dung text: Giáo trình Xây dựng chương trình dịch - Chương VI: Kiểm tra kiểu

1. CHƯƠNG VI KIỂM TRA KIỂU Nội dung chính: Hai cách kiểm tra kiểu là kiểm tra tĩnh được thực hiện trong thời gian biên dịch chương trình nguồn và kiểm tra động được thực hiện trong thời gian thực thi chương trình đích. Trong chương này ta tập trung vào phần xử lý ngữ nghĩa bằng cách kiểm tra tĩnh mà cụ thể là kiểm tra kiểu. Phần đầu của chương trình bày các khái niệm về hệ thống kiểu, các biểu thức kiểu. Phần còn lại mô tả cách tạo ra một bộ kiểm tra kiểu đơn giản. Mục tiêu cần đạt: Sau khi học xong chương này, sinh viên phải nắm được: • Hệ thống kiểu với các biểu thức kiểu (kiểu cơ sở và kiểu có cấu trúc) thường gặp ở bất cứ một ngôn ngữ lập trình nào. • Dịch trực tiếp cú pháp cài đặt bộ kiểm tra kiểu đơn giản từ đó có thể mở rộng để cài đặt cho những ngôn ngữ phức tạp hơn. 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 kiểu cơ sở và kiểu có cấu trúc). 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. [3] Compiler Design – Reinhard Wilhelm, Dieter Maurer - Addison - Wesley Publishing Company, 1996. I. HỆ THỐNG KIỂU Trong các ngôn ngữ nói chung đều có kiểu cơ sở và kiểu có cấu trúc. Chẳng hạn trang Pascal, kiểu cơ sở là: boolean, char, integer, real, kiểu miền con và kiểu liệt kê. Các kiểu có cấu trúc như mảng, mẩu tin, tập hợp, 1. Biểu thức kiểu Biểu thức kiểu bao gồm: 1. Kiểu cơ sở là một biểu thức kiểu: boolean, char, integer, real. Ngoài ra còn có các kiểu cơ sở đặc biệt như: kiểu type_error: chỉ ra một lỗi trong quá trình kiểm tra kiểu; kiểu void, “không có giá trị”, cho phép kiểm tra kiểu đối với lệnh. 135
2. D Æ D ; D D Æ id : T {addtype(id.entry, T.type) } T Æ char {T.type := char } T Æ integer {T.type := integer } T Æ ↑T1 {T.type := pointer(T1.type) } T Æ array[num] of T1 {T.type := array(1 num.val, T1.type) } Hình 6.2- Lược đồ dịch lưu trữ kiểu của một danh biểu 2. Kiểm tra kiểu của biểu thức Lược đồ dịch cho kiểm tra kiểu của biểu thức như sau: E Æ literal {E.type := char } E Æ num {E.type := integer } E Æ id {E.type := lookup(id.entry) } E Æ E1 mod E2 {E.type := if E1.type = integer and E2.type = integer then integer else type_error } E Æ E1[E2] {E.type := if E2.type = integer and E1.type = array(s,t) then t else type_error } E Æ E1↑ { E.type := if E1.type = pointer(t) then t else type_error } Hình 6.3- Lược đồ dịch kiểm tra kiểu của biểu thức Ở đây ta dùng hàm lookup(e) để tìm kiểu được lưu trữ trong ô của bảng ký hiệu mà ô đó được trỏ bởi e. 3. Kiểm tra kiểu của các lệnh Ta có lược đồ dịch cho kiểm tra kiểu của lệnh S Æ id := E { S.type := if id.type = E.type then void else type_error } S Æ if E then S1 {S.type := if E.type = boolean then S1.type else type_error } S Æ while E do S1 {S.type := if E.type = boolean then S1.type else type_error } S Æ S1 ; S2 {S.type := if S1.type = void and S2.type = void then void else type_error } Hình 6.4- Lược đồ dịch kiểm tra kiểu của các lệnh 137
3. Hình 6.6- Ðoạn ngôn ngữ giả kiểm tra sự tương đương cấu trúc của hai biểu thức kiểu s và t 2. Tương đương tên Trong một số ngôn ngữ, kiểu được cho bởi tên. Ví dụ trong Pascal type link = ↑ cell; var next : link; last : link; p : ↑cell; q, r : ↑cell; Danh biểu link được khai báo là tên của kiểu ↑cell. Vấn đề đặt ra là next, last, p, q, r có kiểu giống nhau hay không? Câu trả lời phụ thuộc vào sự cài đặt. Hai biểu thức kiểu là tương đương tên nếu tên của chúng giống nhau. Theo quan niệm tương đương tên thì last và next có cùng kiểu; p, q và r có cùng một kiểu nhưng next và p có kiểu khác nhau. IV. CHUYỂN ÐỔI KIỂU Xét biểu thức x + i trong đó x có kiểu real và i có kiểu integer. Vì biểu diễn các số nguyên, số thực khác nhau trong máy tính do đó các chỉ thị máy khác nhau được dùng cho số thực và số nguyên. Trình biên dịch có thể thực hiện việc chuyển đổi kiểu để hai toán hạng có cùng kiểu khi phép toán cộng xảy ra. Bộ kiểm tra kiểu trong trình biên dịch có thể được dùng để thêm các phép toán biến đổi kiểu vào trong biểu diễn trung gian của chương trình nguồn. Chẳng hạn ký hiệu hậu tố của x + i có thể là: x i inttoreal real+ Trong đó: inttoreal đổi số nguyên i thành số thực, real+ thực hiện phép cộng các số thực. Sự ép buộc chuyển đổi kiểu Sự chuyển đổi từ kiểu này sang kiểu khác được gọi là ẩn (implicit) nếu nó được làm một cách tự động bởi chương trình dịch. Chuyển đổi kiểu ẩn còn gọi là ép buộc chuyển đổi kiểu (coercions). Ví dụ 6.2: Ðịnh nghĩa trực tiếp cú pháp cho kiểm tra kiểu và ép buộc chuyển đổi kiểu biến đổi kiểu từ integer thành real: Luật sinh Luật ngữ nghĩa E Æ num E.type := integer E Æ num.num E.type := real E Æ id E.type := lookup(id.entry) E Æ E1 op E2 E.type := if E1.type = integer and E2.type = integer then integer else if E1.type = integer and E2.type = real 139
4. BÀI TẬP CHƯƠNG VI 6.1. Viết các biểu thức kiểu cho các kiểu dữ liệu sau đây: a) Một mảng của các con trỏ có kích thước từ 1 đến 100, trỏ đến đối tượng các số thực. b) Mảng 2 chiều của các số nguyên, hàng có kích thước từ 0 đến 9, cột có chỉ số từ -10 đến 10. c) Các hàm mà miền định nghĩa là các hàm với các đối số nguyên, trị là con trỏ trỏ đến các số nguyên và miền xác định của nó là các mẫu tin chứa số nguyên và ký tự. 6.2. Giả sử có một khai báo C như sau: typedef struct { int a, b ; } CELL, * PCELL ; CELL foo [ 100 ] ; PCELL bar (x, y) int x ; CELL y { } Viết các biểu thức kiểu cho các kiểu dữ liệu foo và bar. 6.3. Cho văn phạm sau đây định nghĩa chuỗi của các chuỗi ký tự: P → D ; E D → D ; D | id : T T → list of T | char | integer E → ( L ) | literal | num | id L → E , L | E Hãy viết các quy tắc biên dịch để xác định các biểu thức kiểu (E) và list (L). 6.4. Giả sử tên kiểu là link và cell được định nghĩa như ở phần tên cho biểu thức kiểu. Hãy xác định những biểu thức kiểu nào dưới đây là tương đương cấu trúc, những biểu thức kiểu nào tương đương tên. a) link b) pointer (cell) c) pointer (link) d) pointer (record ((info x integer) x ( next x pointer (cell))) 6.5. Giả sử rằng kiểu của mỗi định danh là một miền con của số nguyên. Cho biểu thức với các phép toán +, - , * , div và mod như trong Pascal, hãy viết quy tắc kiểm tra kiểu để gán mỗi biểu thức con vào vùng miền con giá trị mă nó sẽ nằm trong đó. 141