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

Chia sẻ: Lotus_123 Lotus_123 | Ngày: | Loại File: PDF | Số trang:138

Thêm vào BST

Báo xấu

65
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đầ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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

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Ử N HÂN CNTT TP. HCM, 2010
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 h iệ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 h iệ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 i
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ừ n gày 0 1/09/2009 đến n gà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 - 0 612468 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) ii
 Các giai đoạn thực hiện : 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 iii
iv
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 ..................................................................................... 4 TỔ NG QUAN ............................................................................. 6 CHƯƠNG 1: GIỚI THIỆU VỀ TRÌNH BIÊN DỊCH .................................................... 6 1.1. Trình biên dịch là gì? ................................................................................... 6 1.1.1. Phân loại trình biên dịch .............................................................................. 6 1.1.2. Quá trình biên d ịch....................................................................................... 7 1.1.3. 1.1.4. Quá trình phân tích ................................ ................................ ...................... 8 Quá trình tổng hợp ....................................................................................... 9 1.1.5. Các pha trong quá trình biên d ịch ................................................................ 9 1.1.6. Các module phụ của trình biên dịch............................................................ 11 1.1.7. CÁC GIỚI HẠN CỦA LUẬN VĂN ...................................................... 13 1.2. Các giới hạn chung ................................ ................................ .................... 13 1.2.1. Ngôn ngữ ANSI C giản lược ....................................................................... 13 1.2.2. NỘI DUNG LUẬN VĂN ...................................................................... 17 1.3. GIỚI THIỆU VỀ CHUYẾN TRƯỚ C ..................................... 18 CHƯƠNG 2: VAI TRÒ, CHỨC NĂNG CỦA CHUYẾN TRƯ ỚC. ............................ 18 2.1. BẢNG DANH BIỂU. ............................................................................ 18 2.2. Bảng danh biểu là gì? Vai trò và ch ức năng? ............................................. 18 2.2.1. Tầng dữ liệu ............................................................................................... 20 2.2.2. Tổ chức lưu trữ dạng bảng băm ................................ ................................ .. 21 2.2.3. Tầng quản lý............................................................................................... 23 2.2.4. PHÂN TÍCH TỪ VỰ NG. ...................................................................... 24 2.3. 2.4. PHÂN TÍCH CÚ PHÁP. ................................ ........................................ 26 Phương pháp phân tích cú pháp từ dưới lên (Bottom-Up Parsing).............. 27 2.4.1. Kỹ thuật phân tích cú pháp LR.................................................................... 30 2.4.2. PHÂN TÍCH NGỮ NGHĨA ................................................................ ... 34 2.5. 2.6. PHÁT SINH MÃ TRUNG GIAN. ......................................................... 35 1
CÁC CÔNG CỤ HỖ TRỢ XÂY DỰNG MỘ T PHẦN TRÌNH CHƯƠNG 3: BIÊN DỊCH. 38 GIỚI THIỆU. ......................................................................................... 38 3.1. Bộ phát sinh trình phân tích từ vựng FLEX ............................................ 38 3.2. Cấu trúc. .................................................................................................... 38 3.2.1. Quy trình vận hành. ................................ ................................ .................... 39 3.2.2. Mộ t số hàm hỗ trợ. ..................................................................................... 40 3.2.3. Bộ phát sinh trình phân tích cú pháp BISON.......................................... 41 3.3. Cấu trúc. .................................................................................................... 41 3.3.1. Quy trình vận hành. ................................ ................................ .................... 44 3.3.2. XÂY DỰ NG CHUYẾN TRƯỚC CỦA TRÌNH BIÊN DỊCH 46 CHƯƠNG 4: QUẢN LÝ MÃ TRUNG GIAN ................................ ............................ 46 4.1. XÂY DỰNG BẢNG DANH BIỂU ........................................................ 47 4.2. Cấu trúc cài đặt chung ................................ ................................ ............... 47 4.2.1. Các cấu trúc dữ liệu lưu trữ thông tin danh biểu......................................... 48 4.2.2. Ví dụ biễu diễn một số kiểu dữ liệu ................................ ............................. 55 4.2.3. Các thao tác quản lý bảng danh biểu. ......................................................... 56 4.2.4. Minh họa sơ đồ lưu trữ ................................ ................................ ............... 56 4.2.5. DỊCH CÁC CẤU TRÚC ................................ ........................................ 58 4.3. Biểu thứ c .................................................................................................... 58 4.3.1. Mả ng và con trỏ ......................................................................................... 66 4.3.2. Dịch biểu thức logic - luồng điều khiển....................................................... 72 4.3.3. 4.3.4. Khai báo ..................................................................................................... 95 TỔ NG KẾT ................................ ............................................ 114 CHƯƠNG 5: KẾT QUẢ............................................................................................ 114 5.1. HẠN CHẾ ........................................................................................... 114 5.2. HƯỚNG PHÁT TRIỂN ................................................................ ....... 114 5.3. PH Ụ LỤC................................ ........................................................................... 116 PHỤ LỤC 1: Bảng xác định độ ưu tiên của các toán tử.................................... 116 PHỤ LỤC 2: Dịch chương trình m ẫu............................................................... 117 THAM KHẢO ................................................................................................... 132 2
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)................................................... 46 Hình 4.2. Mô hình cài đặt bảng danh biểu ............................................................. 47 Hình 4.3. Các cấu trúc lưu trữ thông tin danh biểu................................................ 49 Hình 4.4. Sơ đồ lưu trữ của bucket ................................ ........................................ 50 Hình 4.5. Structdef trong tổ chưc lưu trữ struct ................................ ..................... 51 Hình 4.6. Declarator trong khai báo con trỏ integer.............................................. 52 Hình 4.7. Symlink trong chuỗi thông tin danh biểu ................................................ 54 Hình 4.8. Symbol trong tổ ch ức lưu trữ khai báo biến............................................ 55 Hình 4.9. Biễu diễn một sô kiểu d ữ liệu ................................................................. 55 Hình 4.10. Sơ đồ lưu trữ b iến, struct và typedef ................................ ..................... 57 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ố.......... 59 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 ......... 65 3
Hình 4.13. Cây cú pháp và lan truyền thuộ c tính cho ví dụ 4.13 ............................ 71 Hình 4.14. Phân bố mã cho các câu lệnh if................................ ............................ 74 Hình 4.15. Cây phân tích cú pháp sử dụng cho luật sinh 3 và 3’............................ 77 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 .................... 82 Hình 4.17. Cây phân tích cú pháp cho cấ u trúc lệnh switch ................................ ... 89 Hình 4.18. Mô tả cấu trúc một case_val ................................................................ 90 Hình 4.19. Mô tả cấu trúc một switch table ................................ ........................... 90 Hình 4.20. Switch table khi đã lưu trữ đầ y đủ thông tin để th ực hiện hành vi ACT06 ...................................................................................................................... 93 Hình 4.21. Phân bố mã cho các câu lệnh while ................................ ..................... 94 Hình 4.22. Phân bố mã cho các câu lệnh do-while ................................................ 95 Hình 4.23. Cấu trúc khai báo của mộ t chương trình .............................................. 96 Hình 4.24. Cây phân tích cú pháp của mộ t chương trình đơn giản ........................ 96 Hình 4.25. Sự tương quan giửa khai báo và external_definition ............................ 97 Hình 4.26. Sự lan truyền thuộc tính “int” và “x” ................................................ 100 Hình 4.27. Sơ đồ tổ chức lưu trữ khai báo int x; ............................................ 101 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: . 104 Hình 4.29. Sơ đồ tổ chức lưu trữ hàm inc trong Ví dụ 4 .20: ................................ . 105 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 ................................ ........................................................................... 108 Hình 4.31. Sơ đồ tổ chức lưu trữ cho kiểu dữ liệu struct ...................................... 109 Hình 4.32. Cây phân tích cú pháp cho khai báo con trỏ................................ ....... 110 Hình 4.33 S ơ đồ lưu trữ cho khai báo int *x; ................................................. 111 Hình 4.34. Cây phân tích cú pháp cho khai báo typedef ...................................... 112 Hình 4.36. Tổ chức lưu trữ typedef ................................ ...................................... 113 4
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 ........... 58 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 .................. 63 Bảng 4.3. Luậ t sinh và luậ t ngữ nghĩa trường h ợp mảng, con trỏ .......................... 70 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 ...... 83 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 ...................................................................................................................... 91 Bảng 4.6. Hệ th ống luật sinh nhận kiểu ................................................................. 98 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 ................... 99 Bảng 4.8. Hệ th ống luật phân tích tên hàm và tham số ........................................ 102 Bảng 4.9. Hệ th ống luật nhận các khai báo trong hàm ........................................ 103 Bảng 4.10. Hệ thống lu ật phân tích khai báo struct ................................ ............. 106 Bảng 4.11. Hệ thống lu ật dành cho khai báo con trỏ ........................................... 109 5
Chương 1 – Tổng quan 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. Chương trình nguồn (mã nguồn) Trình biên dịch Báo lỗi Chương trình đích (mã nguồn) Hình 1.1. Trình biên d ịch Trong đa số các trường hợp, ngôn ngữ n guồ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. 6
Chương 1 – Tổng quan 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 b iê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 b iê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ụ b iê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ừ n gô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 b ao gồm 2 bước:  Phân tích.  Tổng hợp. 7
Chương 1 – Tổng quan Chương trình nguồn (mã nguồn) Trình biên d ịch Phân tích Một tập hợp các thông tin mà trình biên dịch thu thập được từ chương trình nguồn Biểu diễn trung gian Tổng hợp Chương trình đ ích (mã nguồn) Hình 1.2. Quá trình biên dịch 1.1.4. Quá trình phân tích Quá trình này nhằm thu thậ p và tích lũy các thông tin từ chương trình nguồn, tạo ra mộ t dạng biễu diễn trung gian tương đương. Từ đó, trình biên dịch sẽ sử dụng biểu diễn trung gian này để phục vụ cho quá trình tổng hợp. Quá trình phân tích bao gồm 3 bước:  Phân tích từ vựng (Lexical analysis). Thự c hiện phân loại chuỗi văn bản trong mã nguồn thành các nhóm, loại từ vựng có ngh ĩa, gọi là token để cung cấp cho bước sau.  Phân tích cú pháp (Syntax analysis). Từ các token nhận được, th ực hiện kiểm tra xem mã nguồn có được viết theo đúng cú pháp củ a ngôn ngữ hay không.  Phân tích ngữ nghĩa (Semantic analysis). Kiểm tra ngữ ngh ĩa và thực thi các hành vi ngữ n gh ĩa tương ứng. 8
Chương 1 – Tổng quan  Phát sinh mã trung gian . Tạo ra mã trung gian – mộ t d ạng biểu diễn củ a chương trình nguồn. Mã trung gian th ường độc lập với các đặc trưng k ỹ thuật của máy đích. 1.1.5. Quá trình tổng hợp Là quá trình xây dựng nên chương trình đ ích từ các thông tin trong biểu biểu diễn trung gian đã thu thập được. Quá trình tổng hợp thực hiện các bước sau để phát sinh mã đ ích:  Tối ưu mã trung gian. Tố i ưu mã trung gian để tạo ra d ạng biểu diễn tốt hơn. Giúp mã đ ích khi được phát sinh có thể th ực thi nhanh hơn ho ặc tiết kiệm không gian hay năng lượng.  Phát sinh mã đích. Tạo ra mã đích từ biễu diễn trung gian đã tối ưu.  Tối ưu mã đích. Thực hiện tố i ưu để tạo ra mộ t tập mã đích có th ể thự c thi nhanh hơn. Hai quá trình tối ưu là tùy chọn. 1.1.6. Các pha trong quá trình biên dịch Từ các bước trong quá trình phân tích và tổng h ợp, quá trình biên dịch sẽ được chia thành từng pha tương ứng, mỗi pha b iên dịch sẽ chuyển dần mã nguồn củ a chương trình sang mã đ ích. Theo đó, mỗ i mộ t pha sẽ nhận một dạng thông tin có cấu trúc được quy đ ịnh sẵn từ pha trước, tiến hành xử lý và tạo ra một dạng thông tin mới để phục vụ cho pha sau liền kề. Tùy thuộ c vào lo ại ngôn ngữ của mã nguồn và lo ại mã đích muốn phát sinh, các pha sẽ được phân nhóm để việc tổ chức, xây dựng được thu ận tiện hơn. Thông thường sự phân nhóm này sẽ tương ứng với mô hình phân tích - tổng hợp . Trong đó, phân tích đ ược gọ i là chuyến trước (Front-End), tổng h ợp sẽ là chuyến sau (Back-End) (Hình 1.3). 9
Chương 1 – Tổng quan Chương trình (mã ngu ồn) Phân tích từ vựng Token Phân tích cú pháp Quản lý b ảng Qu ản lý Cây phân tích cú pháp lỗ i danh biểu Phân tích ngữ nghĩa Cây phân tích cú pháp Bộ p hát sinh mã trung gian Front-End Mã trung gian Bộ tối ưu mã trung gian Mã trung gian đã tố i ưu Bộ phát sinh mã đích Mã đích Bộ tố i ưu mã đích Back-End Mã đích đã tố i ưu Hình 1.3. Các pha biên d ịch mã nguồn Chuyến trư ớc phụ thuộc rất nhiều vào lo ại ngôn ngữ nguồn , trong khi chuyến sau ch ỉ phụ thuộc chủ yếu vào bộ m ã trung gian mà chuyến trước cung cấp, và các đ ặc điểm phần cứng mà mã đích thực thi trên đó. Khi chuyến sau đ ã được xây dựng tốt trên một bộ m ã trung gian chuẩn, thì việc xây dựng nên một 10
Chương 1 – Tổng quan trình biên dịch ngôn ngữ mới để d ịch mã cho cùng m ột loại ph ần cứng ch ỉ là việc xây dự ng lại chuyến trước cho phù h ợp với ngôn ngữ m ới. Qu ản lý bảng danh biểu và quản lý lỗi là hai pha luôn được thự c hiện xuyên suốt trong quá trình biên dịch.  Bảng danh biểu. Những thông tin về một danh biểu (tên, kiểu, phạm vi,…) sẽ được trình biên dịch thu thập và lưu trữ vào bảng danh biểu. Chuyến sau sẽ sử dụng những dữ liệu n ày để phát sinh mã.  Kiểm và thông báo lỗ i. Mỗi bước xử lý trong sơ đồ trên đều có th ể xu ất hiện lỗi về khai báo, cú pháp, ngữ nghĩa,... Trình biên d ịch cần kiểm tra được các lỗi và thông báo lỗ i cho người sử dụng. 1.1.7. Các module phụ của trình biên dịch Chương trình nguồn (mã nguồn) Tiền xử lý Trình biên dịch Bộ dịch mã h ợp ngữ Thư viện Linker/Loader Mã thực thi tuyệt đối trên chip Hình 1.4. Quá trình d ịch mã cho chip 1 .1.7.1. Tiền xử lý - Preprocessor Trong thực tế, mã nguồn của một chương trình thường được tách ra thành nhiều tập tin để thuận tiện cho việc quản lý. Do đó đ ể b iên dịch được chương trình, ta cần thu th ập đư ợc tất cả các thông tin từ các tập tin mã nguồn 11
Chương 1 – Tổng quan riêng lẻ, công việc đó sẽ đ ược thự c hiện ở quá trình tiền xử lý, đồng thời dịch các macro, các chỉ thị thành các câu lệnh tương ứng trong chương trình. Tiền xử lý thực hiện dịch các khai báo hỗ trợ lập trình được viết trong chương trình, chuyển các khai báo đó thành mã nguồn mà trình biên dịch có th ể xử lý được. Tiền xử lý thự c hiện dịch các loại macro sau: o Các m acro m à người lập trình khai báo. o Macro chèn tập tin. Ví dụ: #include o Built-in macro: là các macro được xây dựng sẵn đ ể hỗ trợ lập trình. Ví dụ như macro khai báo chèn mộ t đo ạn lệnh hợp ngữ : __asm __endasm; 1 .1.7.2. Bộ dịch mã hợp ngữ - Assembler Đa số trình biên d ịch chỉ d ịch ra mã hợp ngữ, do phụ thuộc vào đặc tính của thiết b ị ph ần cứng nên mã hợp ngữ chưa thể th ực thi được, ví dụ như m ã h ợp ngữ cần th ực thi trên một loại vi xử lý PIC[6] có bộ nhớ RAM, ROM ở m ức hạn chế. Lúc đó ta cần chuyển đổi từ m ã hợp ngữ sang mã thực thi (opcode) cụ thể đ ể phù hợp với vi xử lý PIC thì mới có thể th ực thi được. 1 .1.7.3. Trình liên k ết/Tả i – Linker/Loader Do cấu trúc chương trình đôi khi có sử dụng đến các hàm thư viện đ ã được biên d ịch sẵn (nhằm tránh biên dịch nhiều lần), đồng thời không gian bộ nhớ dùng để thực thi lệnh trên chip (thường gọ i là ROM) có tính chất đặc thù riêng, nên ta cần mộ t chương trình được gọ i là linker đ ể thực hiện liên kết các đoạn mã lại với nhau thành 1 khối thống nhất trước khi nạp xuống bộ nhớ ROM. 12
Chương 1 – Tổng quan 1 .2. CÁC GIỚI HẠN CỦA LUẬN VĂN 1.2.1. Các giới hạn chung Nh ằm mụ c đích tìm hiểu và học hỏ i, việc xây dựng trình biên dịch trong khuôn khổ luận văn này sẽ bao gồm các giới hạn sau:  Xây dựng cho ngôn ngữ ANSI C giản lược.  Chỉ thực hiện xây d ựng chuyến trư ớc. Mã phát sinh được tính đến thời điểm hiện tại là mã trung gian. 1.2.2. Ngôn ngữ ANSI C giản lược 1 .2.2.1. Cấu trúc chương trình  Khai báo biến (cục bộ , toàn cục).  Khai báo hàm  Gọi hàm, truyền biến, gọ i hàm đa cấp. LEVEL1 LEVEL2 LEVEL3 main() void func1() { { statments Statments func1(); ... statments ... } func2(); statments } void func2() { void func3() Statments { ... Statments func3(); ... ... ... } } Hình 1.5. Cấu trúc chương trình 1 .2.2.2. Hằ ng số  Hằng số số họ c: 13
Chương 1 – Tổng quan o Th ập phân: -3, 10,… o Th ập lục phân (hexadecimal): 0x30, … o Nhị phân: 0b00011101  Ký tự hằng: ‘A’, ‘b’…  Chuỗi hằng: “ABCD” 1 .2.2.3. Biến và các kiểu biến Tên kiểu Kích thước Giá trị tối thiểu Giá trị tối đa 1 b yte 0 255 unsigned char 1 b yte -128 +127 char unsigned int 2 b ytes 0 65535 (unsigned short) 2 b ytes -32768 +32767 int (short) 4 b ytes 0 4294967295 unsigned long 4 b ytes -2147483648 +2147483647 long Bảng 1.1. Các kiểu dữ liệu  Phạm vi biến: o Biến toàn cục: ph ạm vi hoạt động từ sau khai báo biến. o Cục bộ: Chỉ có hiệu lực cục bộ trong hàm, hoặc trong block chứa nó.  Phạm vi khai báo: ở đầu hàm, ho ặc khai báo toàn cụ c.  Có thể dùng toán tử & để truy xu ất đ ịa ch ỉ củ a biến.  Hỗ trợ b iến tĩnh static và extern 1 .2.2.4. Con trỏ  Hỗ trợ con trỏ một cấp của tất cả cá kiểu dữ liệu.  Hỗ trợ các thao tác số học trên con trõ.  Kích thước con trỏ: 2 bytes.  Không hỗ trợ con trỏ hàm. 14