Bài giảng Xây dựng chương trình dịch - Chương 1: Giới thiệu về chương trình dịch

Nội dung text: Bài giảng Xây dựng chương trình dịch - Chương 1: Giới thiệu về chương trình dịch

1. CHƯƠNG 1 Giới thiệu về chương trình dịch Mục tiêu: Giới thiệu các khái niệm cơ bản, các giai đoạn chính khi biên dịch chương trình
2. Chương trình nguồn Trình biên dịch Chương trình đích (Source program) (Compiler) (Target program) Thông báo lỗi (Error messages )
3. Chương trình nguồn khung (Skeletal source program) Bộ tiền xử lí (Preprocessor) Chương trình nguồn (Source program) Trình biên dịch (Compiler) Chương trình hợp ngữ đích (Target assembly program) Trình dịch hợp ngữ (Assembler) Mã máy tái khả định (Relocatable machine code) Thư viện/tập tin Trình tải/liên kết (Loader/link-editor) đối tượng (Library/object files) Mã máy tuyệt đối (Absolute machine code)
4. Chương trình nguồn (Source program) Phân tích từ vựng (Lexical analyzer) Phân tích cú pháp (Syntax analyzer) Phân tích ngữ nghĩa (Semantic analyzer) Quản lí bảng kí tự Quản lí lỗi (Symbol-table manager) (Error handler) Sinh mã trung gian (Intermediate code generator) Tối ưu mã (Code optimizer) Sinh mã (Code generator) Chương trình đích (Target program)
5. • Ví dụ : 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. Định danh (identifier) position 2. Ký hiệu phép gán := 3. Định danh initial 4. Ký hiệu phép cộng + 5. Định danh rate 6. Ký hiệu phép nhân * 7. Số 60
6. • Ví dụ: Giả sử ngôn ngữ định nghĩa câu lệnh gán bởi các luật sinh sau : assig stmt → id := expr expr → expr + expr | expr * expr | (expr) | id | number • Lệnh gán position := initial + rate * 60 được biểu diễn bằng parse tree như sau:
7. • Cấu trúc phân cấp của một chương trình thường được diễn tả bởi quy luật đệ qui Ví dụ: Định nghĩa đệ qui một biểu thức số học như sau 1) Định danh (identifier/id) là một biểu thức (expression/expr) 2) Số (number) là một biểu thức. 3) Nếu expr1 và expr2 là các biểu thức thì: expr1 + expr2 expr1 * expr2 (expr1) cũng là những biểu thức.
8. 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 • Tập hợp thông tin về các kiểu dữ liệu cho giai đoạn sinh mã về sau • Sử dụng cấu trúc phân cấp của giai đoạn phân tích cú pháp để xác định các toán tử, toán hạng của các biểu thức và câu lệnh • 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
9. 4. Sinh mã trung gian (Intermediate Code Generator) • Sau khi phân tích cấu trúc và ngữ nghĩa, một số trình biên dịch sẽ tạo ra một dạng biểu diễn trung gian của chương trình nguồn • Mã trung gian có 2 đặc tính quan trọng: Dễ tạo và dễ dàng chuyển đổi thành chương trình đích • Mã trung gian có cách biểu diễn. Thông thường người ta sử dụng dạng "mã máy 3 địa chỉ" (three-address code), tương tự như dạng hợp ngữ cho một máy mà trong đó mỗi vị trí bộ nhớ có thể đóng vai trò như một thanh ghi.
10. 5. Tối ưu mã (Code Optimizer) • Giai đoạn tối ưu mã cố gắng tối ưu mã trung gian để thu được mã máy thực hiện nhanh hơn Ví dụ: Mã trung gian nêu trên có thể tối ưu thành: temp1 := id3 * 60.0 id1 := id2 + temp1
11. Ví dụ: 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
12. • Bảng ký hiệu (symbol table) là một cấu trúc dữ liệu mà mỗi phần tử là một bản ghi dùng để lưu trữ một định danh, các trường là các thuộc tính của định danh • Trong quá trình phân tích từ vựng, tên các định danh được tìm thấy và nó được đưa vào bảng ký hiệu nhưng thường thì các thuộc tính của nó chưa xác định được trong giai đoạn này • Các thuộc tính khác của các định danh sẽ được bổ sung trong các giai đoạn biên dịch tiếp theo
13. Xử lí lỗi • Mỗi giai đoạn biên dịch có thể gặp nhiều lỗi, ví dụ: ✓ Giai đoạn phân tích từ vự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 gặp 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 • 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: Quá trình biên dịch có thể dừng lại hoặc tiếp tục
14. Phân tích ngữ nghĩa := id1 + id2 * id3 Inttoreal | 60 Sinh mã trung gian temp1 := inttoreal (60) temp2 := id3 * temp1 temp3 := id2 + temp2 id1 := temp3