Luận Văn Khảo sát và xây dựng thử nghiệm chuyến trước của trình biên dịch dành cho ngôn ngữ ANSI C giản lược

Khóa luận tốt nghiệp
Đề tài: Khảo sát và xây dựng thử nghiệm chuyến trước của trình biên dịch dành cho ngôn ngữ ANSI C giản lược





MỤC LỤC 1
DANH MỤC CÁC HÌNH VẼ . 3
DANH MỤC CÁC BẢNG . 5
CHƯƠNG 1: TỔNG QUAN . 6
1.1. GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH 6
1.1.1. Trình biên dịch là gì? . 6
1.1.2. Phân loại trình biên dịch 6
1.1.3. Quá trình biên dịch . 7
1.1.4. Quá trình phân tích 8
1.1.5. Quá trình tổng hợp . 9
1.1.6. Các pha trong quá trình biên dịch 9
1.1.7. Các module phụ của trình biên dịch 11
1.2. CÁC GIỚI HẠN CỦA LUẬN VĂN 13
1.2.1. Các giới hạn chung 13
1.2.2. Ngôn ngữ ANSI C giản lược . 13
1.3. NỘI DUNG LUẬN VĂN 17
CHƯƠNG 2: GIỚI THIỆU VỀ CHUYẾN TRƯỚC . 18
2.1. VAI TRÒ, CHỨC NĂNG CỦA CHUYẾN TRƯỚC. 18
2.2. BẢNG DANH BIỂU. 18
2.2.1. Bảng danh biểu là gì? Vai trò và chức năng? . 18
2.2.2. Tầng dữ liệu . 20
2.2.3. Tổ chức lưu trữ dạng bảng băm 21
2.2.4. Tầng quản lý . 23
2.3. PHÂN TÍCH TỪ VỰNG. 24
2.4. PHÂN TÍCH CÚ PHÁP. 26
2.4.1. Phương pháp phân tích cú pháp từ dưới lên (Bottom-Up Parsing) 27
2.4.2. Kỹ thuật phân tích cú pháp LR 30
2.5. PHÂN TÍCH NGỮ NGHĨA . 34
2.6. PHÁT SINH MÃ TRUNG GIAN 35
2
CHƯƠNG 3: CÁC CÔNG CỤ HỖ TRỢ XÂY DỰNG MỘT PHẦN TRÌNH
BIÊN DỊCH. 38
3.1. GIỚI THIỆU 38
3.2. Bộ phát sinh trình phân tích từ vựng FLEX 38
3.2.1. Cấu trúc. 38
3.2.2. Quy trình vận hành. 39
3.2.3. Một số hàm hỗ trợ 40
3.3. Bộ phát sinh trình phân tích cú pháp BISON 41
3.3.1. Cấu trúc. 41
3.3.2. Quy trình vận hành. 44
CHƯƠNG 4: XÂY DỰNG CHUYẾN TRƯỚC CỦA TRÌNH BIÊN DỊCH 46
4.1. MÔ HÌNH CHUYẾN TRƯỚC CỦA TRÌNH BIÊN DỊCH 46
4.2. QUẢN LÝ MÃ TRUNG GIAN [9] . 47
4.3. XÂY DỰNG BẢNG DANH BIỂU [1, 2, 3, 8, 9] . 48
4.3.1. Cấu trúc cài đặt chung . 48
4.3.2. Các cấu trúc dữ liệu lưu trữ thông tin danh biểu . 49
4.3.3. Ví dụ biễu diễn một số kiểu dữ liệu . 56
4.3.4. Các thao tác quản lý bảng danh biểu 57
4.3.5. Minh họa sơ đồ lưu trữ . 57
4.4. DỊCH CÁC CẤU TRÚC 59
4.4.1. Biểu thức 59
4.4.2. Mảng và con trỏ . 67
4.4.3. Dịch biểu thức logic - luồng điều khiển. 73
4.4.4. Khai báo . 96
CHƯƠNG 5: TỔNG KẾT 115
5.1. KẾT QUẢ 115
5.2. HẠN CHẾ . 115
5.3. HƯỚNG PHÁT TRIỂN . 115
PHỤ LỤC . 117
PHỤ LỤC 1: Bảng xác định độ ưu tiên của các toán tử 117
PHỤ LỤC 2: Dịch chương trình mẫu. 118
THAM KHẢO . 133



Chương 1 – Tổng quan
6
CHƯƠNG 1: TỔNG QUAN
1.1. GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH
1.1.1. Trình biên dịch là gì?
Trình biên dịch (TBD) là một chương trình xử lý ngôn ngữ, làm công việc
dịch chương trình hay một chuỗi các câu lệnh được viết bằng ngôn ngữ lập trình
(gọi là ngôn ngữ nguồn hay mã nguồn) thành chương trình tương đương dưới
dạng ngôn ngữ đích. Một phần quan trọng trong quá trình dịch là ghi nhận và
thông báo lỗi.
Trong đa số các trường hợp, ngôn ngữ nguồn là ngôn ngữ cấp cao như
Fortran, C/C++, Java, Và ngôn ngữ đích là mã hợp ngữ hoặc mã máy của
một hoặc một họ hệ thống phần cứng.
1.1.2. Phân loại trình biên dịch
Theo số bước biên dịch, ta chia làm hai loại chính: một bước và nhiều
bước.
1.1.2.1. Trình biên dịch một bước
Việc biên dịch mã nguồn viết bằng ngôn ngữ cấp cao sang ngôn ngữ
máy (hay mã máy) gọi là trình biên dịch 1 bước. Các trình biên dịch trước
đây cho Pascal hay Borland C là trình biên dịch một bước.
Trình biên dịch
Chương trình nguồn
(mã nguồn)
Chương trình đích
(mã nguồn)
Báo lỗi
Hình 1.1. Trình biên dịch
Chương 1 – Tổng quan
7
1.1.2.2. Trình biên dịch nhiều bước.
Các trình biên dịch cần nhiều hơn một bước để hoàn tất gọi là trình
biên dịch nhiều bước.
Các kiểu trình biên dịch nhiều bước bao gồm:
 Trình biên dịch nguồn sang nguồn: dịch từ một ngôn ngữ cấp cao
này sang một ngôn ngữ cấp cao khác. Chẳng hạn biên dịch một
chương trình viết bằng ngôn ngữ C++ sang một chương trình viết
bằng ngôn ngữ C.
 Trình biên dịch phân đoạn: biên dịch sang một loại mã thực thi gần
với máy, thông thường là mã hợp ngữ. Ví dụ biên dịch một chương
trình viết bằng ngôn ngữ C sang một chương trình viết bằng mã hợp
ngữ cho một con chip bất kỳ (x86, VN-08, SG-08), từ mã hợp ngữ
này, ta lại cần một trình biên dịch hợp ngữ để dịch mã hợp ngữ sang
mã máy thực thi trên chip.
Trên thực tế, có trình biên dịch thực hiện biên dịch ngược, dịch từ
ngôn ngữ cấp thấp sang lại ngôn ngữ cấp cao và trình biên dịch như thế được
gọi là trình biên dịch ngược.
1.1.3. Quá trình biên dịch
Quá trình biên dịch mã nguồn được thực hiện theo mô hình biên dịch
phân tích - tổng hợp bao gồm 2 bước:
 Phân tích.
 Tổng hợp.



THAM KHẢO
[1] Alfred. V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers:
Principles, Techniques and Tools, 2
nd
ed., Addison Wesley, 2007.
[2] Alfred. V. Aho, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles,
Techniques and Tools, 1st ed., Addison Wesley, 1986.
[3] Allen I.Hollub, Compiler Design In C, Addison Wesley, 1990.
[4] John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to
Automata Theory, Languages, and Computation, 2nd ed., Addison Wesley,
2001.
[5] John R. Levine, Flex & Bison, 1st ed., O‟Reilly Media, Inc., 2009.
[6] Niklaus Wirth, Compiler Construction, Addision Wesley, 1996.
[7] Charles Donnelly, Richard Stallman, Bison – The Yacc-compatible Parser
Generator, Free Software Foundation, 2009.
[8] Muchnick, Steven, Advanced Compiler Design and Implementation, Morgan
Kaufmann Publishers, 1997
[9] http://sdcc.sourceforge.net/