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
Có thể bạn quan tâm!
-
Chương trình dịch - 2 -
Phân Tích Ngữ Nghĩa (Semantic Analysis) -
Nhắc Lại Một Số Kiến Thức Về Văn Phạm – Ngôn Ngữ - Automat
Xem toàn bộ 224 trang tài liệu này.
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
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ức năng, nhiệm vụ của giai đoạn phân tích cú pháp 76
3.1.2. Xử lý lỗi cú pháp 77
3.1.3. Các chiến lược phục hồi lỗi 77
3.1.4. Các phương pháp phân tích cú pháp 78
3.2. Biến Ðổi văn phạm phi ngữ cảnh 79
3.2.1. Cây phân tích cú pháp (Parsing tree) và dẫn xuất 79
3.2.2. Ngôn ngữ nhập nhằng (Ambiguity) 82
3.2.3. Kỹ thuật khử nhập nhằng 83
3.2.4. Kỹ thuật khử đệ quy trái 84
3.2.5. Kỹ thuật thừa số hoá bên trái 88
3.3. Phân tích cú pháp từ trên xuống 93
3.3.1. Phân tích cú pháp đệ quy xuống 93
3.3.2. Phân tích cú pháp dự đoán (phân tích LL(1)) 96
3.4. Phân tích cú pháp từ dưới lên (Bottom - up parsing) 117
3.4.1. Phân tích đẩy thu ( Shift – Reduce parsing) 118
3.4.2. Phân tích cú pháp thứ bậc toán tử 124
3.4.3. Phân tích LR(K) 127
3.4.4. Giải thuật phân tích LR 128
3.4.5. Xây dựng bảng phân tích cú pháp 133
CÂU HỎI VÀ BÀI TẬP CHƯƠNG 3 146
LỜI GIẢI TÓM TẮT HOẶC HƯỚNG DẪN 155
TÀI LIỆU THAM KHẢO 218
DANH MỤC HÌNH VẼ
Hình 1.1. Mô tả việc dịch các chương trình sang Assembly 10
Hình 1.2. Sơ đồ một chương trình dịch 11
Hình 1.3. Mô hình phân tích - tổng hợp 12
Hình 1.4. Cây phân tích cú pháp 12
Hình 1.5. Cấu trúc môi trường của chương trình dịch 14
Hình 1.6. Một cây phân tích cú pháp 16
Hình 1.7. Sơ đồ cấu trúc của một chương trình dịch 18
Hình 2.1. NFA với ε - dịch chuyển 35
Hình 2.2. Vị trí của giai đoạn phân tích từ vựng 35
Hình 2.3. Sơ đồ chuyển nhận dạng token relop 42
Hình 2.4. Mô phỏng cặp bộ đệm 44
Hình 2.5. Sơ đồ mô tả Automat đoán nhận biểu thức b*a+bb 46
Hình 2.6. Biểu diễn automat bằng đồ thị 47
Hình 2.7. Đồ thị biểu diễn Automat 48
Hình 2.8. NFA với ε - dịch chuyển 49
Hình 2.9. Sơ đồ giải thuật 52
Hình 2.10. Biểu diễn automat bằng đồ thị 52
Hình 2.11. Biểu diễn automat bằng đồ thị 54
Hình 2.12. Biểu diễn automat bằng đồ thị 55
Hình 2.13. Biểu diễn automat bằng đồ thị 56
Hình 2.14. Sơ đồ giải thuật 57
Hình 2.15. Biểu diễn automat bằng đồ thị 57
Hình 2.16. Biểu diễn automat bằng đồ thị 60
Hình 2.17. Automat đoán nhận biểu thức r= 61
Hình 2.18. Automat đoán nhận biểu thức r = a 61
Hình 2.19. Automat đoán nhận biểu thức r = s+t 61
Hình 2.20. Automat đoán nhận biểu thức r=st 62
Hình 2.21a. Automat đoán nhận biểu thức r = s*62
Hình 2.21b. Automat đoán nhận biểu thức r = s+62
Hình 2.22. Các automat đoán nhận a, b 64
Hình 2.23. Automat đoán nhận r7 = a+b 64
Hình 2.24. Automat đoán nhận r5 = (a+b)*65
Hình 2.25. Automat đoán nhận r=(a b)*abb 65
Hình 3.1. Vị trí của bộ phân tích cú pháp 77
Hình 3.2. Minh họa một cây phân tích cú pháp 80
Hình 3.3. Minh họa một cây phân tích cú pháp 81
Hình 3.4. Xây dựng cây phân tích cú pháp từ dẫn xuất 82
Hình 3.5. Hai cây phân tích cú pháp của xâu id + id * id 83
Hình 3.6. Hai cây phân tích cú pháp của cùng một xâu 84
Hình 3.7 a, b, c. Mô tả quá trình phân tích xâu w = cad 94
Hình 3.8. Sơ đồ chuyển của một biến 97
Hình 3.9. Sơ đồ chuyển cho các biến 99
Hình 3.10. Sơ đồ chuyển rút gọn 100
Hình 3.11. Mô tả hình tổ chức dữ liệu của kỹ thuật dự đoán 104
Hình 3.12. Cây phân tích cú pháp cho xâu vào id + id * id 107
Hình 3.13. Mô hình phân tích đẩy - thu 121
Hình 3.13a. Cây phân tích cú pháp cho xâu vào id * id +id theo đẩy – thu 121
Hình 3.14. Mô hình bộ phân tích cú pháp LR 128
Hình 3.14a. Cây phân tích cú pháp cho xâu vào id * id + id theo LR 128
Hình 3.15. Sơ đồ chuyển 142
DANH MỤC BẢNG
Bảng 2.1. Các ví dụ về token 38
Bảng 2.2. Biểu thức chính quy cho một số token 41
Bảng 2.3. Mô phỏng automat đoán nhận từ bbaaabb 46
Bảng 2.4. Mô phỏng automat đoán nhận từ aaabba 47
Bảng 2.5. Mô tả quá trình đoán nhận xâu 49
Bảng 2.6. Mô tả quá trình đoán nhận xâu 50
Bảng 2.7. Mô phỏng giải thuật 54
Bảng 2.8. Mô phỏng giải thuật 55
Bảng 2.9. Mô phỏng giải thuật 60
Bảng 3.1. Bảng phân tích cú pháp 107
Bảng 3.2. Phân tích cú pháp cho xâu vào id + id * id 107
Bảng 3.3. Bảng phân tích cú pháp 113
Bảng 3.4. Bảng phân tích cú pháp 114
Bảng 3.5. Bảng phân tích cú pháp M phục hồi lỗi 116
Bảng 3.6. Phân tích cú pháp cho xâu vào + id * + id phục hồi lỗi 117
Bảng 3.7. Quá trình phân tích đẩy thu xâu id1 + id2* id3123
Bảng 3.8. Các quan hệ thứ bậc toán tử 125
Bảng 3.9. Bảng quan hệ thứ bậc các toán tử 125
Bảng 3.10. Bảng phân tích cú pháp 131
Bảng 3.11. Quá trình phân tích xâu id*id+id 132
Bảng 3.12. Mô phỏng giải thuật đoán nhận xâu id1 + id2* id3135
Bảng 3.13. Bảng phân tích cú pháp LR(1) 144
LỜI NÓI ĐẦU
LỜI NÓI ĐẦU
Chương trình dịch (compiler) là bộ môn khoa học quan trọng của khoa học máy tính. Ở nhiều nước trên thế giới, môn học “Chương trình dịch” đã trở thành môn học bắt buộc và là cơ sở của các ngành thuộc lĩnh vực công nghệ thông tin. Ở nước ta, hiện nay nhiều trường đại học cũng đang giảng dạy môn học này cho sinh viên các ngành khoa học máy tính và công nghệ thông tin. ... Tuy nhiên tài liệu phục vụ giảng dạy cho môn học ở nước ta còn ít, thời lượng dành cho môn học cũng còn rất khác nhau ở mỗi trường. §Ó cã mét néi dung thèng nhÊt cho c¸c ngµnh thuộc lÜnh vùc c«ng nghÖ th«ng tin cđa Tr•êng, tr•êng §¹i häc S• ph¹m Kü thuËt Nam
§Þnh, Trường ®· ban hµnh ch•¬ng tr×nh chi tiÒt cho m«n häc. Việc xuất bản tập đề cương bài giảng nhằm đáp ứng nhu cầu cung cấp tài liệu môn học cho việc giảng dạy của giảng viên và học tập của sinh viên các ngành thuộc khoa Công nghệ Thông tin trường Đại học Sư phạm Kỹ thuật Nam Định nói riêng và làm tại liệu tham khảo cho sinh viên và cán bộ giảng dạy các trường nói chung.
Tập đề cương 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. Đây là các kiến thức nền tảng, làm cơ sở cho việc xây dựng ra các ngôn ngữ lập trình bậc cao và các chương trình dịch. Về nội dung, tập đề cương bài giảng được chia thành 3 chương:
Chương 1. Tổng quan về chương trình dịch
Chương này trình bày: Các khái niệm, kiển thức cơ bản về chương trình dịch. Môi trường của chương trình dịch. Các giai đoạn của chương trình dịch. Nhóm các giai đoạn của chương trình dịch. Các đặc trưng cơ bản của ngôn ngữ lập trình bậc cao.
Chương 2. Phân tích từ vựng
Chương này nhắc lại một số kiến thức về văn phạm, ngôn ngữ, Automat. Trình bày các kiến thức về thẻ từ, mẫu từ vựng và trị từ vựng; vị trí, nhiệm vụ của giai đoạn phân tích từ vựng; một số kỹ thuật đọc chương trình nguồn; kỹ thuật sử dụng Automat để phân tích từ vựng và kỹ thuật biến đổi automat.
Chương 3. Phân tích cú pháp
LỜI NÓI ĐẦU
Chươngnày trình bày các kiến thức cơ bản về: Vị trí, nhiệm vụ của giai đoạn phân tích cú pháp và các phương pháp phân tích cú pháp. Các kỹ thuật biến đổi văn phạm: khử đệ quy trái, thừa số hoá bên trái, khử nhập nhằng. Phương pháp phân tích top – down: phân tích cú pháp đệ quy xuống, phân tích cú pháp dự đoán. Phương pháp phân tích bottom – up: phân tích cú pháp đẩy thu, phân tích cú pháp LR(k).
Đặc biệt cuối mỗi chương còn đưa ra hệ thống câu hỏi, bài tập nhằm củng cố, khắc sâu, nâng cao và vận dụng các kiến thức vào giải các bài tập và cuối cùng là phần lời giải tóm tắt hoặc hướng dẫn cho các bài tập nhằm giúp sinh viên tự rèn luyện kỹ năng và kiểm tra kiến thức.
Trong quá trình biên soạn, tập đề cương bài giảng không tránh khỏi những sai sót, rất mong đồng nghiệp và các sinh viên đóng góp ý kiến để tập đề cương bài giảng ngày càng được hoàn thiện hơn.
Người biên soạn
Phạm Hùng Phú