Giáo trình Xây dựng chương trình dịch - Chương I: Giới thiệu về sự biên dịch

Nội dung text: Giáo trình Xây dựng chương trình dịch - Chương I: Giới thiệu về sự biên dịch

1. CHƯƠNG I GIỚI THIỆU VỀ SỰ BIÊN DỊCH Nội dung chính: Để máy tính có thể hiểu và thực thi một chương trình được viết bằng ngôn ngữ cấp cao, ta cần phải có một trình biên dịch thực hiện việc chuyển đổi chương trình đó sang chương trình ở dạng ngôn ngữ đích. Chương này trình bày một cách tổng quan về cấu trúc của một trình biên dịch và mối liên hệ giữa nó với các thành phần khác - “họ hàng” của nó - như bộ tiền xử lý, bộ tải và soạn thảo liên kết,v.v. Cấu trúc của trình biên dịch được mô tả trong chương là một cấu trúc mức quan niệm bao gồm các giai đoạn: Phân tích từ vựng, Phân tích cú pháp, Phân tích ngữ nghĩa, Sinh mã trung gian, Tối ưu mã và Sinh mã đích. Mục tiêu cần đạt: Sau khi học xong chương này, sinh viên phải nắm được một cách tổng quan về nhiệm vụ của các thành phần của một trình biên dịch, mối liên hệ giữa các thành phần đó và môi trường nơi trình biên dịch thực hiện công việc của nó. Tài liệu tham khảo: [1] Trình Biên Dịch - Phan Thị Tươi (Trường Ðại học kỹ thuật Tp.HCM) - NXB Giáo dục, 1998. [2] Compilers : Principles, Technique and Tools - Alfred V.Aho, Jeffrey D.Ullman - Addison - Wesley Publishing Company, 1986. [3] Compiler Design – Reinhard Wilhelm, Dieter Maurer - Addison - Wesley Publishing Company, 1996. I. TRÌNH BIÊN DỊCH Nói một cách đơn giản, trình biên dịch là một chương trình làm nhiệm vụ đọc một chương trình được viết bằng một ngôn ngữ - ngôn ngữ nguồn (source language) - rồi dịch nó thành một chương trình tương đương ở một ngôn ngữ khác - ngôn ngữ đích (target languague). Một phần quan trọng trong quá trình dịch là ghi nhận lại các lỗi có trong chương trình nguồn để thông báo lại cho người viết chương trình. Chương trình Trình biên Chương trình nguồn dịch đích Hình 1.1 - Một trình biên dịch 1. Mô hình phân tích - tổng hợp của một trình biên dịch Chương trình dịch thường bao gồm hai quá trình : phân tích và tổng hợp - Phân tích → đặc tả trung gian - Tổng hợp → chương trình đích 1
2. Chương trình nguồn khung Bộ tiền xử lý Chương trình nguồn Trình biên dịch Chương trình đích hợp ngữ Trình dịch hợp ngữ Mã máy khả tái định vị Trình tải / Liên kết Thư viện, Tập tin đối tượng khả tái định vị Mã máy tuyệt đối Hình 1.3 - Một trình xử lý ngôn ngữ điển hình II. SỰ PHÂN TÍCH CHƯƠNG TRÌNH NGUỒN Phần này giới thiệu về các quá trình phân tích và cách dùng nó thông qua một số ngôn ngữ định dạng văn bản. 1. Phân tích từ vựng (Lexical Analysis) Trong một trình biên dịch, giai đọan phân tích từ vựng sẽ đọc chương trình nguồn từ trái sang phải (quét nguyên liệu - scanning) để tách ra thành các thẻ từ (token). Ví dụ 1.2: Quá trình phân tích từ vựng cho câu lệnh gán position := initial + rate * 60 sẽ tách thành các token như sau: 1. Danh biểu position 2. Ký hiệu phép gán := 3. Danh biểu initial 3
3. cũng là những biểu thức. Câu lệnh (statement) cũng có thể định nghĩa đệ qui : 1) Nếu id1 là một danh biểu và expr2 là một biểu thức thì id1 := expr2 là một lệnh (stmt). 2) Nếu expr1 là một biểu thức và stmt2 là một lệnh thì while (expr1) do stmt2 if (expr1) then stmt2 đều là các lệnh. Người ta dùng các qui tắc đệ qui như trên để đặc tả luật sinh (production) cho ngôn ngữ. Sự phân chia giữa quá trình phân tích từ vựng và phân tích cú pháp cũng tuỳ theo công việc thực hiện. 3. Phân tích ngữ nghĩa (Semantic Analysis) Giai đoạn phân tích ngữ nghĩa sẽ thực hiện việc kiểm tra xem chương trình nguồn có chứa lỗi về ngữ nghĩa hay không và tập hợp thông tin về kiểu cho giai đoạn sinh mã về sau. Một phần quan trọng trong giai đoạn phân tích ngữ nghĩa là kiểm tra kiểu (type checking) và ép chuyển đổi kiểu. Ví dụ 1.5: Trong biểu thức position := initial + rate * 60 Các danh biểu (tên biến) được khai báo là real, 60 là số integer vì vậy trình biên dịch đổi số nguyên 60 thành số thực 60.0 := position + * initial 60 rate thành := position + * initial inttoreal rate 60.0 Hình 1.5 - Chuyển đổi kiểu trên cây phân tích cú pháp 5
4. Ví dụ 1.6: Chẳng hạn, một khai báo trong Pascal có dạng var position, initial, rate : real thì thuộc tính kiểu real chưa thể xác định khi các danh biểu được xác định và đưa vào bảng ký hiệu. Các giai đoạn sau đó như phân tích ngữ nghĩa và sinh mã trung gian mới đưa thêm các thông tin này vào và sử dụng chúng. Nói chung giai đoạn sinh mã thường đưa các thông tin chi tiết về vị trí lưu trữ dành cho định danh và sẽ sử dụng chúng khi cần thiết. Bảng ký hiệu 1 position 2 initial rate 3 4 2. Xử lý lỗi Mỗi giai đoạn có thể gặp nhiều lỗi, tuy nhiên sau khi phát hiện ra lỗi, tùy thuộc vào trình biên dịch mà có các cách xử lý lỗi khác nhau, chẳng hạn : - Dừng và thông báo lỗi khi gặp lỗi đầu tiên (Pascal). - Ghi nhận lỗi và tiếp tục quá trình dịch (C). Giai đoạn phân tích từ vựng thường gặp lỗi khi các ký tự không thể ghép thành một token. Giai đoạn phân tích cú pháp gặp lỗi khi các token không thể kết hợp với nhau theo đúng cấu trúc ngôn ngữ. Giai đoạn phân tích ngữ nghĩa báo lỗi khi các toán hạng có kiểu không đúng yêu cầu của phép toán hay các kết cấu không có nghĩa đối với thao tác thực hiện mặc dù chúng hoàn toàn đúng về mặt cú pháp. 3. Các giai đoạn phân tích Giai đoạn phân tích từ vựng: Ðọc từng ký tự gộp lại thành token, token có thể là một danh biểu, từ khóa, một ký hiệu, Chuỗi ký tự tạo thành một token gọi là lexeme - trị từ vựng của token đó. Ví dụ 1.7: Danh biểu rate có token id, trị từ vựng là rate và danh biểu này sẽ được đưa vào bảng ký hiệu nếu nó chưa có trong đó. Giai đoạn phân tích cú pháp và phân tích ngữ nghĩa: Xây dựng cấu trúc phân cấp cho chuỗi các token, biểu diễn bởi cây cú pháp và kiểm tra ngôn ngữ theo cú pháp. Ví dụ 1.8: Cây cú pháp và cấu trúc lưu trữ cho biểu thức position := initial + rate * 60 7
5. Có một khác biệt rất lớn giữa khối lượng tối ưu hoá mã được các trình biên dịch khác nhau thực hiện. Trong những trình biên dịch gọi là "trình biên dịch chuyên tối ưu", một phần thời gian đáng kể được dành cho giai đoạn này. Tuy nhiên, cũng có những phương pháp tối ưu giúp giảm đáng kể thời gian chạy của chương trình nguồn mà không làm chậm đi thời gian dịch quá nhiều. 6. Sinh mã Giai đoạn cuối cùng của biên dịch là sinh mã đích, thường là mã máy hoặc mã hợp ngữ. Các vị trí vùng nhớ được chọn lựa cho mỗi biến được chương trình sử dụng. Sau đó, các chỉ thị trung gian được dịch lần lượt thành chuỗi các chỉ thị mã máy. Vấn đề quyết định là việc gán các biến cho các thanh ghi. Ví dụ 1.11: Sử dụng các thanh ghi (chẳng hạn R1, R2) cho việc sinh mã đích như sau: MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 Toán hạng thứ nhất và thứ hai của mỗi chỉ thị tương ứng mô tả đối tượng nguồn và đích. Chữ F trong mỗi chỉ thị cho biết chỉ thị đang xử lý các số chấm động (floating_point). Dấu # để xác định số 60.0 xem như một hằng số. 7. Ví dụ Xem hình vẽ 1.8 (trang 10) mô tả các giai đoạn biên dịch cho biểu thức: position := initial + rate * 60. IV. NHÓM CÁC GIAI ÐOẠN Các giai đoạn mà chúng ta đề cập ở trên là thực hiện theo trình tự logic của một trình biên dịch. Nhưng trong thực tế, cài đặt các hoạt động của nhiều hơn một giai đoạn có thể được nhóm lại với nhau. Thông thường chúng được nhóm thành hai nhóm cơ bản, gọi là: kỳ đầu (Front end) và kỳ sau (Back end). 1. Kỳ đầu (Front End) Kỳ đầu bao gồm các giai đoạn hoặc các phần giai đoạn phụ thuộc nhiều vào ngôn ngữ nguồn và hầu như độc lập với máy đích. Thông thường, nó chứa các giai đoạn sau: Phân tích từ vựng, Phân tích cú pháp, Phân tích ngữ nghĩa và Sinh mã trung gian. Một phần của công việc tối ưu hóa mã cũng được thực hiện ở kỳ đầu. Front end cũng bao gồm cả việc xử lý lỗi xuất hiện trong từng giai đoạn. 2. Kỳ sau (Back End) Kỳ sau bao gồm một số phần nào đó của trình biên dịch phụ thuộc vào máy đích và nói chung các phần này không phụ thuộc vào ngôn ngữ nguồn mà là ngôn ngữ trung gian. Trong kỳ sau, chúng ta gặp một số vấn đề tối ưu hoá mã, phát sinh mã đích cùng với việc xử lý lỗi và các thao tác trên bảng ký hiệu. 9