Khóa luậ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

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN KHOA HỌC MÁY TÍNH NGUYỄN VIỆT CƢỜNG – NGUYỄN THÀNH TRUNG 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 CỬ NHÂN CNTT TP. HCM, 2010 TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN KHOA HỌC MÁY TÍNH NGUYỄN VIỆT CƢỜNG – 0612051 NGUYỄN THÀNH TRUNG – 0612468 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 CỬ NHÂN CNTT GIÁO VIÊN HƢỚNG DẪN TS. NGUYỄN THANH PHƢƠNG KHÓA 2006 – 2010 i NHẬN XÉT CỦA GIÁO VIÊN HƢỚNG DẪN ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… TpHCM, ngày ….. tháng …… năm …… Giáo viên hướng dẫn ii NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… ……………………………………………………………………………… Khóa luận đáp ứng yêu cầu của Khóa luận cử nhân CNTT. TpHCM, ngày ….. tháng …… năm …… Giáo viên phản biện iii LỜI CÁM ƠN Đầu tiên, chúng em xin cảm ơn khoa Công nghệ Thông tin, trường Đại học Khoa học Tự nhiên Thành phố Hồ Chí Minh đã tạo điều kiện cho chúng em thực hiện đề tài này. Chúng em xin chân thành cám ơn các thầy cô khoa Công nghệ Thông tin đã truyền đạt những kiến thức hữu ích tạo nền tảng vững chắc cho chúng em định hướng trong học tập và phát huy khả năng của mình khi bước vào đời. Đặc biệt, chúng em xin gởi lời cảm ơn chân thành và lời chúc sức khỏe đến thầy Nguyễn Thanh Phương đã hướng dẫn và dạy bảo tận tình để nhóm em hoàn thành tốt luận văn tốt nghiệp của mình. Chúng em xin cảm ơn anh Đặng Đăng Khoa và anh Phan Lê Sang đã giúp đỡ tận tụy và luôn sát cánh bên chúng em như những người anh trong gia đình trong suốt quá trình thực hiện khóa luận. Chúng em cũng xin cảm ơn sự động viên tích cực của các anh chị nhân viên phòng SELab trường Khoa hoc Tự nhiên và bạn bè trong quá trình chúng em thực hiện đề tài. Và cuối cùng chúng con xin cảm ơn các đấng sinh thành đã nuôi dạy, dìu dắt và luôn là nguồn khích lệ để chúng con phấn đấu trong học tập. Mặc dù cố gắng và nổ lực hết mình, chúng em vẫn còn mắc nhiều thiếu sót trong luận văn của mình, chúng em hy vọng sẽ nhận được sự ủng hộ và đóng góp ý kiến để hoàn thiện đề tài này một cách tốt hơn. TP. Hồ Chí Minh, tháng 06, 2010. Nhóm sinh viên thực hiện Nguyễn Việt Cường – Nguyễn Thành Trung iv KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN: KHOA HỌC MÁY TÍNH ĐỀ CƢƠNG CHI TIẾT Tên đề 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. Giáo viên hƣớng dẫn: TS. Nguyễn Thanh Phƣơng Thời gian thực hiện: Từ ngày 01/09/2009 đến ngày 10/07/2010 Sinh viên thực hiện: 1. Nguyễn Việt Cường - 0612051 2. Nguyễn Thành Trung - 0612468 Loại đề tài: Tìm hiểu công nghệ và xây dựng ứng dụng. Nội Dung Đề Tài: Nội dung: – Tìm hiểu kỹ thuật xây dựng trình biên dịch. – Khảo sát các công cụ hỗ trợ phát sinh một phần trình biên dịch. – Vận dụng vào việc xây dựng chuyến trước cho ngôn ngữ ANSI C giản lược. – Giải quyết các bài toán nảy sinh trong thực tế, vốn không xuất hiện trong lý thuyết nền tảng. Yêu cầu: – Nắm vững và vận dụng có sáng tạo các kiến thức tiếp thu được từ lý thuyết cũng như thực tế. – Xây dựng thành công chuyến trước của trình biên dịch (có thể vận hành). Kết quả: Phát sinh ra mã trung gian, hướng đến họ chip VN-08 Kế Hoạch Thực Hiện: (mô tả chi tiết thời gian của các giai đoạn thực hiện và phân công công việc của từng thành viên trong nhóm)  Các giai đoạn thực hiện : v o Bắt đầu : 01/09/2009 o Hoàn thành giai đoạn tìm tài liệu và project liên quan : 28/09/2009 o Hoàn thành đọc tài liệu và thiết kế mô hình C-Compiler : 28/12/2009 o Hoàn thành giai đoạn Coding và Testing : 15/05/2010 o Hoàn thành báo cáo cuối cùng : 10/07/2010  Phân công công việc : o Xây dựng cấu trúc, quản lý bảng danh biểu : Nguyễn Thành Trung. o Tìm hiểu các công cụ phát sinh trình biên dịch : Nguyễn Việt Cường. o Phát sinh mã cho các cấu trúc khai báo, định nghĩa kiểu dữ liệu : Nguyễn Thành Trung. o Phát sinh mã cho các cấu trúc điều khiển, biểu thức : Nguyễn Việt Cường. Xác nhận của GVHD Ngày……tháng……năm…… SV Thực hiện 1 MỤC 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 3 DANH MỤC CÁC HÌNH VẼ Hình 1.1. Trình biên dịch ......................................................................................... 6 Hình 1.2. Quá trình biên dịch .................................................................................. 8 Hình 1.3. Các pha biên dịch mã nguồn .................................................................. 10 Hình 1.4. Quá trình dịch mã cho chip .................................................................... 11 Hình 1.5. Cấu trúc chương trình ............................................................................ 13 Hình 2.1. Sự phân chia tầng trong cài đặt bảng danh biểu .................................... 19 Hình 2.2. Cấu trúc lưu trữ (dạng đơn giản) cho danh biểu .................................... 20 Hình 2.3. Bảng băm với kích thước khóa 256 ........................................................ 21 Hình 2.4. Bảng danh biểu với liên kết chỉ định phạm vi ......................................... 23 Hình 2.5 .Giao thức liên hệ của bộ phân tích từ vựng. ........................................... 25 Hình 2.6. Vị trí của trình phân tích cú pháp trong chuyến trước của trình biên dịch ...................................................................................................................... 27 Hình 2.7. Cấu trúc của một bộ phân tích cú pháp LR ............................................ 31 Hình 2.8. Automat của văn phạm dành cho biểu thức đơn giản[1] ......................... 32 Hình 3.1. Quá trình phân tích từ vựng ................................................................... 39 Hình 3.2. Quá trình phân tích cú pháp của BISON ................................................ 44 Hình 4.1. Cấu trúc của một toán hạng (operand)................................................... 47 Hình 4.2. Mô hình cài đặt bảng danh biểu ............................................................. 48 Hình 4.3. Các cấu trúc lưu trữ thông tin danh biểu ................................................ 50 Hình 4.4. Sơ đồ lưu trữ của bucket ........................................................................ 51 Hình 4.5. Structdef trong tổ chưc lưu trữ struct ..................................................... 52 Hình 4.6. Declarator trong khai báo con trỏ integer .............................................. 53 Hình 4.7. Symlink trong chuỗi thông tin danh biểu ................................................ 55 Hình 4.8. Symbol trong tổ chức lưu trữ khai báo biến............................................ 56 Hình 4.9. Biễu diễn một sô kiểu dữ liệu ................................................................. 56 Hình 4.10. Sơ đồ lưu trữ biến, struct và typedef ..................................................... 58 Hình 4.11. Quá trình lan truyền thuộc tính danh biểu và thuộc tính hằng số.......... 60 4 Hình 4.12. Cây cú pháp và lan truyền thuộc tính cho biểu thức ++a + b * c ......... 66 Hình 4.13. Cây cú pháp và lan truyền thuộc tính cho ví dụ 4.13 ............................ 72 Hình 4.14. Phân bố mã cho các câu lệnh if ............................................................ 75 Hình 4.15. Cây phân tích cú pháp sử dụng cho luật sinh 3 và 3’............................ 78 Hình 4.16. Cây phân tích cú pháp của cấu trúc điều khiển ví dụ 4.16 .................... 83 Hình 4.17. Cây phân tích cú pháp cho cấu trúc lệnh switch ................................... 90 Hình 4.18. Mô tả cấu trúc một case_val ................................................................ 91 Hình 4.19. Mô tả cấu trúc một switch table ........................................................... 91 Hình 4.20. Switch table khi đã lưu trữ đầy đủ thông tin để thực hiện hành vi ACT06 ...................................................................................................................... 94 Hình 4.21. Phân bố mã cho các câu lệnh while ..................................................... 95 Hình 4.22. Phân bố mã cho các câu lệnh do-while ................................................ 96 Hình 4.23. Cấu trúc khai báo của một chương trình .............................................. 97 Hình 4.24. Cây phân tích cú pháp của một chương trình đơn giản ........................ 97 Hình 4.25. Sự tương quan giửa khai báo và external_definition ............................ 98 Hình 4.26. Sự lan truyền thuộc tính “int” và “x” ................................................ 101 Hình 4.27. Sơ đồ tổ chức lưu trữ khai báo int x; ............................................ 102 Hình 4.28. Cây phân tích cú pháp và lan truyền thuộc tính cho ví dụ ví dụ 4.20: . 105 Hình 4.29. Sơ đồ tổ chức lưu trữ hàm inc trong Ví dụ 4.20: ................................. 106 Hình 4.30. Cây phân tích cú pháp và quá trình lan truyền thuộc tính cho khai báo struct ........................................................................................................... 109 Hình 4.31. Sơ đồ tổ chức lưu trữ cho kiểu dữ liệu struct ...................................... 110 Hình 4.32. Cây phân tích cú pháp cho khai báo con trỏ....................................... 111 Hình 4.33 Sơ đồ lưu trữ cho khai báo int *x; ................................................. 112 Hình 4.34. Cây phân tích cú pháp cho khai báo typedef ...................................... 113 Hình 4.36. Tổ chức lưu trữ typedef ...................................................................... 114 5 DANH MỤC CÁC BẢNG Bảng 1.1. Các kiểu dữ liệu ..................................................................................... 14 Bảng 1.2. Các toán tử 2 ngôi ................................................................................. 15 Bảng 2.1. Mô tả một số token của ngôn ngữ C ....................................................... 24 Bảng 2.2. Mô tả từng bước hoạt động của phương pháp phân tích cú pháp dưới lên ...................................................................................................................... 29 Bảng 2.3. Bảng phân tích cú pháp của văn phạm dành cho biểu thức đơn giản ..... 33 Bảng 2.4. Các bước thực hiện của bộ phân tích cú pháp LR với câu nhập 2 * 3 .... 34 Bảng 4.1. Cách hình thành một toán hạng từ danh biểu hoặc một constant ........... 59 Bảng 4.2. Luật sinh và luật ngữ nghĩa trường hợp tính toán biểu thức .................. 64 Bảng 4.3. Luật sinh và luật ngữ nghĩa trường hợp mảng, con trỏ .......................... 71 Bảng 4.4. Mô tả các hành vi ngữ nghĩa và phát sinh mã ba địa chỉ của lệnh if ...... 84 Bảng 4.5. Mô tả các hành vi ngữ nghĩa và phát sinh mã ba địa chỉ của lệnh switch ...................................................................................................................... 92 Bảng 4.6. Hệ thống luật sinh nhận kiểu ................................................................. 99 Bảng 4.7. Hệ thống luật nhận tên biến và số lượng phần tử của mảng ................. 100 Bảng 4.8. Hệ thống luật phân tích tên hàm và tham số ........................................ 103 Bảng 4.9. Hệ thống luật nhận các khai báo trong hàm ........................................ 104 Bảng 4.10. Hệ thống luật phân tích khai báo struct ............................................. 107 Bảng 4.11. Hệ thống luật dành cho khai báo con trỏ ........................................... 110 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.