Chương 1: Giới thiệu Trình biên dịch (compiler)

Khoa KTMT Vũ Đức Lung 1 TRÌNH BIÊN DỊCH (COMPILER) Khoa Kỹ thuật máy tính GV: TS. Vũ Đức Lung  Email: lungvd@uit.edu.vn  Thời gian: - Lý Thuyết: 45 tiết (3 TC) Điểm số: - Điểm báo cáo: 50% - Điểm thi cuối kỳ: 50% Khoa KTMT Vũ Đức Lung 2 MỤC ĐÍCH & NỘI DUNG  Môn học Trình biên dịch hay còn gọi là Chương trình dịch sẽ giới thiệu những nguyên tắc và kỹ thuật cơ bản để cài đặt một trình biên dịch.  Những kiến thức này sẽ giúp hiểu được cơ cấu và cách vận hành trong các trình biên dịch của các ngôn ngữ lập trình thông dụng như Pascal, C, C++ và Java, nhờ đó hiểu thấu đáo hơn về các ngôn ngữ này, giúp nâng cao kỹ năng lập trình và gỡ lỗi chương trình. Khoa KTMT Vũ Đức Lung 3 TÀI LIỆU THAM KHẢO 1. Phan Thị Tươi. Giáo trình Trình biên dịch, nhà xuất bản đại học quốc gia tp HCM, 2009. 2. Aho, Sethi, and Ullman [1986]. Compilers: Principles, Techniques, and Tools, Addison-Wesley, Reading Mass., 1986. (Bản dịch tiếng Việt gồm hai tập với tựa đề: Trình biên dịch: Nguyên lý, Kỹ thuật và Công cụ, nhà xuất bản Thống kê, 2000-2001). Khoa KTMT Vũ Đức Lung 4 CHƯƠNG 1: GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH 1. Ngôn ngữ lập trình: 1.1 Giới thiệu:  Con người muốn máy tính thực hiện công việc, phải viết các yêu cầu đưa cho máy bằng ngôn ngữ máy hiểu được.  Việc viết các yêu cầu ta gọi là lập trình  Ngôn ngữ dùng để lập trình được gọi là ngôn ngữ lập trình Khoa KTMT Vũ Đức Lung 5 GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH 1.2 Phân loại:  Ngôn ngữ máy. 10110011010010010011010110110001  Hợp ngữ. • MOV r0, B ; move B into register r0 • ADD r0, C ; add • MOV A, r0 ; store  Ngôn ngữ cấp cao. A := B + C 1.3 Chương trình:  Tập hợp các yêu cầu được sắp đặt hợp lý để máy thực hiện.  Các yêu cầu có thể được diễn tả bằng nhiều ngôn ngữ khác nhau, thế nhưng máy tính chỉ hiểu được một ngôn ngữ duy nhất: ngôn ngữ máy (machine language). Khoa KTMT Vũ Đức Lung 6 GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH 1.4 Phiên dịch (translation):  Quá trình biến đổi một chương trình được viết bằng một ngôn ngữ (ngôn ngữ nguồn) thành một chương trình tương đương nhưng được diễn tả bằng một ngôn ngữ khác (ngôn ngữ đích).  Ngôn ngữ đích thường là ngôn ngữ máy.  Có hai dạng phiên dịch: Biên dịch (compilation) và Thông dịch (interpretation):  Chương trình chịu trách nhiệm dịch từ một ngôn ngữ này sang một ngôn ngữ khác được gọi chung là chương trình dịch (translator) và có thể được chia thành hai loại: Trình biên dịch (compiler) và Trình thông dịch (interpreter). Khoa KTMT Vũ Đức Lung 7 GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH 1.4.1 Biên dịch (compilation):  Chương trình nguồn được ghi trong các tập tin rồi được dịch thành chương trình đích và được ghi lại trong các tập tin.  Sau đó chúng ta có thể cho chương trình chạy bằng cách "mở" tập tin chứa chương trình đích ra.  Công việc này tương tự như công việc của một chuyên gia dịch thuật khi thực hiện dịch một văn bản (tác phẩm văn học, tài liệu kỹ thuật). Khoa KTMT Vũ Đức Lung 8 GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH  Trình biên dịch, còn gọi là phần mềm biên dịch, compiler, là một chương trình máy tính làm công việc dịch một chuỗi các câu lệnh được viết bằng một ngôn ngữ lập trình (gọi là ngôn ngữ nguồn hay mã nguồn), thành một chương trình tương đương nhưng ở dưới dạng một ngôn ngữ máy tính mới (gọi là ngôn ngữ đích) và thường là ngôn ngữ ở cấp thấp hơn, như ngôn ngữ máy.  Chương trình mới được dịch gọi mã đối tượng  Chương trình đích có thể được thi hành trực tiếp bởi một máy tính hay bởi một máy ảo Khoa KTMT Vũ Đức Lung 9 GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH 1.4.2 Thông dịch (interpretation):  Chương trình nguồn được dịch rồi cho thực hiện ngay mà không ghi lại bản dịch.  Công việc này tương tự như công việc của một thông dịch viên. Khoa KTMT Vũ Đức Lung 10 CompilerChương trình nguồn Chương trình đích Chương trình đíchInput Output InterpreterChương trình nguồn Output Input Biên dịch và thông dịch GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH Khoa KTMT Vũ Đức Lung 11 GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH 1.5. Đặc tả ngôn ngữ lập trình Tối thiểu cần định nghĩa: 1. Tập các ký hiệu cần dùng trong các chương trình hợp lệ 2. Tập các chương trình hợp lệ 3. Nghĩa của chương trình hợp lệ Các phương pháp xác định nghĩa của CT hợp lệ: - Phương pháp thứ nhất là định nghĩa bằng phép ánh xạ. Sử dụng phép toán hàm: hàm Lamda. - Phương pháp thứ hai: Máy trừu tượng. - Phương pháp thứ ba: Tập (x,y) là sự biên dịch,x là CT nguồn, y là đích. Khoa KTMT Vũ Đức Lung 12 GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH  Cú pháp và Ngữ nghĩa  Cú pháp: sự kết hợp của các ký hiệu (dạng của biểu thức, các phát biểu, các đơn vị nhỏ trong chương trình)  Ngữ nghĩa: ý nghĩa của các kết hợp Khoa KTMT Vũ Đức Lung 13 TRÌNH BIÊN DỊCH 1. Các thành phần của trình biên dịch: 1.1 Phân tích từ vựng: Nhận dạng token. Token: danh biểu, hằng, từ khóa, các toán tử phép toán, các ký hiệu phân cách, khoảng trắng, các ký hiệu đặc biệt Ví dụ: COST := ( PRICE + TAX )*65 Đầu ra của bộ phân tích từ vựng: () := ( () + () ) * (,4) Viết gọn: id1 := (id2 + id3) * num4 Khoa KTMT Vũ Đức Lung 14 TRÌNH BIÊN DỊCH 1.2 Bảng danh biểu Ví dụ: COST := (PRICE + TAX) * 65 Bảng danh biểu Khoa KTMT Vũ Đức Lung 15 TRÌNH BIÊN DỊCH 1.3 Phát hiện và thông báo lỗi 1.4 Phân tích cú pháp Vídụ: COST := (PRICE + TAX) * 65 Kết quả phân tích từ vựng: id1 := ( id2 + id3 )* num4 Kết quả phân tích cú pháp: Cây cú pháp của phát biểu Khoa KTMT Vũ Đức Lung 16 TRÌNH BIÊN DỊCH 1.5 Phân tích ngữ nghĩa: Cây cú pháp có xử lý ngữ nghĩa Khoa KTMT Vũ Đức Lung 17 TRÌNH BIÊN DỊCH 1.6 Sinh mã trung gian: temp1:= intoreal(65) temp2:= id2+ id3 temp3:= temp2* temp1 id1:= temp3 1.7 Tối ưu mã trung gian: temp1:= id2+ id3 id1:= temp1 * 65 Khoa KTMT Vũ Đức Lung 18 TRÌNH BIÊN DỊCH 1.8 Sinh mã đối tượng: movF id2, R1 movF id3, R2 addF R2, R1 multF# 65.0, R1 movF R1, id1 Khoa KTMT Vũ Đức Lung 19 TRÌNH BIÊN DỊCH Tổng hợp quá trình biên dịch Khoa KTMT Vũ Đức Lung 20 TRÌNH BIÊN DỊCH Khoa KTMT Vũ Đức Lung 21 CÁC MỐI LIÊN QUAN VỚI TRÌNH BIÊN DỊCH 1. Bộ tiền xử lý:  Xử lý macro (macro processing)  Chêm tập tin (file inclusion)  Bộ xử lý hoà hợp (rational processor)  Mở rộng ngôn ngữ (language extension) Khoa KTMT Vũ Đức Lung 22 CÁC MỐI LIÊN QUAN VỚI TRÌNH BIÊN DỊCH 2. Trình biên dịch hợp ngữ: Phát biểu gán b := a + 2 được dịch ra mã hợp ngữ MOV a, R1 ADD #2 , R1 MOV R1, b Khoa KTMT Vũ Đức Lung 23 CÁC MỐI LIÊN QUAN VỚI TRÌNH BIÊN DỊCH 3. Trình biên dịch hợp ngữ hai chuyến: Chuyến thứ nhất: đọc mã hợp ngữ và tạo bảng danh biểu Danh biểu Điạ chỉ tương đối a 0 b 4 Chuyến thứ hai: đọc mã hợp ngữ và dịch sang mã máy khả định vị địa chỉ: MOV a, R1 0001 010000000000* ADD #2, R1 0010 0110 00000010 (1.6) MOV R1, b 0100 010000000100* Khoa KTMT Vũ Đức Lung 24 CÁC MỐI LIÊN QUAN VỚI TRÌNH BIÊN DỊCH 4. Bộ cất liên kết soạn thảo: Loader là chương trình thực hiện hai nhiệm vụ: cất và soạn thảo liên kết. Quá trình cất bao gồm lấy mã máy khả định vị tính lại thành địa chỉ tuyệt đối. Như ở ví dụ phần 3: Giả sử mã máy được cất trong bộ nhớ trong tại địa chỉ L = 00001111; địa chỉ tuyệt đối của a, b là 00001111 và 00010011. Ba chỉ thị (1.6) được viết lại dưới dạng mã máy tuyệt đối: 0001010000001111 0011011000000010 (1.7) 0010010000010011 Link-editor cho phép tạo một chương trình duy nhất từ nhiều tập tin ở dạng mã máy khả định vị của những lần biên dịch riêng biệt và từ các tập tin thư viện do hệ thống cung cấp. Khoa KTMT Vũ Đức Lung 25 CÁC MỐI LIÊN QUAN VỚI TRÌNH BIÊN DỊCH  Hệ thống xử lý ngôn ngữ Khoa KTMT Vũ Đức Lung 26 CÁC MỐI LIÊN QUAN VỚI TRÌNH BIÊN DỊCH 5. Nhóm các giai đoạn của trình biên dịch  Giai đoạn trước và giai đoạn sau(front end and back end)  Các chuyến  Thu giảm số lượng các chuyến Thídụ: goto L : goto L : L : a = b + c