Tập bài giảng Chương trình dịch

Tập bài giảng “Chương trình dịch” được biên soạn theo chương trình chi tiết môn học “Chương trình dịch” của trường Đại học Sư phạm Kỹ thuật Nam Định. Mục tiêu của tập đề cương bài giảng nhằm cung cấp các kiến thức cơ bản, tổng quan về chương trình dịch. Giúp sinh viên hiểu được các kiến thức cơ bản, tổng quan về chương trình dịch nói chung và các kỹ thuật cơ bản trong xây dựng các bộ phân tích từ vựng và phân tích cú pháp của các chương trình dịch của các ngôn ngữ lập trình bậc cao. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Tập bài giảng Chương trình dịch Môc lôc LỜI NÓI ĐẦU ............................................................................................................ 7 Chƣơng 1. TỔNG QUAN VỀ CHƢƠNG TRÌNH DỊCH .......................................... 9 1.1. Mở đầu ............................................................................................................ 9 1.2. Chƣơng trình dịch ......................................................................................... 11 1.2.1. Các khái niệm ........................................................................................ 11 1.2.2. Mô hình phân tích - tổng hợp của một chƣơng trình dịch ..................... 12 1.2.3. Môi trƣờng của chƣơng trình dịch ......................................................... 13 1.3. Phân tích chƣơng trình nguồn ...................................................................... 14 1.3.1. Phân tích từ vựng (Lexical Analysis) .................................................... 14 1.3.2. Phân tích cú pháp (Syntax Analysis) ..................................................... 16 1.3.3. Phân tích ngữ nghĩa (Semantic Analysis) .............................................. 17 1.4. Các giai đoạn của chƣơng trình dịch ............................................................. 18 1.4.1. Quản lý bảng ký hiệu ............................................................................. 19 1.4.2. Xử lý lỗi ................................................................................................. 19 1.4.3. Các giai đoạn phân tích .......................................................................... 20 1.4.4. Sinh mã trung gian ................................................................................. 20 1.4.5. Tối ƣu mã ............................................................................................... 21 1.4.6. Sinh mã đích .......................................................................................... 21 1.5. Nhóm các giai đoạn ....................................................................................... 21 1.5.1. Kỳ đầu (Front End) ................................................................................ 22 1.5.2. Kỳ sau (Back End) ................................................................................. 22 1.6. Các đặc trƣng của ngôn ngữ lập trình bậc cao .............................................. 22 1.6.1. Từ vựng .................................................................................................. 22 1.6.2. Cú pháp .................................................................................................. 23 1.6.3. Ngữ nghĩa ............................................................................................... 23 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 1 ..................................................................... 24 Chƣơng 2. PHÂN TÍCH TỪ VỰNG ........................................................................ 25 2.1. Nhắc lại một số kiến thức về văn phạm – ngôn ngữ - Automat.................... 25 2.1.1. Một số khái niệm cơ sở .......................................................................... 25 2.1.2. Biểu diễn ngôn ngữ ................................................................................ 26 2.1.3. Văn phạm ............................................................................................... 27 2.1.4. Văn phạm phi ngữ cảnh ......................................................................... 28 1 2.1.5. Biểu thức chính quy (Regular Expression)............................................ 29 2.1.6. Automat hữu hạn đơn định .................................................................... 31 2.1.7. Automat hữu hạn không đơn định - NFA (Nondeterministic Finite Automata) ........................................................................................................ 31 2.1.8. Automat hữu hạn không đơn định với ε-dịch chuyển (NFAε) .............. 32 2.2. Giai đoạn phân tích từ vựng ......................................................................... 34 2.2.1. Thẻ từ, mẫu từ vựng và trị từ vựng (từ vị)............................................. 35 2.2.2. Nhận biết thẻ từ (token) ......................................................................... 40 2.3. Kỹ thuật đọc chƣơng trình nguồn ................................................................. 43 2.3.1. Cặp bộ đệm (Buffer Pairs) ..................................................................... 43 2.3.2. Khóa cầm canh (Sentinel) ..................................................................... 44 2.4. Kỹ thuật sử dụng Automat để phân tích từ vựng .......................................... 45 2.4.1. Giải thuật sử dụng DFA ......................................................................... 45 2.4.2. Giải thuật sử dụng NFA ......................................................................... 48 2.4.3. Giải thuật sử dụng NFA ....................................................................... 49 2.5. Kỹ thuật biến đổi Automat ............................................................................ 50 2.6. Giải thuật Thomson ....................................................................................... 61 CÂU HỎI VÀ BÀI TẬP CHƢƠNG 2 ..................................................................... 66 Chƣơng 3. PHÂN TÍCH CÚ PHÁP ......................................................................... 76 3.1. Giai đoạn phân tích cú pháp .......................................................................... 76 3.1.1. Vị trí, chứ ...