Tài liệu Nghiên cứu trình biên dịch cho cpu risc 32 bit

Đại Học Quốc Gia Tp. Hồ Chí Minh TRƯỜNG ĐẠI HỌC BÁCH KHOA -------------------- TRẦN HỒ NAM NGHIÊN CỨU TRÌNH BIÊN DỊCH CHO CPU RISC 32 BIT Chuyên ngành : Kỹ Thuật Điện Tử LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 7 năm 2009 CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH Cán bộ hướng dẫn khoa học : ThS. Tống Văn On (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Cán bộ chấm nhận xét 1 : TS. Lưu Thanh Trà (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Cán bộ chấm nhận xét 2 : ThS. Hồ Trung Mỹ (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Luận văn thạc sĩ được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày 16 tháng 7 năm 2009 ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA ---------------- CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM Độc Lập - Tự Do - Hạnh Phúc ---oOo--Tp. HCM, ngày . ... . tháng . .. . . năm . 2009. . . NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ và tên học viên: . .TRẦN HỒ NAM. . . . . . . . . . . . . . . . . . . . . . Giới tính : Nam ;/ Nữ Ngày, tháng, năm sinh : . .30/8/1982 . . . . . . . . . . Nơi sinh : . . Bình Dương. . . . . . . . Chuyên ngành : . . Kỹ thuật điện tử. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Khoá (Năm trúng tuyển) : . 2006. . . . . . . . 1- TÊN ĐỀ TÀI: . . .THIẾT KẾ TRÌNH DỊCH HỢP NGỮ CHO CPU RISC 32 BIT . . . . . . . . . . . . . . ............................................... .................................. 2- NHIỆM VỤ LUẬN VĂN: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .......................................................................... . . . – Nghiên cứu các bước thực hiện một trình biên dịch nói chung và trình dịch hợp ngữ nói riêng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . – Tìm hiểu tập lệnh của một CPU RISC 32 bit tiêu biểu (ARM7). . . . . . . . . . . . . . . . . . . . . . . – Xây dựng trình dịch hợp ngữ cho CPU ARM7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .......................................................................... .......................................................................... .......................................................................... .......................................................................... .......................................................................... .......................................................................... .......................................................................... ........... 3- NGÀY GIAO NHIỆM VỤ : . . . . . . . . . . . . . . . . . . . . . 4- NGÀY HOÀN THÀNH NHIỆM VỤ : . . . . . . . . . . . . . . . . 5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN (Ghi đầy đủ học hàm, học vị ): . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .ThS TỐNG VĂN ON . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thông qua. CÁN BỘ HƯỚNG DẪN (Họ tên và chữ ký) CHỦ NHIỆM BỘ MÔN QUẢN LÝ CHUYÊN NGÀNH (Họ tên và chữ ký) LỜI CẢM ƠN Em xin gửi lời cảm ơn chân thành đến tất cả các thầy cô trường Đại học Bách Khoa TP.HCM đã trực tiếp giảng dạy và truyền đạt phương pháp học tập, kiến thức quý báu và cả tâm huyết, niềm say mê nghiên cứu khoa học để em có đủ trình độ, bản lĩnh và niềm tin trên con đường chinh phục những đỉnh cao khoa học. Em xin chân thành cảm ơn thầy Tống Văn On, người dành thời gian quý báu để định hướng và tận tình hướng dẫn em thực hiện luận văn này. Xin cảm ơn bạn bè và người thân đã giúp đỡ và động viên tinh thần trong những lúc khó khăn. Cuối cùng, con cảm ơn gia đình và bố mẹ luôn là chỗ dựa vững chắc và tin yêu để con thực hiện những ước mơ khoa học của mình. TRẦN HỒ NAM Tóm tắt luận văn Tóm tắt luận văn Nội dung luận văn bao gồm các kiến thức cần thiết về trình biên dịch, trình dịch hợp ngữ và cách thức để xây dựng một chương trình dịch hợp ngữ (assembler) cho máy tính có tập chỉ thị thu gọn (Reduced Instruction Set Computer – RISC) đồng thời nghiên cứu tập lệnh của một CPU RISC tiêu biểu ARM7. Luận văn đề cập sâu đến các vấn đề cần thiết khi một người nào đó muốn xây dựng một trình dịch hợp ngữ cho một CPU có sẵn bao gồm: cách thức hoạt động của trình dịch hợp ngữ, vấn đề các tham chiếu chưa xác định (unresolved references) – bảng ký hiệu (symbol table), vấn đề xử lý các chỉ dẫn (directive), vấn đề xử lý các macro,… Để minh họa cho kiến thức lý thuyết được đề cập, luận văn đã xây dựng một trình dịch hợp ngữ cho CPU ARM7. Một trình dịch hợp ngữ bao giờ cũng đi kèm với một trình liên kết (linker) và trình nạp (loader). Các kiến thức về trình liên kết và trình nạp sẽ được đề cập trong mối liên quan với trình dịch hợp ngữ. Cách thức xây dựng trình liên kết và trình nạp không nằm trong khuôn khổ của luận văn này. Luận văn “Nghiên cứu trình biên dịch cho CPU RISC 32 bit” bao gồm 5 chương và phần phụ lục, với các nội dung chính như sau: Chương 1: Giới thiệu về trình biên dịch đồng thời mô tả chi tiết các thành phần của một trình biên dịch bao gồm việc phân tích từ vựng, bảng ký hiệu, phân tích cú pháp, phân tích ngữ nghĩa, sinh mã trung gian, tối ưu mã trung gian và sinh mã đối tượng. Chương 2: Chương này trình bày chi tiết về trình dịch hợp ngữ và các khái niệm liên quan đến trình dịch hợp ngữ. Bên cạnh đó, phương pháp xây dựng một trình dịch hợp ngữ hoàn chỉnh cũng được đề cập chi tiết. Chương 3: Trình bày tổng quan về CPU RISC và họ vi xử lý ARM. Các tập lệnh của ARM (bao gồm tập lệnh ARM và tập lệnh Thumb) cũng được mô tả chi tiết. Chương 4: Các bước để xây dựng trình dịch hợp ngữ cho CPU ARM được mô tả chi tiết trong chương này bao gồm việc thiết kế giao diện, thiết kế phần lõi và kết quả kiểm tra chương trình. i Tóm tắt luận văn Chương 5: Chương này đánh giá về kết quả của luận văn, các kết quả đạt được cũng như những hạn chế còn tồn tại. Qua đó đề ra các hướng phát triển trong tương lai. Phụ lục: Trình bày chi tiết các dữ liệu dùng để thiết kế chương trình như: bảng mã lệnh, bảng các định nghĩa của chương trình, bảng các biến toàn cục của chương trình và bảng các hàm của chương trình. Ngoài ra phần phụ lục còn trình bày toàn bộ mã của chương trình. ii Các chữ viết tắt Các chữ viết tắt A ALU Arithmetic Logic Unit ARM Advanced RISC Machine CISC Complex Instruction Set Computer CPU Central processing Unit D Defined/Macro definition mode E Macro expansion mode ILC Instruction Location Counter LIFO Last In First Out C D E I L iii Các chữ viết tắt M MES Macro Expansion Stack MDT Macro Definition Table N Normal mode RISC Reduced Instruction Set Computer SBZ Should be zero SBO Should be one U Undefined N R S U iv Mục lục Mục lục Tóm tắt luận văn........................................................................................................................................i Các chữ viết tắt ....................................................................................................................................... iii Mục lục .....................................................................................................................................................v Mục lục hình vẽ ...................................................................................................................................... vii Mục lục bảng ........................................................................................................................................... ix Chương 1. Trình biên dịch .......................................................................................................................1 1.1. Giới thiệu .......................................................................................................................................1 1.2. Tổng quan về trình biên dịch .........................................................................................................1 1.3. Các phần của trình biên dịch.........................................................................................................2 1.3.1. Phân tích từ vựng (lexical analysis)........................................................................................2 1.3.2. Bảng ký hiệu (bảng danh biểu) ...............................................................................................6 1.3.3. Phát hiện và thông báo lỗi ......................................................................................................7 1.3.4. Phân tích cú pháp (Syntactic analysis parsing) ......................................................................7 1.3.5. Phân tích ngữ nghĩa................................................................................................................9 1.3.6. Sinh mã trung gian ............................................................................................................... 10 1.3.7. Tối ưu mã trung gian............................................................................................................ 10 1.3.8. Sinh mã đối tượng ............................................................................................................... 11 1.4. Trình dịch hợp ngữ ..................................................................................................................... 13 Chương 2. Trình dịch hợp ngữ ............................................................................................................. 14 2.1. Khái niệm trình dịch hợp ngữ ..................................................................................................... 14 2.2. Tập tin đối tượng ........................................................................................................................ 16 2.3. Cách hoạt động của trình dịch hợp ngữ..................................................................................... 16 2.4. Quá trình hợp dịch...................................................................................................................... 19 2.4.1. Trình dịch hợp ngữ hai bước ............................................................................................... 19 2.4.2. Trình dịch hợp ngữ một bước.............................................................................................. 20 2.5. Phân tích trình dịch hợp ngữ hai bước ...................................................................................... 20 2.5.1. Bước 1 ................................................................................................................................. 20 2.5.2. Bước 2 ................................................................................................................................. 26 2.6. Phân tích trình dịch hợp ngữ một bước ..................................................................................... 27 2.7. Bảng ký hiệu ............................................................................................................................... 31 2.7.1. Mảng tuyến tính (linear array).............................................................................................. 31 2.7.2. Mảng được sắp xếp (sorted array) ...................................................................................... 31 2.7.3. Khối các danh sách liên kết (buckets with linked list) .......................................................... 31 2.7.4. Cây tìm kiếm nhị phân (binary search tree) ......................................................................... 32 2.7.5. Bảng băm (hash table)......................................................................................................... 32 2.8. Các chỉ dẫn................................................................................................................................. 33 2.9. Macro .......................................................................................................................................... 35 2.9.1. Khái niệm macro .................................................................................................................. 36 2.9.2. Các tham số của macro ....................................................................................................... 38 2.9.3. Hoạt động của bước không ................................................................................................. 39 2.9.4. Macro khai triển lồng nhau................................................................................................... 43 2.9.5. Các chỉ dẫn dịch có điều kiện .............................................................................................. 45 Chương 3. Tổng quan CPU RISC 32 bit ARM7.................................................................................... 47 3.1. Khái niệm RISC .......................................................................................................................... 47 3.2. Họ vi xử lý ARM.......................................................................................................................... 48 3.3. Kiến trúc của ARM7.................................................................................................................... 49 v Mục lục 3.4. Tập lệnh CPU RISC ARM7......................................................................................................... 50 3.4.1. Tập lệnh ARM ...................................................................................................................... 51 3.4.2. Tập lệnh Thumb ................................................................................................................... 71 3.5. Các chỉ dẫn................................................................................................................................. 81 3.5.1. Các chỉ dẫn biên dịch........................................................................................................... 81 3.5.2. Các chỉ dẫn điều khiển......................................................................................................... 83 3.5.3. Các chỉ dẫn macro ............................................................................................................... 85 Chương 4. Xây dựng trình dịch hợp ngữ.............................................................................................. 87 4.1. Giới thiệu chương trình .............................................................................................................. 87 4.2. Xây dựng chương trình .............................................................................................................. 87 4.2.1. Thiết kế giao diện................................................................................................................. 87 4.2.2. Thiết kế phần lõi................................................................................................................... 93 4.3. Kiểm tra chương trình............................................................................................................... 103 4.3.1. Kiểm tra kết quả dịch tập lệnh ARM .................................................................................. 104 4.3.2. Kiểm tra kết quả dịch tập lệnh Thumb ............................................................................... 116 4.3.3. Kiểm tra kết quả dịch các chỉ dẫn, định nghĩa và khai triển macro ................................... 122 4.3.4. Kiểm tra kết quả dịch với đoạn mã lệnh đơn giản trong thực tế........................................ 130 Chương 5. Kết luận và hướng phát triển đề tài .................................................................................. 136 5.1. Kết luận..................................................................................................................................... 136 5.2. Hướng phát triển ...................................................................................................................... 137 Phụ lục. Các dữ liệu dùng để thiết kế chương trình ........................................................................... 139 1. 2. 3. 4. 5. Bảng mã lệnh ......................................................................................................................... 139 Bảng các định nghĩa của chương trình.................................................................................. 146 Bảng các biến toàn cục của chương trình ............................................................................. 148 Bảng các hàm của chương trình............................................................................................ 150 Mã chương trình..................................................................................................................... 152 Tài liệu tham khảo ............................................................................................................................... 315 vi Mục lục hình vẽ Mục lục hình vẽ Hình 1-1 Vị trí của trình biên dịch ...........................................................................................................1 Hình 1-2 Cây cú pháp của phát biểu ........................................................................................................8 Hình 1-3 Cây cú pháp có xử lý ngữ nghĩa..............................................................................................10 Hình 1-4 Biên dịch phát biểu .................................................................................................................12 Hình 2-1 Các thành phần chính của trình dịch hợp ngữ.........................................................................18 Hình 2-2 Lưu đồ thực hiện bước 1 .........................................................................................................25 Hình 2-3 Lưu đồ thực hiện bước 2 .........................................................................................................26 Hình 2-4 Lưu đồ thực hiện của trình dịch hợp ngữ một bước (phần 1) .................................................29 Hình 2-5 Lưu đồ thực hiện của trình dịch hợp ngữ một bước (phần 2) .................................................30 Hình 2-6 Lưu đồ của trình dịch hợp ngữ hai bước khi có chỉ dẫn (bước 1)...........................................34 Hình 2-7 Lưu đồ của trình dịch hợp ngữ hai bước khi có chỉ dẫn (bước 2)...........................................35 Hình 2-8 Lưu đồ thực hiện bước không (chương trình chính)...............................................................40 Hình 2-9 Lưu đồ thực hiện bước không (hàm Input và hàm Output) ....................................................41 Hình 2-10 Lưu đồ thực hiện bước không (chế độ định nghĩa và chế độ khai triển) ..............................42 Hình 2-11 Lưu đồ chế dộ khai triển được bổ sung chức năng khai triển macro lồng nhau ...................45 Hình 3-1 Kiến trúc ARM7 .....................................................................................................................49 Hình 3-2 Khuôn dạng lệnh B, BL tập lệnh ARM ..................................................................................52 Hình 3-3 Khuôn dạng lệnh BX tập lệnh ARM.......................................................................................53 Hình 3-4 Khuôn dạng các lệnh xử lý dữ liệu tập lệnh ARM .................................................................55 Hình 3-5 Khuôn dạng giá trị tức thời lệnh xử lý dữ liệu (ARM) ...........................................................56 Hình 3-6 Khuôn dạng thanh ghi lệnh xử lý dữ liệu (ARM) ...................................................................56 Hình 3-7 Khuôn dạng dịch trái logic bởi giá trị lệnh xử lý dữ liệu (ARM) ...........................................57 Hình 3-8 Khuôn dạng dịch trái logic bởi thanh ghi lệnh xử lý dữ liệu (ARM)......................................57 Hình 3-9 Khuôn dạng dịch phải logic bởi giá trị lệnh xử lý dữ liệu (ARM)..........................................57 Hình 3-10 Khuôn dạng dịch phải logic bởi thanh ghi logic lệnh xử lý dữ liệu (ARM) .........................57 Hình 3-11 Khuôn dạng dịch phải số học bởi giá trị lệnh xử lý dữ liệu (ARM) .....................................57 Hình 3-12 Khuôn dạng dịch phải số học bởi thanh ghi logic lệnh xử lý dữ liệu (ARM).......................58 Hình 3-13 Khuôn dạng quay phải bởi giá trị lệnh xử lý dữ liệu (ARM)...............................................58 Hình 3-14 Khuôn dạng quay phải bởi thanh ghi lệnh xử lý dữ liệu (ARM) ..........................................58 Hình 3-15 Khuôn dạng quay phải mở rộng lệnh xử lý dữ liệu (ARM)..................................................58 Hình 3-16 Khuôn dạng lệnh MUL tập lệnh ARM .................................................................................58 Hình 3-17 Khuôn dạng lệnh MLA tập lệnh ARM .................................................................................59 Hình 3-18 Khuôn dạng lệnh SMULL tập lệnh ARM.............................................................................60 Hình 3-19 Khuôn dạng lệnh UMULL tập lệnh ARM ............................................................................60 Hình 3-20 Khuôn dạng lệnh SMLAL tập lệnh ARM.............................................................................60 Hình 3-21 Khuôn dạng lệnh UMLAL tập lệnh ARM ............................................................................61 Hình 3-22 Khuôn dạng lệnh CLZ tập lệnh ARM...................................................................................61 Hình 3-23 Khuôn dạng lệnh MRS tập lệnh ARM..................................................................................61 Hình 3-24 Khuôn dạng lệnh MSR(1) tập lệnh ARM .............................................................................62 Hình 3-25 Khuôn dạng lệnh MSR(2) tập lệnh ARM .............................................................................63 Hình 3-26 Khuôn dạng lệnh LDR, STR(1) tập lệnh ARM ....................................................................64 Hình 3-27 Khuôn dạng độ dịch tức thời lệnh LDR/STR(1) (ARM) .....................................................64 Hình 3-28 Khuôn dạng độ dịch thanh ghi lệnh LDR/STR(1) (ARM) ..................................................65 Hình 3-29 Khuôn dạng độ dịch tỉ lệ thanh ghi lệnh LDR/STR(1) (ARM) ...........................................65 Hình 3-30 Khuôn dạng độ dịch tức thời chỉ số sau lệnh LDR/STR(1) (ARM) ...................................65 Hình 3-31 Khuôn dạng độ dịch thanh ghi chỉ số sau lệnh LDR/STR(1) (ARM)..................................65 Hình 3-32 Khuôn dạng độ dịch tỉ lệ thanh ghi chỉ số sau lệnh LDR/STR(1) (ARM)...........................66 Hình 3-33 Khuôn dạng lệnh LDR, STR(2) tập lệnh ARM ....................................................................66 vii Mục lục hình vẽ Hình 3-34 Khuôn dạng độ dịch tức thời lệnh LDR/STR(2) (ARM) .....................................................67 Hình 3-35 Khuôn dạng độ dịch thanh ghi lệnh LDR/STR(2) (ARM) ..................................................67 Hình 3-36 Khuôn dạng độ dịch tức thời chỉ số sau lệnh LDR/STR(2) (ARM) ....................................67 Hình 3-37 Khuôn dạng độ dịch thanh ghi chỉ số sau lệnh LDR/STR(2) (ARM)..................................68 Hình 3-38 Khuôn dạng lệnh LDM, STM tập lệnh ARM .......................................................................68 Hình 3-39 Khuôn dạng lệnh SWP tập lệnh ARM ..................................................................................69 Hình 3-40 Khuôn dạng lệnh SWPB tập lệnh ARM ...............................................................................70 Hình 3-41 Khuôn dạng lệnh SWI tập lệnh ARM...................................................................................70 Hình 3-42 Khuôn dạng lệnh BKPT tập lệnh ARM ................................................................................70 Hình 3-43 Khuôn dạng lệnh B(1) tập lệnh Thumb ................................................................................71 Hình 3-44 Khuôn dạng lệnh B(2) tập lệnh Thumb ................................................................................72 Hình 3-45 Khuôn dạng lệnh BX tập lệnh Thumb ..................................................................................72 Hình 3-46 Khuôn dạng lệnh ADD/SUB thanh ghi tập lệnh Thumb ......................................................73 Hình 3-47 Khuôn dạng lệnh ADD/SUB hằng số tập lệnh Thumb .........................................................73 Hình 3-48 Khuôn dạng các lệnh thao tác với hằng số tập lệnh Thumb .................................................74 Hình 3-49 Khuôn dạng lệnh dịch trái, phải tập lệnh Thumb..................................................................74 Hình 3-50 Khuôn dạng các lệnh thao tác giữa hai thanh ghi thấp tập lệnh Thumb ...............................75 Hình 3-51 Khuôn dạng lệnh ADD/CMP/MOV tập lệnh Thumb ...........................................................76 Hình 3-52 Khuôn dạng lệnh ADD với thanh ghi SP/PC tập lệnh Thumb..............................................77 Hình 3-53 Khuôn dạng lệnh ADD/SUB với thanh ghi SP tập lệnh Thumb...........................................77 Hình 3-54 Khuôn dạng lệnh LDR/STR với offset hằng số tập lệnh Thumb..........................................78 Hình 3-55 Khuôn dạng lệnh LDRH/STRH tập lệnh Thumb.................................................................78 Hình 3-56 Khuôn dạng lệnh LDR/STR với offset thanh ghi tập lệnh Thumb .......................................79 Hình 3-57 Khuôn dạng lệnh LDR dùng thanh ghi PC tập lệnh Thumb .................................................79 Hình 3-58 Khuôn dạng lệnh LDR/STR dùng thanh ghi SP tập lệnh Thumb .........................................80 Hình 3-59 Khuôn dạng lệnh LDMIA/STMIA tập lệnh Thumb .............................................................80 Hình 3-60 Khuôn dạng lệnh POP/PUSH tập lệnh Thumb .....................................................................81 Hình 4-1 Cửa sổ giới thiệu .....................................................................................................................88 Hình 4-2 Cửa sổ chính ...........................................................................................................................89 Hình 4-3 Cửa sổ soạn thảo .....................................................................................................................92 Hình 4-4 Cửa sổ so sánh ........................................................................................................................92 Hình 4-5 Cửa sổ thông tin ......................................................................................................................93 Hình 4-6 Lưu đồ thực hiện bước không .................................................................................................94 Hình 4-7 Lưu đồ thực hiện bước một...................................................................................................101 Hình 4-8 Lưu đồ thực hiện bước hai ....................................................................................................102 Hình 4-9 Nội dung tập tin đối tượng tương đối tập lệnh ARM (Keil uVision3)..................................108 Hình 4-10 Nội dung tập tin đối tượng tuyệt đối tập lệnh ARM (trình dịch hợp ngữ)..........................112 Hình 4-11 Nội dung tập tin đối tượng tương đối tập lệnh Thumb (Keil uVision3) .............................118 Hình 4-12 Nội dung tập tin đối tượng tuyệt đối tập lệnh Thumb (trình dịch hợp ngữ) .......................120 Hình 4-13 Nội dung tập tin đối tượng tương đối khi dịch có chỉ dẫn, macro (Keil uVison3) .............124 Hình 4-14 Nội dung tập tin đối tượng tuyệt đối khi dịch có chỉ dẫn, macro (trình dịch hợp ngữ) ......127 Hình 4-15 Nội dung tập tin đối tượng tương đối sắp xếp mảng (Keil uVision3).................................131 Hình 4-16 Nội dung tập tin đối tượng tuyệt đối sắp xếp mảng (trình dịch hợp ngữ)..........................133 viii Mục lục hình vẽ Mục lục bảng Bảng 1-1 Bảng ký hiệu ....................................................................................................6 Bảng 2-1 Bộ đếm vị trí nhớ của phát biểu.....................................................................21 Bảng 2-2 Bảng ký hiệu cho chương trình ở Bảng 2-1...................................................22 Bảng 2-3 Trích đoạn bảng opcode cho trình dịch hợp ngữ của 80386 .........................23 Bảng 3-1 Trường điều kiện và mã lệnh.........................................................................51 Bảng 3-2 Mã lệnh xử lý dữ liệu (ARM)........................................................................54 Bảng 3-3 Cú pháp các lệnh xử lý dữ liệu tập lệnh ARM ..............................................55 Bảng 3-4 Cú pháp địa chỉ và khuôn dạng lệnh..............................................................69 Bảng 3-5 Mã lệnh thao tác giữa hai thanh ghi thấp (Thumb) .......................................75 Bảng 3-6 Gía trị bit B và L tương ứng với tên lệnh của lệnh LDR/STR (Thumb) .......78 Bảng 3-7 Gía trị op tương ứng với tên lệnh của lệnh LDR/STR (Thumb) ...................79 Bảng 4-1 Chức năng của các cửa sổ..............................................................................87 Bảng 4-2 Chức năng cửa sổ chính.................................................................................89 Bảng 4-3 Các hàm quan trọng của bước không ............................................................94 Bảng 4-4 Các chỉ dẫn được chương trình hỗ trợ ...........................................................95 Bảng 4-5 Thành phần cơ bản của tập lệnh ARM và tập lệnh Thumb ...........................97 Bảng 4-6 Bảng mã lệnh cho 2 lệnh BX và ADD ..........................................................99 Bảng 4-7 Các hàm quan trọng của bước 1 ..................................................................100 Bảng 4-8 Các hàm quan trọng của bước 2 ..................................................................102 ix Chương 1. Trình biên dịch Chương 1.Trình biên dịch 1.1.Giới thiệu Ngày nay, cùng với sự phát triển ngày càng cao của khoa học kỹ thuật, nhu cầu của con người về các thiết bị điện tử ngày càng cao và đa dạng. Từ các thiết bị gia dụng như tủ lạnh, tivi, máy giặt, … đến các thiết bị tinh vi, phức tạp như điện thoại di động, máy vi tính, xe hơi, … Để thoả mãn các nhu cầu này của con người, các thiết bị điện tử ngày nay thường trang bị bộ vi xử lý hoặc vi điều khiển bên trong nó. Đa số các bộ vi xử lý, vi điều khiển phức tạp đều có chứa CPU RISC bên trong. Đi kèm với bộ vi xử lý, vi điều khiển này là chương trình dùng để điều khiển hoạt động của thiết bị. Các chương trình này thường được viết bằng ngôn ngữ cấp cao sau đó được dịch xuống ngôn ngữ máy của bộ vi xử lý hoặc vi điều khiển tương ứng. Từ đó ta thấy sự cần thiết của trình biên dịch, không những trong lĩnh vực tin học mà còn trong việc sản xuất các thiết bị phục vụ nhu cầu cuộc sống và giải trí của con người. 1.2.Tổng quan về trình biên dịch Trình biên dịch là chương trình dùng để đọc một chương trình được viết trong một ngôn ngữ lập trình được gọi là ngôn ngữ nguồn (source language) và dịch chương trình đó sang chương trình tương ứng trong ngôn ngữ khác, ngôn ngữ đích (target language). Chương trình nguồn Trình biên dịch Chương trình đích Thông báo lỗi Hình 1-1 Vị trí của trình biên dịch Như vậy thực tế sẽ có rất nhiều trình biên dịch, vì tồn tại hàng nghìn các ngôn ngữ nguồn từ những ngôn ngữ lập trình họ cổ điển (Fortran, Pascal) đến các ngôn ngữ đặc biệt xuất hiện rất nhiều trong lĩnh vực ứng dụng máy tính. Trang 1 Chương 1. Trình biên dịch Ngôn ngữ đích cũng rất đa dạng vì có thể là ngôn ngữ lập trình bất kì hoặc là ngôn ngữ máy. Trình biên dịch đầu tiên xuất hiện vào những năm đầu năm 50 của thế kỷ 20. Lúc đó viết trình biên dịch quả là một công việc hết sức khó khăn. Trình biên dịch ngôn ngữ Fortran đầu tiên đã phải viết trong 18 năm/công người. 1.3.Các phần của trình biên dịch Chương trình nguồn trong ngôn ngữ lập trình không gì khác là chuỗi các ký tự. Trình biên dịch có nhiệm vụ chuyển chuỗi ký tự này sang chuỗi ký hiệu khác – đó là mã đối tượng. Quá trình này bao gồm các quá trình nhỏ hơn và được đặt tên như sau: ¾ Phân tích từ vựng. ¾ Bảng ký hiệu và thông báo lỗi. ¾ Phân tích cú pháp. ¾ Phân tích ngữ nghĩa. ¾ Sinh mã trung gian. ¾ Tối ưu mã trung gian. ¾ Sinh mã đối tượng. Đối với một trình biên dịch tồn tại trong thực tế, thứ tự các quá trình nhỏ có thể hơi khác so với thứ tự ở trên. Có thể một số quá trình nhỏ kết hợp lại với nhau thành một quá trình duy nhất. Trình biên dịch phải có khả năng nhận biết chuỗi nhập vào có phải là một chương trình hợp lệ cú pháp hay không. Nếu không, trình biên dịch phải thông báo lỗi. Ở đây 6 giai đoạn đầu sẽ được mô tả một cách khái quát. Thực ra những giai đoạn này không nhất thiết phải xuất hiện một cách tách biệt trong một trình biên dịch. Nhưng để cho tiện lợi từng giai đoạn sẽ được giới thiệu để thấy rõ khái niệm của từng phần trong quá trình biên dịch. 1.3.1.Phân tích từ vựng (lexical analysis) Giai đoạn phân tích từ vựng là giai đoạn đầu của quá trình biên dịch. Dòng nhập vào trình biên dịch là chuỗi các ký tự cho phép của một ngôn ngữ lập trình, cũng là chuỗi nhập vào bộ phân tích từ vựng ( lexical analyzer). Thí dụ ngôn ngữ Pascal : các ký tự alphabet là các ký tự sau Trang 2 Chương 1. Trình biên dịch ¾ A…Z, a…z, $, @ 0 1 2 … 9 dấu trống ¾ + = := / * () , & > = … Trong chương trình nguồn, sự kết hợp một số ký tự alphabet sẽ tạo nên một thực thể của ngôn ngữ. Thí dụ: BEGIN là sự kết hợp của 5 ký tự B, E, G, I, N tạo nên thực thể là từ khoá BEGIN. Các thực thể của chương trình nguồn thường bao gồm: ¾ Ký hiệu trống, dấu tab, dấu xuống hàng. ¾ Từ khoá: begin, end, goto, while, do, integer… ¾ Chuỗi các ký tự số tượng trưng cho hằng số. ¾ Ký hiệu, dùng để đặt tên cho các biến, hàm thủ tục, nhãn. ¾ Các ký hiệu đặt biệt: +, -, /, *, :=, =, >, >=, <= Các thực thể này được gọi là token. Nhiệm vụ của bộ phân tích từ vựng là khi tiếp nhận chuỗi ký tự nhập phải biết nhóm các ký tự thành các thực thể cú pháp token. Token là ký hiệu kết thúc (terminal symbol), mỗi token sẽ có một cấu trúc từ vựng. Cấu trúc từ vựng này là một cặp (loại token, dữ liệu), gồm hai thành phần: ¾ Thành phần thứ nhất là phạm trù cú pháp: hằng, biến. ¾ Thành phần thứ hai là con trỏ, chỉ đến thông tin của token, được cất giữ trong bảng, được gọi là bảng danh biểu hay bảng ký hiệu (symbol table). Với ngôn ngữ lập trình cho trước, số lượng loại token là hữu hạn. Tóm lại, bộ phân tích từ vựng là bộ dịch (translator) mà đầu nhập của nó là chuỗi các ký tự tượng trưng cho chương trình nguồn, đầu ra là các token. Dạng đầu ra này là đầu nhập của bộ phân tích cú pháp (syntactic analyzer). Thí dụ : Chương trình nguồn là phát biểu gán trong ngôn ngữ Pascal COST := (PRICE + TAX) * 65 Bộ phân tích từ vựng có nhiệm vụ nhận biết: ¾ COST, PRICE, TAX là nhóm token thuộc loại ký hiệu, 65 là token thuộc loại hằng. ¾ Các ký tự :=, (, ), +, * tự bản thân là token. Giả sử tất cả hằng, ký hiệu là các token có loại và . Thành phần thứ hai là dữ liệu ở đây chính là con trỏ chỉ đến vị trí của các token đó trong bảng ký hiệu, Trang 3 Chương 1. Trình biên dịch chứa đựng trị từ vựng (lexeme) của token và thuộc tính khác của token. Thành phần thứ nhất của token sẽ được dùng trong giai đoạn phân tích cú pháp. Thành phần thứ hai của token được dùng trong giai đoạn xử lý ngữ nghĩa và sinh mã đối tượng. Trở lại với ví dụ trên, đầu ra của bộ phân tích tự vựng sẽ có các token sau: (,1) := (,2) + (,3) * (,4) Để đơn giản, biểu thức trên có thể viết lại thành: id1 := ( id2 + id3 ) * num4 Các chỉ số 1, 2, 3, 4 là con trỏ của token tương ứng trong bảng ký hiệu trong Bảng 1-1. Các ký hiệu :=, (, ), *, là các token, loại token sẽ được hiểu là chính nó, không có dữ liệu, nên chúng không có thành phần thứ hai là con trỏ. Sự phân tích từ vựng sẽ đơn giản nếu token có nhiều hơn 1 ký tự, được cô lập bởi các ký tự mà tự chúng là token. Ở thí dụ trên, COST, PRICE, TAX, 65 là các token, được tạo bởi nhiều hơn 1 ký tự được cô lập bởi các token :=, (, +, ), *. Rõ ràng :=, (, ), +, * không thể là một thành phần trong COST, PRICE, TAX, 65. Song trong các trường hợp khác thì phân tích tự vựng không phải đơn giản như vậy. Thí dụ: trong Fortran ta có hai phát biểu sau DO 10 I = 1.15 (1) DO 10 I = 1, 15 (2) Giả sử dấu trống được bỏ qua khi bộ phân tích từ vựng xét các ký tự. Như vậy trong trượng hợp (1) DO10I là biến và 1.15 là hằng và (1) là phát biểu gán. Trong trường hợp (2) DO là từ khoá, I là biến vòng DO, 1 và 15 là hằng. Trong hai trường hợp trên, bộ phân tích từ vựng chỉ xác định được token kế tiếp khi gặp dấu ‘.’ trong (1) và dấu ‘,’ trong (2). Như vậy bộ phân tích từ vựng cần phải nhìn thấy trước 1 token. Nhưng nhìn thấy trước 1 token nhiều khi cũng chưa đủ. Thí dụ: DECLARE (X1, X2, Xn) trong ngôn ngữ PL/I. Bộ phân tích từ vựng sẽ không thể nói được DECLARE là tên hàm và X1, X2, Xn là các đối số của hàm hay DECLARE là từ khoá khai báo biến, X1, X2, Xn là các ký hiệu mà kiểu dữ liệu của chúng sẽ đứng ngay sau dấu đóng ngoặc ‘)’. Muốn kết luận được một trong hai trường hợp là đúng, bộ phân tích từ vựng phải có khả năng nhìn trước một khoảng cách bất Trang 4 Chương 1. Trình biên dịch kỳ. Từ những suy nghĩ trên dẫn đến hai cách tiếp cận với việc phân tích từ vựng. Hầu hết các kỹ thuật được sử dụng để phân tích từ vựng cũng nằm trong hai phạm trù trên. 1.3.1.1.Bộ phân tích từ vựng thao tác trực tiếp (directly) Nếu có một chuỗi ký tự của văn bản nhập và có con trỏ trong văn bản, đánh dấu vị trí bắt đầu tìm token thì bộ phân tích từ vựng sẽ xác định được ngay token nằm phía bên phải của vị trí con trỏ. Sau đó nó sẽ chuyển vị trí con trỏ về bên phải, ở vị trí ký tự đầu tiên, đứng sau ký tự cuối cùng của token vừa được xác định. Thí dụ: COST := ( PRICE + TAX ) * 65 Vị trí con trỏ trước khi xác định được token PRICE Vị trí con trỏ sau khi xác định được token PRICE 1.3.1.2.Bộ phân tích từ vựng thao tác gián tiếp (indirectly) Nếu với chuỗi ký tự của văn bản nhập cho trước, có con trỏ trong văn bản và loại token cho trước, bộ phân tích từ vựng sẽ xác định được token nếu các ký tự đứng ngay sau con trỏ tạo nên token của loại token cho trước. Nếu đúng con trỏ sẽ được chuyển đến ký tự đứng ngay sau token vừa được xác định. Thí dụ: xét văn bản trong Fortran DO 10 I = 1, 15 Giả sử con trỏ chỉ tận cùng bên trái của văn bản. Bộ phân tích từ vựng gián tiếp sẽ hỏi token có thuộc loại DO hay id. Trong trường hợp thứ nhất con trỏ sẽ chuyển sang phải với khoảng cách là hai ký tự. Trường hợp thứ hai là năm ký tự. Còn bộ phân tích từ vựng trực tiếp sẽ kiểm tra văn bản cho đến khi gặp dấu ‘ ,’ lúc đó bộ phân tích từ vựng sẽ kết luận token được nhận biết thuộc loại DO. Con trỏ sẽ được dịch chuyển sang phải hai ký tự mặc dù có nhiều ký hiệu được rà. Trang 5 Chương 1. Trình biên dịch 1.3.2.Bảng ký hiệu (bảng danh biểu) Các token được bộ phân tích từ vựng nhận biết và các thông tin của từng token sẽ được lưu chứa trong bảng danh biểu hay bảng ký hiệu. Giả sử ta có phát biểu: COST := ( PRICE + TAX ) * 65 Sau khi phát biểu trên được đi qua bộ phân tích từ vựng, bảng ký hiệu sẽ chứa các thông tin sau: Bảng 1-1 Bảng ký hiệu Chỉ số 1 2 3 4 Token Lexeme id id id num COST PRICE TAX 65 Các thông tin khác biến thực biến thực biến thực hằng số nguyên Nếu bộ phân tích từ vựng nhận tiếp các chuỗi ký tự của chương trình nhập, để nhận dạng token, thì bảng ký hiệu cũng thường xuyên được truy xuất. Hành vi truy xuất nhằm hai mục đích: nếu ký hiệu vừa được nhận dạng đã được lưu chứa trong bảng ký hiệu thì phần thứ hai của token là dữ liệu sẽ được cập nhật bằng chỉ số của ký hiệu đó trong bảng ký hiệu. Thí dụ: COST có chỉ số là 1 trong bảng ký hiệu, COST lại xuất hiện trong chuỗi nhập sau: Y := COST * 2.0 Chuỗi xuất của bộ phân tích từ vựng là: id5 := id1 * num6 Ù (id,5) := (id,1) * (num, 6) Trong trường hợp này COST không cất vào bảng ký hiệu nữa, nhưng bộ phân tích từ vựng sẽ đẩy ra token (id,1), 1 là vị trí COST đã được cất trong bảng ký hiệu trước đó. Bảng ký hiệu thường xuyên được truy xuất để thêm hoặc truy xuất các token, do đó phải thoả mãn hai điều kiện: ¾ Thực hiện nhanh các thao tác thêm token, hoặc các thông tin của token. ¾ Có khả năng truy xuất nhanh các thông tin của 1 token. Trang 6 Chương 1. Trình biên dịch 1.3.3.Phát hiện và thông báo lỗi Ở mỗi giai đoạn của quá trình biên dịch một chương trình nguồn đều có thể có lỗi. Như vậy sau khi phát hiện một lỗi, trình biên dịch xem xét lỗi đó xem có tiếp tục quá trình dịch hay không. Tất nhiên, nếu một trình biên dịch mà ngay khi phát hiện lỗi đầu tiên đã dừng chương trình thì không hữu hiệu. Trong giai đoạn phân tích từ vựng và cú pháp thường xuất hiện nhiều lỗi do trình biên dịch phát hiện. Trong lúc phân tích từ vựng lỗi được phát hiện khi phần còn lại trên bảng nhập không thể tạo nên token. Lỗi xãy ra khi bộ phân tích cú pháp không thể xây dựng cấu trúc cú pháp cho chuỗi token cho trước. Lỗi cũng có thể được phát hiện trong quá trình phân tích ngữ nghĩa, khi trình biên dịch kiểm tra kiểu dữ liệu của hai toán hạng thuộc một phép toán không phù hợp. Thí dụ một toán hạng thuộc kiểu dãy, cộng với toán hạng là tên của chương trình con. 1.3.4.Phân tích cú pháp (Syntactic analysis parsing) Chuỗi xuất ra từ bộ phân tích từ vựng là các token có dạng (loại token, dữ liệu), sẽ là chuỗi nhập vào bộ phân tích cú pháp. Bộ phân tích cú pháp chỉ xét thành phần thứ nhất của token là loại token. Sự phân tích cú pháp là một quá trình, trong quá trình này chuỗi các token sẽ được kiểm tra xem có thể được biểu diễn bằng cấu trúc cú pháp của ngôn ngữ lập trình cho trước không? Nếu tồn tại một cấu trúc cú pháp cho chuỗi nhập thì cấu trúc được sinh ra đó chính là kết quả của quá trình phân tích cú pháp. Ở giai đoạn sinh mã, cấu trúc cú pháp sẽ được xem xét để từ đó sinh ra mã cho chuỗi ký tự của chương trình nguồn. Giả sử ta có phát biểu COST := (PRICE + TAX) * 65 Kết quả của quá trình phân tích từ vựng COST := (PRICE + TAX) * 65 Æ id1 := (id2 + id3) * num4 Kết quả của quá trình phân tích cú pháp: Trang 7 ( 1-1)