Tập đề cương bài giảng Chương trình dịch (Phần 1)

75 trang Gia Huy 17/05/2022 3320

Download

Bạn đang xem 20 trang mẫu của tài liệu "Tập đề cương bài giảng Chương trình dịch (Phần 1)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

tap_de_cuong_bai_giang_chuong_trinh_dich_phan_1.pdf

Nội dung text: Tập đề cương bài giảng Chương trình dịch (Phần 1)

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ứ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 2
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 3
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 4
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 5
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* id3 123 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* id3 135 Bảng 3.13. Bảng phân tích cú pháp LR(1) 144 6
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 7
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ú 8
Chƣơng 1. Tổng quan về chƣơng trình dịch Chƣơng 1 TỔNG QUAN VỀ CHƢƠNG TRÌNH DỊCH Mục tiêu: Giúp sinh viên có khả năng: - Hiểu đƣợc các khái niệm cơ bản: Chƣơng trình dịch, hệ thống thông dịch, biên dịch. - Hiểu đƣợc môi trƣờng của một chƣơng trình dịch. - Hiểu đƣợc cấu trúc của một chƣơng trình dịch - Hiểu đƣợc các giai đoạn của chƣơng trình dịch: vị trí, nhiệm vụ. - Biết đƣợc các đặc trƣng cơ bản của ngôn ngữ lập trình bậc cao. Nội dung chính: - Khái niệm 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. 1.1. Mở đầu Các ngôn ngữ lập chƣơng trình thực chất là các ngôn ngữ dùng để biểu diễn giải thuật thực hiện một bài toán nào đó. Để thuận tiện và đơn giản cho quá trình viết chƣơng trình ngƣời ta xây dựng các ngôn ngữ lập trình bậc cao nhƣ Algol, Pascal, C, C++, Visual Fox, Visual Basic, Hiện nay có rất nhiều ngôn ngữ lập trình bậc cao. Những ngôn ngữ lập trình bậc cao có chung đặc tính là không phụ thuộc vào máy tính, gần gũi với toán học và các lĩnh vực hoạt động của con ngƣời. Chẳng hạn Visual Fox là ngôn ngữ vừa gần gũi, thích hợp với công việc quản lý sản xuất, kinh doanh vừa đủ chặt chẽ để diễn đạt các công thức toán học và mang tính logic cao. Viết chƣơng trình bằng ngôn ngữ máy có ƣu điểm cơ bản là chƣơng trình thực hiện nhanh, vì khi nạp chƣơng trình vào máy tính nó chạy đƣợc ngay không cần giai đoạn dịch, song nó có những nhƣợc điểm cơ bản sau: - Ngôn ngữ máy rất xa lạ với ngôn ngữ toán học và ngôn ngữ tự nhiên của con ngƣời. - Dễ sinh ra lỗi, song lại khó phát hiện lỗi, mất nhiều thời gian hiệu chỉnh chƣơng trình. - Khó diễn đạt rõ ràng giải thuật. - Phụ thuộc vào máy tính, không thuận tiện cho việc giao lƣu phổ biến các chƣơng trình, các giải thuật toán tốt, dẫn đến sự lãng phí về lao động xã hội. 9
Chƣơng 1. Tổng quan về chƣơng trình dịch Những lý do nêu trên là nguyên nhân thúc đẩy việc sản sinh ra nhiều ngôn ngữ lập trình bậc cao khác nhau. Trái ngƣợc với ngôn ngữ máy, ngôn ngữ lập trình bậc cao có các đặc điểm sau: - Gần gũi với ngôn ngữ toán học và ngôn ngữ tự nhiên của con ngƣời. - Không phụ thuộc vào máy cụ thể, do vậy dễ phổ biến, dễ giao lƣu trao đổi hợp tác giữa những ngƣời làm chƣơng trình, tăng hiệu quả lao động của xã hội. - Ít sinh ra lỗi, cho phép phát hiện lỗi nhanh và do vậy tiết kiệm thời gian hiệu chỉnh chƣơng trình. Về nguyên tắc, các máy tính chỉ có thể thực hiện đƣợc các chƣơng trình viết bằng ngôn ngữ máy. Vì vậy, các chƣơng trình viết bằng các ngôn ngữ lập trình bậc cao muốn máy tính thực hiện đƣợc phải trải qua giai đoạn chuyển ngôn ngữ lập trình bậc cao sang ngôn ngữ máy. Giai đoạn chuyển ngôn ngữ lập trình bậc cao sang ngôn ngữ máy đƣợc gọi là giai đoạn dịch chƣơng trình hay ngắn gọn là dịch. Chƣơng trình thực hiện giai đoạn dịch gọi là chƣơng trình dịch (Compiler). Đối với chƣơng trình dịch thì các chƣơng trình viết bằng ngôn ngữ lập trình bậc cao là dữ liệu đầu vào và đƣợc gọi là chƣơng trình nguồn; chƣơng trình là kết quả dịch (đầu ra) của chƣơng trình dịch đƣợc gọi là chƣơng trình đích. Ngôn ngữ dùng để viết chƣơng trình nguồn ta gọi là ngôn ngữ nguồn. Ngôn ngữ dùng để viết chƣơng trình đích ta gọi là ngôn ngữ đích. Trong thực tế với mục đích tận dụng các chƣơng trình tốt đã có, viết bằng các ngôn ngữ lập trình bậc cao khác nhau; ngƣời ta thƣờng dịch các chƣơng trình nguồn ra ngôn ngữ trung gian sau đó ghép chúng lại thành một chƣơng trình viết bằng cùng một ngôn ngữ sau đó mới chuyển sang ngôn ngữ máy. Thậm chí có những chƣơng trình đƣợc viết bằng nhiều ngôn ngữ lập trình khác nhau, ngƣời ta gọi là chƣơng trình viết ở dạng hợp ngữ. Hình 1.1 mô tả việc dịch các chƣơng trình viết bằng các ngôn ngữ khác nhau sang chƣơng trình viết bằng ngôn ngữ trung gian Assembly. Chƣơng trình Chƣơng trình ++ Trong C Trong C Assembly Chƣơng trình Chƣơng trình trong Pascal Trong Assembly Hình 1.1. Mô tả việc dịch các chương trình sang Assembly 10
Chƣơng 1. Tổng quan về chƣơng trình dịch - Về bản chất, mọi chƣơng trình viết bằng một ngôn ngữ lập trình bậc cao đều đƣợc coi là một dãy ký hiệu và đƣợc gọi là xâu vào hay văn bản vào. Do vậy, quá trình dịch có thể coi là quá trình biến đổi một xâu vào hay văn bản vào viết ở ngôn ngữ này thành một xâu ra hay văn bản ra viết bằng ngôn ngữ khác sao cho nó bảo toàn “ngữ nghĩa” (Semantic) của xâu vào (chƣơng trình tƣơng đƣơng). Vấn đề bảo toàn “ngữ nghĩa” của văn bản vào là vấn đề chƣa đƣợc xác định rõ ràng trong lý thuyết chƣơng trình dịch. Một số tác giả đã đƣa ra khái niệm bảo toàn “ngữ nghĩa” nhƣ sau: Hai xâu đƣợc gọi là bản dịch của nhau nếu khi dịch sang ngôn ngữ thứ ba thì chúng có kết quả nhƣ nhau. 1.2. Chƣơng trình dịch 1.2.1. Các khái niệm 1) Khái niệm chương trình dịch Chƣơng trình dịch là một chƣơng trình làm nhiệm vụ đọc một chƣơng trình đƣợc viết bằng một ngôn ngữ - ngôn ngữ nguồn (source language), rồi dịch nó thành một chƣơng trình tƣơng đƣơng ở một ngôn ngữ khác - Ngôn ngữ đích (target languague). Một phần quan trọng trong quá trình dịch là ghi nhận lại các lỗi có trong chƣơng trình nguồn để thông báo lại cho ngƣời viết chƣơng trình. Chƣơng trình Chƣơng Chƣơng trình nguồn trình dịch đích Báo lỗi Hình 1.2. Sơ đồ một chương trình dịch 2) Biên dịch và thông dịch Ngƣời ta chia chƣơng trình dịch thành hai dạng là trình biên dịch và trình thông dịch. a) Trình biên dịch (Compiler) Trong hệ thống biên dịch, chƣơng trình dịch đọc toàn bộ chƣơng trình nguồn và dịch toàn bộ chƣơng trình nguồn sang chƣơng trình đích. - Chƣơng trình nguồn viết bằng ngôn ngữ lập trình bậc cao. - Chƣơng trình đích viết bằng ngôn ngữ máy hoặc assembly hoặc ngôn ngữ trung gian. Chƣơng trình đích cần có khả năng chạy độc lập trên tất cả các máy mà không cần chƣơng trình dịch nữa. 11
Chƣơng 1. Tổng quan về chƣơng trình dịch Ƣu điểm của chƣơng trình dịch là chƣơng trình chạy nhanh. Nhƣợc điểm của nó là việc thiết kế và cài đặt phức tạp. Ví dụ nhƣ chƣơng trình dịch của Turbo C hay Turbo Pascal. b) Trình thông dịch (Interpreter) Trong hệ thống thông dịch, chƣơng trình dịch đọc vào từng câu lệnh, dịch sang chƣơng trình đích rồi thực hiện ngay câu lệnh đó. Ví dụ nhƣ chƣơng trình dịch của hệ điều hành DOS khi thực hiện lệnh tại dấu nhắc lệnh hay chƣơng trình dịch của hệ quản trị cơ sở dữ liệu Visual Foxpro khi thực hiện lệnh tại cửa sổ lệnh. 1.2.2. Mô hình phân tích - tổng hợp của một chƣơng trình dịch Chƣơng trình dịch thƣờng bao gồm hai quá trình: phân tích và tổng hợp - Phân tích đặc tả trung gian - Tổng hợp chƣơng trình đích Chƣơng trình Phân tích Đặc Tổng hợp Chƣơng trình nguồn tả tru ng gian đích Hình 1.3. Mô hình phân tích - tổng hợp Trong quá trình phân tích chƣơng trình nguồn sẽ đƣợc phân rã thành một cấu trúc phân cấp, thƣờng là dạng cây - cây cú pháp (parsing tree). Ví dụ 1.1: Câu lệnh gán position := initial + rate * 60 có cây phân tích cú pháp hình 1.4. stmt expr id assign expr expr position operator := id expr expr + operator id initial number * rate 60 Hình 1.4. Cây phân tích cú pháp 12
Chƣơng 1. Tổng quan về chƣơng trình dịch 1.2.3. Môi trƣờng của chƣơng trình dịch Ngoài chƣơng trình dịch, còn phải cần dùng nhiều chƣơng trình khác nữa để tạo ra một chƣơng trình đích có thể thực thi đƣợc (executable). Các chƣơng trình đó gồm: bộ soạn thảo, bộ tiền xử lý, trình dịch hợp ngữ, bộ tải và liên kết. Hệ thống các chƣơng trình này giúp cho ngƣời lập trình có đƣợc một môi trƣờng hoàn chỉnh để phát triển các ứng dụng. - Bộ soạn thảo: cho phép soạn thảo chƣơng trình nguồn. - Bộ tiền xử lý: Xử lý một số chức năng ban đầu để tạo ra một chƣơng trình nguồn hoàn chỉnh từ một chƣơng trình nguồn khung (nguyên thuỷ) ban đầu. Ví dụ, một chƣơng trình nguồn có thể đƣợc phân thành các module và đƣợc lƣu trong các tập tin riêng rẽ. Công việc tập hợp lại các tập tin này thƣờng đƣợc giao cho một chƣơng trình riêng biệt gọi là bộ tiền xử lý (preprocessor). Bộ tiền xử lý có thể "bung" các ký hiệu tắt đƣợc gọi là các macro thành các câu lệnh của ngôn ngữ nguồn. Ngoài ra, bộ tiền xử lý còn cho phép bỏ qua các chú thích. - Chƣơng trình dịch: cho phép kiểm lỗi chƣơng chƣơng trình, dịch ra ngôn ngữ đích. Dịch ra ngôn ngữ đích nhƣng đang ở dạng định vị lại đƣợc hay có thể ở dạng ngôn ngữ assembly. Ngoài ra, chƣơng trình đích đƣợc tạo ra bởi chƣơng trình dịch có thể cần phải đƣợc xử lý thêm trƣớc khi chúng có thể chạy đƣợc. Thông thƣờng, chƣơng trình dịch chỉ tạo ra mã lệnh hợp ngữ (assembly code) để trình dịch hợp ngữ (assembler) dịch thành dạng mã máy định vị lại đƣợc. - Tải/liên kết: Tải chƣơng trình vào bộ nhớ máy tính và liên kết với một số thủ tục trong thƣ viện hệ thống để tạo thành một chƣơng trình mã máy tuyệt đối và thực thi đƣợc trên máy tính. Hình sau trình bày sơ đồ cấu trúc môi trƣờng của một chƣơng trình dịch trong một hệ thống biên dịch điển hình. 13
Chƣơng 1. Tổng quan về chƣơng trình dịch Chƣơng trình nguồn khung (nguyên thuỷ) Bộ tiền xử lý Chƣơng trình nguồn Trình biên dịch Chƣơng trình đích hợp ngữ Trình dịch hợp ngữ Mã máy khả tái định vị Thƣ viện, Tập tin đối tƣợng Trình tải / Liên kết định vị lại đƣợc Mã máy tuyệt đối Hình 1.5. Cấu trúc môi trường của chương trình dịch 1.3. Phân tích chƣơng trình nguồn Quá trình phân tích chƣơng trình nguồn, về mặt logic có thể chia thành ba giai đoạn phân tích: Phân tích từ vựng, phân tích cú pháp và phân tích ngữ nghĩa. 1.3.1. Phân tích từ vựng (Lexical Analysis) Trong một chƣơng trình dịch, giai đoạn phân tích từ vựng sẽ đọc chƣơng trình nguồn từ trái sang phải (quét nguyên liệu - scanning) để tách ra thành các từ vị (lexeme) và tìm ra các thẻ từ (token) tƣơng ứng cho các từ vị đó. Thẻ từ là dạng ngữ pháp của từ vị; hay nói một cách khác, thẻ từ là tập hợp xâu các ký tự kết thúc (từ vị) có chung nhau luật ngữ pháp sinh ra các từ vị đó và mỗi thẻ từ thƣờng đƣợc đặt bởi một tên để định danh (phân biệt các thẻ từ với nhau) . Mỗi thẻ từ sẽ có một mẫu từ vựng (pattern) để xác định một từ vị là thuộc thẻ từ nào; hay nói cách khác, mẫu từ vựng của thẻ từ là luật ngữ pháp sinh ra các từ vị của thẻ từ đó. 14
Chƣơng 1. Tổng quan về chƣơng trình dịch Từ vị của một thẻ từ là một từ của thẻ từ và nó phải thỏa mãn mẫu từ vựng của thẻ từ đó. Nhờ vào mẫu của thẻ từ, chƣơng trình dịch trong giai đoạn phân tích từ vựng sẽ phân tích để xác định ra các thẻ từ trả về cho giai đoạn phân tích cú pháp hoặc báo lỗi. Ví dụ 1.2: a) Trong một văn phạm có các luật sinh: 1. digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Thì: + digit là thẻ từ (token); + 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 là mẫu từ vựng (pattern) của thẻ từ digit; + Mỗi chữ số: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 là một từ vị (lexeme) của thẻ từ digit. 2. letter A | B | | Z | a | b | | z Thì: + letter là thẻ từ (token); + A | B | | Z | a | b | | z là mẫu từ vựng (pattern) của thẻ từ letter; + Mỗi chữ cái La tinh: A, B, C, , Z, a, b, c, , z là một từ vị (lexeme) của thẻ từ letter. * 3. id (letter | _ )(letter | digit | _ ) Thì: + id là thẻ từ (token); * + (letter | _ )(letter | digit | _ ) là mẫu từ vựng (pattern) của thẻ từ id; + A, X1B, max_1a23 là 3 từ vị (lexeme) của thẻ từ id. b) Trong một văn phạm có các luật sinh: 1. Stmt id := expr 2. Expr expr + exprexpr - exprexpr /exprexpr * expridnumber 3. Relop +-*/ 4. Assign := Quá trình phân tích từ vựng cho câu lệnh gán position:= initial + rate * 60 sẽ tách thành các từ vị (lexeme) và trả về các thẻ từ (token) nhƣ sau: 1. position là từ vị của thẻ từ tên id 2. := là từ vị của thẻ từ phép gán assign 3. initial là từ vị của thẻ từ tên id 4. + là từ vị của thẻ từ phép toán operator 15
Chƣơng 1. Tổng quan về chƣơng trình dịch 5. rate là từ vị của thẻ từ tên id 6. * là là từ vị của thẻ từ phép toán operator 7. 60 từ vị của thẻ từ số nguyên number Trong quá trình phân tích từ vựng các khoảng trắng (blank) sẽ bị bỏ qua. 1.3.2. Phân tích cú pháp (Syntax Analysis) Giai đoạn phân tích cú pháp sẽ dựa vào bộ luật cú pháp để tìm cấu trúc cú pháp của chƣơng trình nguồn. Các cấu trúc cú pháp này sẽ tƣơng ứng với một biểu thức, một phép gán, một khai báo, câu lệnh điều kiện, câu lệnh lặp, Trong nhiều phƣơng pháp phân tích thì kết quả trả về không nhất thiết phải là cây cú pháp. Giai đoạn phân tích cú pháp thực hiện công việc nhóm các thẻ từ của chƣơng trình nguồn thành các ngữ đoạn văn phạm (grammatical phrase), mà sau đó sẽ đƣợc chƣơng trình dịch tổng hợp ra thành phẩm. Thông thƣờng, các ngữ đoạn văn phạm này đƣợc biểu diễn bằng dạng cây phân tích cú pháp (parsing tree). Về bản chất thì phân tích cú pháp sẽ cho ta thông tin về cú pháp của chƣơng trình nguồn và đƣợc thể hiện dƣới dạng cây phân tích cú pháp. Với ngôn ngữ đƣợc đặc tả bởi các luật sinh thì giai đoạn phân tích cú pháp dựa vào các luật sinh để xây dựng cây phân tích cú pháp. Ví dụ 1.3: Với câu lệnh gán position:= initial + rate * 60, giả sử bộ luật cú pháp của ngôn ngữ để nhận biết câu lệnh gán đƣợc đặc tả bởi các luật sinh sau: Stmt id := expr Expr expr + exprexpr - exprexpr /exprexpr * expridnumber Operator +-*/ Assign := Thế thì cây phân tích cú pháp của ví dụ trên sẽ đƣợc xây dựng nhƣ sau: stmt id expr assign expr expr position operator := id expr expr + operator initial id number * rate 60 Hình 1.6. Một cây phân tích cú pháp 16
Chƣơng 1. Tổng quan về chƣơng trình dịch Cấu trúc phân cấp của một chƣơng trình thƣờng đƣợc diễn tả bởi quy luật đệ quy. Ví dụ 1.4: 1. Định danh (tên hay danh biểu - identifier) là một biểu thức (expr). 2. Số (number) là một biểu thức. 3. Nếu expr1 và expr2 là các biểu thức thì: - expr1 + expr2; - expr1 * expr2; - (expr) cũng là những biểu thức. Câu lệnh (statement) cũng có thể định nghĩa đệ quy: 1. Nếu id1 là một Danh biểu (tên hay định danh) và expr2 là một biểu thức thì id1:= expr2 là một lệnh (stmt). 2. Nếu expr1 là một biểu thức và stmt2 là một lệnh thì: - while (expr1) do stmt2; - if (expr1) then stmt2 đều là các lệnh. Ngƣời ta dùng các quy tắc đệ quy nhƣ trên để đặc tả luật sinh (production) cho ngôn ngữ. Sự phân chia giữa quá trình phân tích từ vựng và phân tích cú pháp cũng tuỳ theo công việc thực hiện. 1.3.3. Phân tích ngữ nghĩa (Semantic Analysis) Giai đoạn phân tích ngữ nghĩa sẽ thực hiện công việc: - Kiểm tra các lỗi ngữ nghĩa của chƣơng trình nguồn: Kiểm tra kiểu, phạm vi của hằng, biến; kiểm tra việc sử dụng trùng tên trùng nhau, - Thu nhận thông tin thuộc tính cho các thẻ từ; chẳng hạn, thông tin về giá trị, thông tin về loại của hằng, biến hay hàm cho tên. Một phần quan trọng trong giai đoạn phân tích ngữ nghĩa là kiểm tra kiểu (type checking) và ép chuyển đổi kiểu. Chƣơng trình dịch, trong giai đoạn phân tích ngữ nghĩa sẽ kiểm tra kiểu dựa vào các đặc tả của ngôn ngữ nguồn để xem các toán hạng của một toán tử có hợp lệ hay không và thông báo lỗi nếu thấy lỗi. Ví dụ 1.5: Xét câu lệnh gán position:= initial + rate * 60; Trong khai báo ta có: Var position, initial: integer; Rate: real; Khi phân tích ngữ nghĩa: - Khai báo thứ nhất cho biết position, initial có kiểu số nguyên. - Khai báo thứ hai cho biết rate có kiểu số thực. 17
Chƣơng 1. Tổng quan về chƣơng trình dịch - Câu lệnh gán cho biết vế phải của nó là kết quả của phép nhân một số thực rate với một số nguyên rồi cộng với một số nguyên; vậy nó phải có kiểu thực. Cho nên position phải có kiểu thực. Tuy nhiên khi so sánh lại thì mâu thuẫn. Vì vậy, chƣơng trình dịch sẽ báo lỗi sai kiểu dữ liệu. Nhƣng nếu trong khai báo: Var position, initial, Rate: real; Các tên biến đƣợc khai báo là real, 60 là số integer vì vậy chƣơng trình dịch sẽ ép chuyển đổi số nguyên 60 thành số thực 60.0. Phân tích ngữ nghĩa phải dựa vào các luật ngữ nghĩa đi kèm với từng luật cú pháp để thực hiện chức năng sinh thuộc tính cho các thẻ từ (token) và kiểm tra lỗi ngữ nghĩa. 1.4. Các giai đoạn của chƣơng trình dịch Để dễ hình dung, một chƣơng trình dịch đƣợc chia thành các giai đoạn, mỗi giai đoạn chuyển chƣơng trình nguồn từ một dạng biểu diễn này sang một dạng biểu diễn khác. Một cách phân rã điển hình chƣơng trình dịch đƣợc trình bày trong hình sau: Chƣơng trình nguồn Phân tích từ vựng Phân tích cú pháp Phân tích ngữ nghĩa Quản lý bảng ký Xử lý lỗi hiệu Sinh mã trung gian Tối ƣu mã Sinh mã đích Chƣơng trình đích Hình 1.7. Sơ đồ cấu trúc của một chương trình dịch 18
Chƣơng 1. Tổng quan về chƣơng trình dịch Việc quản lý bảng ký hiệu và xử lý lỗi đƣợc thực hiện xuyên suốt qua tất cả các giai đoạn. 1.4.1. Quản lý bảng ký hiệu Một nhiệm vụ quan trọng của chƣơng trình dịch là ghi lại các định danh (tên hay danh biểu) đƣợc sử dụng trong chƣơng trình nguồn và thu thập các thông tin về các thuộc tính khác nhau của mỗi định danh. Những thuộc tính này có thể cung cấp thông tin về vị trí lƣu trữ đƣợc cấp phát cho một định danh, kiểu và tầm hoạt động của định danh, và nếu định danh là tên của một thủ tục hoặc hàm thì thuộc tính là các thông tin về số lƣợng và kiểu của các đối số, phƣơng pháp truyền đối số và kiểu trả về của thủ tục hoặc hàm nếu có. Bảng ký hiệu (symbol table) là một cấu trúc dữ liệu mà mỗi phần tử là một bản ghi dùng để lƣu trữ một định danh, bao gồm các trƣờng lƣu giữ ký hiệu và các thuộc tính của nó. Cấu trúc này cho phép tìm kiếm, truy xuất các định danh (tên hay danh biểu) một cách nhanh chóng. Trong quá trình phân tích từ vựng, định danh (tên hay danh biểu ) đƣợc tìm thấy và nó đƣợc đƣa vào bảng ký hiệu nhƣng nói chung các thuộc tính của nó có thể chƣa xác định đƣợc trong giai đoạn này mà nó đƣợc bổ sung dần trong các giai đoạn phân tích cú pháp và phân tích ngữ nghĩa. 1 position 2 initial 3 rate 4 1.4.2. Xử lý lỗi Mỗi giai đoạn có thể gặp nhiều lỗi, tuy nhiên sau khi phát hiện ra lỗi, tùy thuộc vào chƣơng trình dịch mà có các cách xử lý lỗi khác nhau, chẳng hạn: - Dừng và thông báo lỗi khi gặp lỗi đầu tiên (Turbo Pascal). - Ghi nhận lỗi và tiếp tục quá trình dịch (Turbo C). Giai đoạn phân tích từ vựng thƣờng gặp lỗi khi các ký tự không thể ghép thành một token. Giai đoạn phân tích cú pháp gặp lỗi khi các token không thể kết hợp với nhau theo đúng cấu trúc cú pháp của ngôn ngữ. Giai đoạn phân tích ngữ nghĩa báo lỗi khi các toán hạng có kiểu không đúng, sử dụng tên trùng nhau, yêu cầu của phép toán hay các cấu trúc không có nghĩa đối với thao tác thực hiện mặc dù chúng hoàn toàn đúng về mặt cú pháp. 19
Chƣơng 1. Tổng quan về chƣơng trình dịch 1.4.3. Các giai đoạn phân tích Giai đoạn phân tích từ vựng: đọc từng ký tự rồi gộp lại thành các từ vị (lexeme), sau đó kiểm tra các mẫu để tìm ra các thẻ từ (token) tƣơng ứng, token có thể là tên( định danh hay danh biểu), từ khóa, phép toán, Chuỗi ký tự tạo thành một thỏa mãn mẫu của một token gọi là lexeme - trị từ vựng (từ vị) của token đó. Ví dụ 1.6: Từ vị rate là một tên có token là tên (id), trị từ vựng (từ vị) là rate và tên này sẽ đƣợc đƣa vào bảng ký hiệu nếu nó chƣa có trong đó. Giai đoạn phân tích cú pháp và phân tích ngữ nghĩa: Xây dựng cấu trúc phân cấp cho chuỗi các token, biểu diễn bởi cây cú pháp và kiểm tra ngôn ngữ theo cú pháp. 1.4.4. Sinh mã trung gian Sau khi phân tích ngữ nghĩa, một số chƣơng trình dịch sẽ tạo ra một dạng biểu diễn trung gian của chƣơng trình nguồn. Có thể xem dạng biểu diễn này nhƣ một chƣơng trình dành cho một máy trừu tƣợng. Chúng có 2 đặc tính quan trọng: dễ sinh và dễ dịch thành chƣơng trình đích. Dạng biểu diễn trung gian có rất nhiều loại. Thông thƣờng, ngƣời ta sử dụng dạng "mã máy 3 địa chỉ" (three-address code), tƣơng tự nhƣ dạng hợp ngữ cho một máy mà trong đó mỗi vị trí bộ nhớ có thể đóng vai trò nhƣ một thanh ghi. Mã máy 3 địa chỉ là một dãy các lệnh liên tiếp, mỗi lệnh có thể có tối đa 3 đối số. Ví dụ 1.7: Trong ví dụ trên, sau các giai đoạn phân tích thì mã trung gian sẽ đƣợc tạo ra nhƣ sau: t1:= inttoreal (60) t2:= id3 * t1 t3:= id2 + t2 id1:= t3 (Trong đó id1 là position; id2 là initial; id3 là rate ) Dạng trung gian này có một số tính chất: - Mỗi lệnh chỉ chứa nhiều nhất một toán tử. Do đó khi tạo ra lệnh này, chƣơng trình dịch phải xác định thứ tự các phép toán, ví dụ * thực hiện trƣớc +. - Chƣơng trình dịch phải tạo ra một biến tạm để lƣu trữ giá trị tính toán cho mỗi lệnh. - Một số lệnh có ít hơn 3 toán hạng. 20
Chƣơng 1. Tổng quan về chƣơng trình dịch 1.4.5. Tối ƣu mã Giai đoạn tối ƣu mã cố gắng cải thiện mã trung gian để có thể có mã máy thực hiện nhanh hơn. Một số phƣơng pháp tối ƣu hóa hoàn toàn bình thƣờng. Ví dụ 1.8: Mã trung gian nêu trên có thể tối ƣu thành: t1:= id3 * 60.0 id1:= id2 + t1 Để tối ƣu mã, ta thấy việc đổi số nguyên 60 thành số thực 60.0 có thể thực hiện một lần vào lúc biên dịch, vì vậy có thể loại bỏ phép toán inttoreal. Ngoài ra, t3 chỉ đƣợc dùng một lần để chuyển giá trị cho id1 nên có thể giảm bớt Có một khác biệt rất lớn giữa khối lƣợng tối ƣu hoá mã đƣợc các chƣơng trình dịch khác nhau thực hiện. Trong những chƣơng trình dịch gọi là "chƣơng trình dịch chuyên tối ƣu", một phần thời gian đáng kể đƣợc dành cho giai đoạn này. Tuy nhiên, cũng có những phƣơng pháp tối ƣu giúp giảm đáng kể thời gian chạy của chƣơng trình nguồn mà không làm chậm đi thời gian dịch quá nhiều. 1.4.6. Sinh mã đích Giai đoạn cuối cùng của biên dịch là sinh mã đích, thƣờng là mã máy hoặc mã hợp ngữ (Assembly). Các vị trí vùng nhớ đƣợc chọn lựa cho mỗi biến đƣợc chƣơng trình sử dụng. Sau đó, các chỉ thị trung gian đƣợc dịch lần lƣợt thành chuỗi các chỉ thị mã máy. Vấn đề quyết định là việc gán các biến cho các thanh ghi. Ví dụ 1.9: Sử dụng các thanh ghi (chẳng hạn R1, R2) cho việc sinh mã đích nhƣ sau: MOV id3, R2 MUL #60.0, R2 MOV id2, R1 ADD R2, R1 MOV R1, id1 Toán hạng thứ nhất và thứ hai của mỗi chỉ thị tƣơng ứng mô tả đối tƣợng nguồn và đích. Dấu # để xác định số 60.0 xem nhƣ một hằng số. 1.5. Nhóm các giai đoạn Các giai đoạn đã đề cập ở trên là thực hiện theo trình tự logic của một chƣơng trình dịch. Nhƣng trong thực tế, cài đặt các hoạt động của nhiều hơn một giai đoạn có thể đƣợc nhóm lại với nhau. Thông thƣờng chúng đƣợc nhóm thành hai nhóm cơ bản và đƣợc gọi là: kỳ đầu (Front end) và kỳ sau (Back end). 21
Chƣơng 1. Tổng quan về chƣơng trình dịch 1.5.1. Kỳ đầu (Front End) Kỳ đầu bao gồm các giai đoạn hoặc các phần giai đoạn phụ thuộc nhiều vào ngôn ngữ nguồn và hầu nhƣ độc lập với ngôn ngữ đích. Thông thƣờng, nó chứa các giai đoạn: Phân tích từ vựng, Phân tích cú pháp, Phân tích ngữ nghĩa và Sinh mã trung gian. Một phần của công việc tối ƣu hóa mã cũng đƣợc thực hiện ở kỳ đầu. Kỳ đầu cũng bao gồm cả việc xử lý lỗi xuất hiện trong từng giai đoạn. 1.5.2. Kỳ sau (Back End) Kỳ sau bao gồm một số phần nào đó của chƣơng trình dịch phụ thuộc vào ngôn ngữ đích và nói chung các phần này không phụ thuộc vào ngôn ngữ nguồn mà là ngôn ngữ trung gian. Trong kỳ sau, sẽ gặp một số vấn đề nhƣ: tối ƣu hoá mã, phát sinh mã đích cùng với việc xử lý lỗi và các thao tác trên bảng ký hiệu. 1.6. Các đặc trƣng của ngôn ngữ lập trình bậc cao 1.6.1. Từ vựng Cũng nhƣ ngôn ngữ tự nhiên, từ vựng của ngôn ngữ lập trình bậc cao đƣợc xây dựng trên bảng chữ cái gồm có: - Chữ cái: A . . Z, a z; - Chữ số: 0 9; - Các ký hiệu toán học: +, -, *, /, =, , (, ), %, - Các ký hiệu khác: [, ], {, }, - Dấu cách (khoảng trống). Các từ vựng của ngôn ngữ lập trình bậc cao đƣợc hiểu bao gồm: Các từ khoá, các tên (hằng, biến, chƣơng trình, chƣơng trình con, kiểu dữ liệu), các kiểu dữ liệu, các phép toán số học, các phép toán quan hệ, phép gán, các dấu, Các từ vựng này có các quy định chặt chẽ về mặt ngữ pháp. Chẳng hạn nhƣ tên thì bắt đầu bằng một chữ cái, sau đó là không, một hoặc nhiều các chữ cái hoặc chữ số; phép gán trong ngôn ngữ C hoặc Foxpro là „=‟ còn trong ngôn ngữ Pascal là „:=‟, Các từ vựng đƣợc phân ta thành từng loại. Mỗi loại đƣợc đặt bởi một tên và gọi là một thẻ từ (token). Mỗi loại có cấu trúc ngữ pháp riêng, quy định cách thức xác định ra các từ của nó và đƣợc gọi là mẫu từ vựng (pattern). Mỗi từ vựng của mỗi loại gọi là trị từ vựng hay từ vị (lexeme). Để xây dựng một chƣơng trình dịch thì phải tìm hiểu tập từ vựng của ngôn ngữ nguồn tức là tìm hiểu tập các thẻ từ và mẫu của các thẻ từ đó và phân tích để biết đƣợc từng loại từ vựng và thuộc tính của nó. Nhiệm vụ này thuộc mô đun phân tích từ vựng. 22
Chƣơng 1. Tổng quan về chƣơng trình dịch 1.6.2. Cú pháp Cú pháp là thành phần quan trọng nhất trong một ngôn ngữ. Ngôn ngữ đƣợc sinh ra bởi một văn phạm gồm tập hợp các từ vựng thỏa mãn các luật sinh ra các từ vựng đó. Các từ vựng ghép lại thành câu, câu phải thoả mãn các luật sinh ra câu của văn phạm của ngôn ngữ đó. Các luật đó gọi là cú pháp của văn phạm. Trong ngôn ngữ lập trình bậc cao, cú pháp của nó đƣợc thể hiện bởi một bộ luật cú pháp. Bộ luật này dùng để mô tả cấu trúc của một chƣơng trình, các câu lệnh, Các cấu trúc cần quan tâm đến bao gồm: - Các khai báo (khai báo chƣơng trình, khai báo chƣơng trình con, khai báo hằng, khai báo biến, khai báo kiểu dữ kiệu); - Các biểu thức số học, biểu thức quan hệ, biểu thức logic; - Các câu lệnh: lệnh gán, lệnh gọi chƣơng trình con, lệnh vào, ra dữ liệu, các câu lệnh điều kiện, các câu lệnh lặp; - Chƣơng trình, chƣơng trình con. Nhiệm vụ trƣớc tiên là phải biết đƣợc bộ luật cú pháp của ngôn ngữ định xây dựng chƣơng trình dịch cho nó. Chƣơng trình phải phân tích chƣơng trình nguồn thành các cấu trúc cú pháp của ngôn ngữ; từ đó, kiểm tra tính đúng đắn về mặt cú pháp của chƣơng trình nguồn. Công việc này thuộc về mô đun phân tích cú pháp. 1.6.3. Ngữ nghĩa Kiểm tra ngữ nghĩa của chƣơng trình nguồn là một phần của chƣơng trình dịch trong giai đoạn phân tích ngữ nghĩa. Ngữ nghĩa của ngôn ngữ lập trình liên quan đến: - Kiểu, phạm vi của hằng, biến, hàm biểu thức; - Phân biệt và sử dụng đúng tên (tên hằng, tên biến, tên chƣơng trình , tên chƣơng trình con, tên kiểu dữ liệu, ). Chƣơng trình dịch phải kiểm tra đƣợc tính đúng đắn trong việc sử dụng các đại lƣợng này. Chẳng hạn kiểm tra chỉ cho gán giá trị cho biến, kiểm tra tính đúng đắn trong gán kiểu, kiểm tra phạm vi của hằng, biến, hàm; kiểm tra việc sử dụng tên trùng nhau. Công việc này thuộc về mô đun phân tích ngữ nghĩa. 23
Chƣơng 1. Tổng quan về chƣơng trình dịch CÂU HỎI VÀ BÀI TẬP CHƢƠNG 1 1.1. Nêu các khái niệm: chƣơng trình dịch, chƣơng trình thông dịch (interpreter), chƣơng trình biên dịch (compiler); mỗi khái niệm hãy cho một ví dụ. 1.2. Nêu các khái niệm: thẻ từ (token), từ vị (lexeme), mẫu từ vựng (pattern); cho ví dụ minh họa. 1.3. Nêu môi trƣờng của một chƣơng trình dịch. Trình bày sơ đồ cấu trúc môi trƣờng của một trình biên dịch. 1.4. Nêu các giai đoạn phân tích chƣơng trình nguồn và chức năng, nhiệm vụ của nó. 1.5. Trình bày sơ đồ cấu trúc của một chƣơng trình dịch. 1.6. Nêu các nhóm giai đoạn của một trình biên dịch; chức năng, nhiệm vụ của mỗi giai đoạn. 1.7. Nêu các đặc trƣng của ngôn ngữ lập trình bậc cao. 1.8. Chƣơng trình dịch của mỗi ngôn ngữ lập trình bậc cao sau sử dụng hệ thống thông dịch hay biên dịch. Nêu phƣơng pháp ghi nhận lại các lỗi có trong chƣơng trình nguồn để thông báo lại cho ngƣời viết chƣơng trình của chƣơng trình dịch đó: - Pascal; - C. 1.9. Các số không dấu trong Pascal là các chuỗi 5280, 39.37, 6.336E4 hoặc 1.894E-4. Ðịnh nghĩa chính quy sau mô tả tập các số này là : digit 0 | 1 | | 9; * digits digit(digit) ; optional_fraction . digits | ε; optional_exponent ( E ( + | - | ε ) digits) | ε; num digits optional_fraction optional_exponent. Hãy chỉ rõ các thẻ từ (token), mẫu từ vựng (pattern), từ vị (lexeme) trong ngôn ngữ trên. 1.10. Hãy chỉ ra một số thẻ từ (token); mẫu từ vựng (pattern) thƣờng gặp và một số trị từ vựng tƣơng ứng của nó trong mỗi ngôn ngữ lập trình bậc cao: Pascal, C. 24
Chƣơng 2. Phân tích từ vựng Chƣơng 2 PHÂN TÍCH TỪ VỰNG Mục tiêu: Giúp sinh viên có khả năng: - Củng cố đƣợc một số kiến thức về văn phạm, ngôn ngữ và automat. - Hiểu đƣợc các khái niệm: thẻ từ, mẫu từ vựng, trị từ vựng. Biểu diễn và nhận biết đƣợc các thẻ từ. - Biết đƣợc vị trí, nhiệm vụ của giai đoạn phân tích từ vựng. - Hiểu đƣợc kỹ thuật đọc chƣơng trình nguồn. - Chuyển đƣợc automat hữu hạn không đơn định về automat hữu hạn đơn định. - Xây đựng đƣợc automat hữu hạn không đơn định đoán nhận một biểu thức chính quy. - Nhận biết đƣợc từ vị bằng automat hữu hạn. Nội dung chính: - Nhắc lại một số kiến thức về văn phạm – ngôn ngữ - Automat. - Thẻ từ, mẫu từ vựng và trị từ vựng (từ vị). - Giai đoạn phân tích từ vựng. - Kỹ thuật đọc chƣơng trình nguồn. - Kỹ thuật sử dụng Automat để phân tích từ vựng. 2.1. Nhắc lại một số kiến thức về văn phạm – ngôn ngữ - Automat 2.1.1. Một số khái niệm cơ sở - Bảng chữ cái (bộ chữ cái) là một tập hợp hữu hạn, khác rỗng các phần tử, ký hiệu là . Các phần tử của một bảng chữ cái  đƣợc gọi là các chữ cái hoặc các ký tự (character) hay ký hiệu (symbol). - Xâu (string) hay từ (word) trên một bảng chữ cái  là một dãy hữu hạn gồm một số lớn hơn hay bằng không các ký tự của bảng chữ cái đó; Trong đó, một ký tự có thể xuất hiện nhiều lần. - Xâu rỗng là xâu không có chữ cái nào, độ dài của xâu rỗng bằng không. Xâu rỗng đƣợc ký hiệu là  hoặc e . Ví dụ 2.1: + Tập hợp các chữ cái La tinh {a, b, c, , A, B, , Z } là một bảng chữ cái và a, b, , A, là các chữ cái hay các ký tự. +  = {0, 1} là một bảng chữ cái nhị phân. 0, 1 là các chữ cái của bảng chữ cái . + Aaab, bbbbb là các từ trên bảng chữ cái La Tinh. 25
Chƣơng 2. Phân tích từ vựng + , 0, 1, 00101, 000011 là các từ trên bảng chữ cái nhị phân  = {0, 1}. - Xâu con của xâu w là xâu x  đƣợc tạo từ các ký tự nằm liền kề nhau trong xâu w. - Tiền tố của xâu w là một xâu con bất kỳ nằm ở đầu xâu w. - Hậu tố của xâu w là một xâu con bất kỳ nằm ở cuối xâu w. - Ngôn ngữ: Cho  là một bảng chữ cái. + * là tập hợp tất cả các xâu trên  kể cả xâu rỗng. + + là tập hợp tất cả các xâu trên  trừ xâu rỗng. + Tập con bất kỳ của tập hợp * đƣợc gọi là ngôn ngữ trên bảng chữ cái . Ví dụ 2.2: Cho bảng chữ cái nhị phân  = {0, 1} thì: + * = {, 0, 1, 00, 01, 10, 11, }. + + = {0, 1, 00, 01, 10, 11, }. +  , + , * , {}, {0}, {1}, {, 0, 1}, { 1, 00, 01, 10}, {0, 1, 00, 01, 10, 11, 0001}, là các ngôn ngữ trên bảng chữ cái  . Và w = 001 là một từ trên bảng chữ cái  thì: + 0, 1, 00, 01, 011 là các xâu con của xâu w. + 0, 00, 001 là các tiền tố của xâu w. + 1, 01, 001 là các hậu tố của xâu w. 2.1.2. Biểu diễn ngôn ngữ - Liệt kê: + Liệt kê hết: Đối với một ngôn ngữ hữu hạn, số lƣợng xâu của nó có ít, để biểu diễn nó, một cách đơn giản, ta chỉ cần liệt kê tất cả các xâu thuộc vào ngôn ngữ đó. Ví dụ 2.3: L1 = {ε}; L2 = { a, ba, aaba, bbbbb}. + Liệt kê không hết: Đối với một ngôn ngữ, số lƣợng xâu của nó có nhiều, các xâu thƣờng tuân theo một quy luật; để biểu diễn nó, một cách đơn giản, ta chỉ cần liệt kê một số xâu và ám chỉ cách xác định các xâu khác thuộc vào ngôn ngữ đó. Ví dụ 2.4: L1 = {ε, a, aa, aaa, }; L2 = { ab, aabb, aaabbb, aaaabbbb, }. - Chỉ ra tính chất đặc trƣng: Trong trƣờng hợp một ngôn ngữ là vô hạn, ta không thể liệt kê đƣợc tất cả các xâu thuộc vào ngôn ngữ đó. Trong những trƣờng 26
Chƣơng 2. Phân tích từ vựng hợp không phức tạp lắm, ngƣời ta thƣờng phải tìm ra tính chất đặc trƣng chung của các xâu và xác định các xâu bằng cách chỉ rõ tính chất đặc trƣng của các xâu đó. Tính chất đặc trƣng này thƣờng đƣợc mô tả thông qua một vị từ. Ví dụ 2.5: i L3 = { a | i là một số nguyên tố }; i j L4 = { a b | i ≥ j ≥ 0 }. - Trong phần lớn các trƣờng hợp, ngƣời ta thƣờng biểu diễn ngôn ngữ một cách tổng quát thông qua một văn phạm hoặc một automat. Văn phạm là cơ chế hay công cụ cho phép sản sinh ra mọi xâu của một ngôn ngữ; trong khi đó automat lại là cơ chế hay công cụ cho phép đoán nhận một xâu bất kỳ có thuộc ngôn ngữ hay không. Về mặt hình thức, cả văn phạm và automat đều là cách biểu diễn khác nhau của cùng một quan niệm. 2.1.3. Văn phạm 1) Định nghĩa Văn phạm là một hệ thống gồm bốn thành phần G = (N, T, P, S) trong đó: N – Là một tập hữu hạn các ký hiệu không kết thúc (Nonterminal) hay tập các biến (variables). T – Là tập hữu hạn các ký hiệu kết thúc hay ký hiệu cuối (Terminal) với N T = . P – Là tập hữu hạn các quy tắc sinh hay còn đƣợc gọi là luật sinh. P: (N  T)+ → (N  T)* α β S N - là ký hiệu chƣa kết thúc đặc biệt dùng làm ký hiệu bắt đầu (start) 2) Phân loại Chomsky dựa vào các luật sinh đã phân văn phạm thành bốn loại: - Văn phạm loại 0 (văn phạm ngữ cấu – Phrase Grammar) là văn phạm mà các luật sinh của nó không có bất kỳ một điều kiện ràng buộc nào hay nói cách khác các luật sinh của nó có dạng: α β với α (N  T)+; β (N  T)* - Văn phạm loại 1 (phạm cảm ngữ cảnh - Context Sensitive Grammar) là văn phạm mà các luật sinh của nó có dạng: α β với α (N  T)+; β (N  T)* và    - Văn phạm loại 2 (văn phạm phi ngữ cảnh - Context free Grammar) là văn phạm mà các luật sinh của nó có dạng: A α với A N; α (NT)* - Văn phạm loại 3 (văn phạm chính quy - Regular Grammar) là văn phạm mà các luật sinh của nó có một trong hai dạng: 27
Chƣơng 2. Phân tích từ vựng 1. A Ba hoặc A a (văn phạm tuyến tính trái); 2. A aB hoặc A a (văn phạm tuyến tính phải). Với điều kiện A, B N; a T. 2.1.4. Văn phạm phi ngữ cảnh Ðể xây dựng cú pháp của một ngôn ngữ lập trình bậc cao, ngƣời ta dùng văn phạm phi ngữ cảnh CFG (Context Free Grammar) hay còn gọi là văn phạm BNF (Backus Naur Form). Văn phạm này bao gồm bốn thành phần: 1. Một bảng chữ cái - Tập hợp các ký hiệu kết thúc (terminal symbols). 2. Một tập hợp các ký hiệu chƣa kết thúc (nonterminal symbols), còn gọi là các biến (variables). 3. Một tập hợp các luật sinh (productions) trong đó mỗi luật sinh bao gồm một ký hiệu chƣa kết thúc - gọi là vế trái, một mũi tên và một chuỗi các token và hoặc các ký hiệu chƣa kết thúc, kết thúc gọi là vế phải. 4. Một trong các ký hiệu chƣa kết thúc đặc biệt đƣợc dùng làm ký hiệu bắt đầu của văn phạm. Quy ƣớc: - Mô tả văn phạm bằng cách liệt kê các luật sinh. - Luật sinh chứa ký hiệu bắt đầu sẽ đƣợc liệt kê đầu tiên. - Nếu có nhiều luật sinh có cùng vế trái thì nhóm lại thành một luật sinh duy nhất, trong đó các vế phải cách nhau bởi ký hiệu “|” và đọc là “hoặc”. Ví dụ 2.6: Nếu xem biểu thức là một danh sách của các số phân biệt nhau bởi dấu + và dấu thì văn phạm với các luật sinh sau sẽ xác định cú pháp của biểu thức. list → list + digit; list → list – digit; list → digit; digit → 0 | 1 | 2 | | 9 và ta có thể nhóm lại thành các luật sinh: list → list + digit | list - digit | digit ; digit → 0 | 1 | 2 | 9 Nhƣ vậy văn phạm phi ngữ cảnh ở đây là: - Tập hợp các ký hiệu kết thúc: 0, 1, 2, , 9, +, - - Tập hợp các ký hiệu chƣa kết thúc: list, digit. - Các luật sinh: 28
Chƣơng 2. Phân tích từ vựng list → list + digit | list - digit | digit ; digit → 0 | 1 | 2 | 9 - Ký hiệu chƣa kết thúc bắt đầu: list. 2.1.5. Biểu thức chính quy (Regular Expression) Văn phạm chính quy đơn giản và đủ dùng cho biểu diễn và phân tích từ vựng. Ngoài cách biểu diễn bằng các luật sinh, văn phạm chính quy còn có cách biểu diễn tƣơng đƣơng bằng biểu thức chính quy. Chẳng hạn có thể viết: id = (letter | _ ) (letter | digit | _ )* hoặc id letter (letter | digit)*; (letter | _ ) (letter | digit | _ )* là một biểu thức chính quy. Biểu thức chính quy đƣợc xây dựng trên một tập hợp các quy tắc xác định. Mỗi biểu thức chính quy r đặc tả một ngôn ngữ L(r). Sau đây là các quy tắc xác định biểu thức chính quy trên bảng chữ cái Σ. 1. ε là một biểu thức chính quy đặc tả cho một chuỗi rỗng {ε }. 2. Nếu a Σ thì a là biểu thức chính quy r đặc tả tập hợp các chuỗi {a} 3. Giả sử r và s là các biểu thức chính quy đặc tả các ngôn ngữ L(r) và L(s) ta có: a. (r) | (s) là một biểu thức chính quy đặc tả L(r)  L(s) b. (r) (s) là một biểu thức chính quy đặc tả L(r)L(s). c. (r)* là một biểu thức chính quy đặc tả (L(r))* d. (r)+ là một biểu thức chính quy đặc tả (L(r))+ Quy ước: Toán tử bao đóng *, + có độ ƣu tiên cao nhất và kết hợp trái. Toán tử ghép có độ ƣu tiên thứ hai và kết hợp trái. Toán tử hợp | có độ ƣu tiên thấp nhất và kết hợp trái. Ví dụ 2.7: Cho bảng chữ cái Σ = {a, b}. 1. Biểu thức chính quy a | b đặc tả {a, b} 2. Biểu thức chính quy (a | b) (a | b) đặc tả tập hợp {aa, ab, ba, bb}. Tập hợp này có thể đƣợc đặc tả bởi biểu thức chính quy tƣơng đƣơng sau: aa | ab | ba | bb. 3. Biểu thức chính quy a* đặc tả { ε, a, aa, aaa, } 4. Biểu thức chính quy (a | b)* đặc tả {(, a, b, aa,bb, }. Tập này có thể đặc tả bởi (a*b* )*. 5. Biểu thức chính quy a | a* b đặc tả {a, b, ab, aab, } 29
Chƣơng 2. Phân tích từ vựng Hai biểu thức chính quy r và s cùng đặc tả một tập hợp thì ta nói rằng chúng tƣơng đƣơng và viết là r = s. 30
Chƣơng 2. Phân tích từ vựng 2.1.6. Automat hữu hạn đơn định 1) Định nghĩa Automat hữu hạn đơn định là một hệ thống gồm 5 thành phần; ký hiệu là M = , trong đó: Q - Tập hữu hạn khác rỗng các trạng thái.  - Tập hữu hạn khác rỗng các ký hiệu vào (gọi tắt là bảng chữ cái vào).  - Ánh xạ còn gọi là hàm chuyển trạng thái có dạng: : Q  Q (q, a) p q0 - Là trạng thái bắt đầu; q0 Q. F - Tập con của Q ( F  Q) là tập các trạng thái kết thúc. 2) Hàm chuyển trạng thái mở rộng 1. δ*(q, ε) = q 2. δ*(q, wa) = δ(δ*(q, w), a); với q Q; w Σ* và a Σ. = δ(δ( δ(q, a) )) * δ (q, a1a2 an-1an) = δ(δ( (δ(δ(q, a1),a2), ),an-1), an) 3) Ngôn ngữ đoán nhận bởi automat hữu hạn đơn định * * L(M) = w   (q0,w) = q F 2.1.7. Automat hữu hạn không đơn định - NFA (Nondeterministic Finite Automata)  1) Định nghĩa Automat hữu hạn không đơn định là một hệ thống gồm 5 thành phần, ký hiệu là M = trong đó: Q - Tập hữu hạn khác rỗng các trạng thái.  - Tập hữu hạn khác rỗng các ký hiệu vào (gọi tắt là bảng chữ cái vào).  - Ánh xạ còn gọi là hàm chuyển trạng thái có dạng: : Q  2Q (q, a) p q0 - Là trạng thái bắt đầu; q0 Q. 31
Chƣơng 2. Phân tích từ vựng F - Tập con của Q là tập các trạng thái kết thúc. 2) Hàm chuyển trạng thái mở rộng 1. δ*(q, ε) = {q} ; 2. δ*(q, wa) = δ(δ*(q, w), a) với q Q; w Σ* và a Σ * δ (q, a1a2 an-1an) = δ(δ( (δ(δ(q, a1),a2), ),an-1), an) 3. - δ(T, a) =  δ(q, a) với  T  Q. q T - δ*(T, a) =  δ*(q, a) với  T  Q. q T 3) Ngôn ngữ đoán nhận bởi automat không đơn định * * N(M) = w   (q0,w) = q  F  Hay N(M) = {w * | δ*(q , w) có chứa một trạng thái trong F } 0 2.1.8. Automat hữu hạn không đơn định với ε-dịch chuyển (NFAε) 1) Định nghĩa Automat hữu hạn không đơn định với ε-dịch chuyển (NFA với ε-dịch chuyển) là một hệ thống gồm 5 thành phần; ký hiệu là M = trong đó: Q - Tập hữu hạn khác rỗng các trạng thái.  - Tập hữu hạn khác rỗng các ký hiệu vào (gọi tắt là bảng chữ cái vào).  - Ánh xạ còn gọi là hàm chuyển trạng thái có dạng: : Q (  {}) 2Q (q, a) p q0 - Là trạng thái bắt đầu; q0 Q. F - Tập con của Q là tập các trạng thái kết thúc. 2) Hàm chuyển trạng thái mở rộng a) Hàm -CLOSURE 1. -CLOSURE(q) là tập hợp các trạng thái p sao cho có đƣờng đi từ trạng thái q tới p khi M nhận vào từ rỗng  (gồm không, một hoặc nhiều cung mang nhãn ). 2. ε-CLOSURE(T) =  ε-CLOSURE(q) với q Q ; T Q q T Chú ý: ε-CLOSURE() =  Ví dụ 2.8: 32
Chƣơng 2. Phân tích từ vựng Cho Automat đƣợc biểu diễn bằng đồ thị hình 2.1. Tính: ε-CLOSURE(0). ε-CLOSURE(0) = {0, 1, 6, 2, 4, 7, 8}  2 a 3   Start   a 6  b 0 1  7 8 9 10  4 b 5  Hình 2.1. NFA với ε - dịch chuyển b) Hàm chuyển trạng thái mở rộng 1. δ*(q, ε) = ε-CLOSURE(q) 2. δ*(q, wa) = ε-CLOSURE(δ(δ*(q, w), a) Suy ra: a. δ*(q, a) = ε-CLOSURE(δ(δ*(q, ε), a) = ε-CLOSURE(δ(ε-CLOSURE(q), a)) * b. δ (q, a1a2 an-1an) = = ε-CLOSURE(δ(ε-CLOSURE(δ( ε-CLOSURE(δ(ε-CLOSURE(q), a1)), a2) ),an)) 3. - δ (T, a) =  δ(q, a) q T - δ* (T, a) =  δ*(q, a) q T Ví dụ 2.9: Cho Automat đƣợc biểu diễn bằng đồ thị hình 2.1. Tính: δ*(0, a). δ*(0, a) = ε-CLOSURE(δ(ε-CLOSURE(0), a)) - ε-CLOSURE(0) = {0, 1, 6, 2, 4, 7, 8} - δ(ε-CLOSURE(0), a) = δ(ε-CLOSURE(0), a) = δ({0, 1, 6, 2, 4, 7, 8}, a) = δ(0, a) δ(1, a) δ(6, a)  δ(2, a) δ(4, a) δ(7, a) δ(8, a) =       {3}      {9} ={3, 9} δ*(0, a) = ε-CLOSURE(δ(ε-CLOSURE(0), a)) 33
Chƣơng 2. Phân tích từ vựng = ε-CLOSURE({3, 9}) = ε-CLOSURE(3)  ε-CLOSURE(9) = {3, 6, 1, 2, 4, 7, 8}{9} = {1, 2, 3, 4, 6, 7, 8, 9} 3) Ngôn ngữ được đoán nhận bởi NFAε L(M) = {w | δ*(q , w) F } 0 2.2. Giai đoạn phân tích từ vựng Có thể kết hợp xen kẽ giữa quá trình phân tích từ vựng và phân tích cú pháp. Tuy nhiên, có thể tách riêng giai đoạn phân tích từ vựng với giai đoạn phân tích cú pháp vì các lý do sau: - Làm cho việc thiết kế và viết chƣơng trình dịch đơn giản hơn. - Làm cho giai đoạn phân tích từ vựng làm việc hiệu quả hơn, chuyên dùng hơn và rất có thể nó đƣợc dùng lại cho các ngôn ngữ nguồn khác. - Nó phù hợp với kỹ thuật lập trình theo hƣớng Modul hoá. Vị trí, chức năng, nhiệm vụ của giai đoạn phân tích từ vựng Giai đoạn phân tích từ vựng là giai đoạn đầu tiên của một quá trình dịch. Chức năng của giai đoạn phân tích từ vựng là phân tích chƣơng trình nguồn về mặt từ vựng: Phân tích chƣơng trình nguồn thành dãy các từ vị và thu chƣơng trình nguồn về dòng các thẻ từ. Nhiệm vụ chủ yếu của giai đoạn này là đọc vào chƣơng trình nguồn. Dựa vào các quy tắc sinh của văn phạm, bảng từ khoá, bảng các ký hiệu, phân tích để nhận ra các từ vị (lexeme) trong chƣơng trình nguồn và thay thế nó bằng các thẻ từ (token) tƣơng ứng. Nói một cách khác, nếu coi giai đoạn phân tích từ vựng ứng với bộ phân tích từ vựng trong chƣơng trình dịch thì đầu vào của bộ phân tích từ vựng là chƣơng trình nguồn; đầu ra của bộ phân tích từ vựng là dòng các thẻ từ (token). Giai đoạn phân tích từ vựng là giai đoạn duy nhất trong quá trình dịch phải dò đọc chƣơng trình nguồn. Vì vậy, một trong các yêu cầu chủ yếu đối với bộ phân tích từ vựng là phải đọc nhanh, phân tích nhanh chƣơng trình nguồn. Ngoài ra, nó còn đảm nhận thêm một số nhiệm vụ khác nhƣ: - Cắt bỏ các dấu cách thừa. - Bỏ qua các dòng chú thích của ngƣời lập trình. 34
Chƣơng 2. Phân tích từ vựng - Bỏ qua các dấu Tab, dấu xuống dòng. - Phát hiện lỗi các lỗi từ vựng và liên hệ với bộ xử lý lỗi để sửa hoặc báo lỗi. Hình 2.2 mô tả vị trí của giai đoạn phân tích từ vựng. Chƣơng Thẻ từ Cây phân tích trình nguồn Phân tích Phân tích (Parse tree) từ vựng cú pháp Yêu cầu thẻ từ mới Bảng kí hiệu Hình 2.2. Vị trí của giai đoạn phân tích từ vựng Ta có thể coi chƣơng trình nguồn là dãy các từ vị và quá trình phân tích từ vựng là quá trình dò đọc chƣơng trình nguồn, nhận biết các từ vị và thay thế chúng bởi các thẻ từ. Ví dụ 2.10: Trong ngôn ngữ lập trình Pascal, với câu lệnh: if a > b then max := a; thì sản phẩm chính của bộ PTTV là dãy thẻ từ sau: IF ID RELOP ID THEN ID ASSIGN ID SEMI 2.2.1. Thẻ từ, mẫu từ vựng và trị từ vựng (từ vị) 1) Khái niệm thẻ từ, mẫu từ vựng và trị từ vựng Khi nói đến bộ phân tích từ vựng, sẽ phải sử dụng các thuật ngữ thẻ từ (token), mẫu từ vựng (pattern) và trị từ vựng - từ vị (lexeme) với nghĩa cụ thể nhƣ sau: Thẻ từ (token) là dạng ngữ pháp của từ vị; hay nói một cách khác, thẻ từ là tập hợp xâu các ký tự kết thúc (từ vị) có chung nhau luật ngữ pháp sinh ra các từ vị đó và mỗi thẻ từ thƣờng đƣợc đặt bởi một tên để định danh (phân biệt các thẻ từ với nhau). Mỗi thẻ từ sẽ có một mẫu từ vựng (pattern) để xác định một từ vị là thuộc thẻ từ nào; hay nói cách khác, mẫu từ vựng của thẻ từ là luật ngữ pháp sinh ra các từ vị của thẻ từ đó. 35
Chƣơng 2. Phân tích từ vựng Trị từ vựng – từ vị (lexeme) của một thẻ từ là một xâu các ký tự kết thúc của thẻ từ và nó phải thỏa mãn mẫu từ vựng của thẻ từ đó. Nhờ vào thẻ từ, mẫu của thẻ từ, chƣơng trình dịch trong giai đoạn phân tích từ vựng sẽ phân tích chƣơng trình nguồn để xác định ra các trị từ vựng của các thẻ từ và trả về các thẻ từ cho giai đoạn phân tích cú pháp hoặc báo lỗi. Ví dụ 2.11: 1. digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Thì: + digit là thẻ từ (token); + 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 là mẫu từ vựng (pattern); + Mỗi chữ số: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 là một trị từ vựng – từ vị (lexeme) của thẻ từ digit. 2. letter A | B | | Z | a | b | | z Thì: + letter là tên của thẻ từ (token); + A | B | | Z | a | b | | z là mẫu từ vựng (pattern); + Mỗi chữ cái La tinh: A, B, C, , Z, a, b, c, , z là một trị từ vựng – từ vị (lexeme) của thẻ từ letter. * 3. id (letter | _ )(letter | digit | _ ) Thì: + id là tên thẻ từ (token); * + (letter | _ )(letter | digit | _ ) là mẫu từ vựng (pattern); + A, X1B, max_1a23 là 3 trị từ vựng – từ v (lexeme) của thẻ từ id. Xét câu lệnh của Pascal: If a = b then x := 0 else x := 1; Ta có thể tách nhỏ câu lệnh thành các phần tử nhỏ nhất (nguyên tử): Từ khoá if, khoảng trống, biến a, khoảng trống, dấu so sánh bằng (=), khoảng trống, biến b, từ khoá then, khoảng trống, biến x, khoảng trống, dấu gán (:=), 36
Chƣơng 2. Phân tích từ vựng khoảng trống, con số 0, dấu xuống hàng, từ khoá else, khoảng trống, biến x, khoảng trống, dấu gán (:=) khoảng trống, con số 1, dấu chấm phẩy (;), dấu xuống hàng. Mỗi phần tử nhỏ nhất (nguyên tử) không thể phân tách đƣợc nữa là một đơn vị từ vựng (lexical unit) hay trị từ vựng (từ vị) (lexeme). Ví dụ 2.12: Không thể tách chuỗi if thành i và f vì khi đó không còn tồn tại ý nghĩa của từ khóa if . Dấu gán (:=) không thể tách ra thành hai dấu là dấu hai chấm (:) và dấu so sánh bằng (=) vì làm nhƣ thế sẽ đánh mất ý nghĩa của nó và tạo ra dấu hai chấm (:) cạnh dấu so sánh bằng (=) vô nghĩa. Có thể nhóm một số trị từ vựng (từ vị) tuân theo một khuôn mẫu nào đó và có chức năng cú pháp giống nhau. Ví dụ 2.13: Các biến a, b và x có thể đƣợc nhóm lại vì chúng đều là tên của các đối tƣợng trong chƣơng trình (identifier) và tuân theo quy ƣớc đặt tên của ngôn ngữ đang xét. Tƣơng tự, các toán tử so sánh cũng thƣờng đƣợc nhóm lại. Các từ khóa if, then và else không đƣợc nhóm lại vì chức năng cú pháp của chúng không giống nhau. Mỗi nhóm trị từ vựng (từ vị) đƣợc biểu diễn bằng một thẻ từ (token); khuôn mẫu của nó đƣợc gọi là mẫu từ vựng (pattern). Thẻ từ (token) là một ký hiệu đại diện cho một loại trị từ vựng (từ vị), nghĩa là một tập các xâu ký tự có cùng chức năng cú pháp. Một số ký hiệu thẻ từ cơ bản: - Dùng ký hiệu ID làm thẻ từ cho các tên trong chƣơng trình. - Dùng ký hiệu RELOP làm thẻ từ cho các toán tử so sánh số học (=, , >=, <, <=). - Dùng ký hiệu IF làm thẻ từ cho từ khóa if, ký hiệu THEN cho từ khóa then, ký hiệu ELSE cho từ khóa else Các ngôn ngữ lập trình thƣờng chia các thẻ từ thành năm loại chính: - Từ khóa (keyword): IF, THEN, ELSE, - Tên (identifier): max, min, ab1, - Hằng (constant): 10, „Dai hoc SPKT Nam Dinh‟ 37
Chƣơng 2. Phân tích từ vựng - Toán tử (operator): +, -, *, /, >, , >, hoặc > >= hoặc >= id pi, count, d2 Mở đầu là chữ cái theo sau là chữ cái, chữ số number 3.1416, 0, 5, 230 Bất kỳ hằng số nào literal “ hello ” Mọi chữ cái nằm giữa “ và ” Bảng 2.1. Các ví dụ về token 2) Thuộc tính của thẻ từ (token) Khi có nhiều mẫu từ vựng khớp với một trị từ vựng (từ vị), bộ phân tích từ vựng trong trƣờng hợp này phải cung cấp thêm một số thông tin khác cho các bƣớc biên dịch sau đó. Do đó đối với mỗi token, bộ phân tích từ vựng sẽ đƣa thông tin về các token vào các thuộc tính đi kèm của chúng. Các token có ảnh hƣởng đến các quyết định phân tích cú pháp; các thuộc tính ảnh hƣởng đến việc phiên dịch các thẻ từ. Token kết hợp với thuộc tính của nó tạo thành một bộ . Ví dụ 2.14: Token và giá trị thuộc tính đi kèm của câu lệnh Pascal: E := M * C + 2 đƣợc viết nhƣ một dãy các bộ sau: 38
Chƣơng 2. Phân tích từ vựng Chú ý rằng một số bộ không cần giá trị thuộc tính, thành phần đầu tiên là đủ để nhận biết trị từ vựng. 3) Mô tả thẻ từ (token) Các thẻ từ (token) khác nhau có các mẫu khác nhau. Các mẫu này là cơ sở để nhận biết thẻ từ. Nhƣ vậy, cần thiết phải hình thức hoá các mẫu này để sao cho có thể lập trình đƣợc. Việc này có thể thực hiện đƣợc nhờ định nghĩa chính quy. a) Định nghĩa chính quy (Regular Definitions) Định nghĩa chính quy là một dãy các định có dạng: d1 r1 ; d2 r2 ; dn rn . Trong đó: di là một tên; ri là một biểu thức chính quy. Ví dụ 2.15: + relop  | >= | , >=, | >= | <> - Mô tả thẻ từ các tên (id): + letter A | B | | Z | a | b | | z ; 39
Chƣơng 2. Phân tích từ vựng + digit 0 | 1 | | 9 ; * + id (letter| _ ) (letter | digit | _ ) . 2.2.2. Nhận biết thẻ từ (token) a) Nhận biết bằng định nghĩa chính quy Trong phần này, ta sẽ sử dụng ngôn ngữ đƣợc tạo ra bởi văn phạm dƣới đây làm ví dụ minh họa: stmt if expr then stmt | if expr then stmt else stmt | ε expr term relop term | term term id | number Trong đó các ký hiệu kết thúc if, then, else, relop, id, number đƣợc cho bởi định nghĩa chính quy sau: if if ; then then; else else ; relop  | > | >= ; * id letter (letter | digit) ; digit 0 | 1 | | 9 ; * digits digit(digit) ; sign  + | - | ε ; optional_fraction . digits | ε ; number (sign)(digits)(optional_fraction) ; delim blank | tab | newline ; + ws delim . Mục đích là xây dựng một bộ phân tích từ vựng có thể xác định đƣợc từ vị (lexeme) cho các thẻ từ (token) và tạo ra một cặp thích hợp token và giá trị thuộc tính của nó bằng cách dùng mẫu (patten) - biểu thức chính quy cho các token nhƣ sau: 40
Chƣơng 2. Phân tích từ vựng Biểu thức chính quy Token Trị thuộc tính ws - - if if - then then - else else - id id con trỏ trong bảng ký hiệu num num giá trị số relop NE (Not Equal) > relop GT (Greater Than) >= relop GE (Greater Or Equal) Bảng 2.2. Biểu thức chính quy cho một số token b) Nhận biết bằng sơ đồ chuyển Ðể nhận biết đƣợc token, phải xây dựng cho mỗi token một sơ đồ chuyển (translation diagram). Nói chung thƣờng có nhiều sơ đồ chuyển, mỗi sơ đồ biểu diễn một nhóm token. Nếu xảy ra thất bại khi đang đi theo một sơ đồ chuyển thì phải quay lui con trỏ tới về nơi nó đã ở trong trạng thái khởi đầu của sơ đồ này rồi kích họat sơ đồ dịch tiếp theo. Do con trỏ đầu trị từ vựng và con trỏ tới cùng chỉ đến một vị trí trong trạng thái khởi đầu của sơ đồ, con trỏ tới sẽ đƣợc dịch lui lại để chỉ đến vị trí đƣợc con trỏ đầu trị từ vựng chỉ tới. Nếu xảy ra thất bại trong tất cả mọi sơ đồ dịch thì xem nhƣ một lỗi từ vựng đã đƣợc phát hiện và sẽ khởi động một thủ tục khắc phục lỗi. 41
Chƣơng 2. Phân tích từ vựng Sơ đồ chuyển nhận dạng token relop: Start 3 (Thẻ từ NE) = 5 other * 4 (Thẻ từ LT) > (Thẻ từ EQ) = (Thẻ từ GE) 6 7 (Thẻ từ G) other * 8 (Thẻ từ GT) Hình 2.3. Sơ đồ chuyển nhận dạng token relop Chú ý: Dùng ký hiệu * để chỉ ra những trạng thái đã đọc quá một ký tự, cần phải quay lui con trỏ lại bƣớc trƣớc đó. 5) Lỗi từ vựng Chỉ một số ít lỗi đƣợc phát hiện tại bƣớc phân tích từ vựng, bởi vì bộ phân tích từ vựng có nhiều cách nhìn nhận chƣơng trình nguồn. Ví dụ chuỗi fi đƣợc nhìn thấy lần đầu tiên trong một chƣơng trình Pascal với ngữ cảnh: fi a = f (x)) Bộ phân tích từ vựng không thể biết đây là lỗi không viết đúng từ khóa if hay một tên (danh biểu) chƣa đƣợc khai báo. Vì fi là một tên hợp lệ nên bộ phân tích từ vựng phải trả về một token và để một giai đoạn khác sau đó xác định lỗi. Tuy nhiên, trong một vài tình huống phải khắc phục lỗi để phân tích tiếp. Chiến lƣợc đơn giản nhất là "phương thức hoảng sợ" (panic mode): Các ký tự tiếp theo sẽ đƣợc xóa ra khỏi xâu vào cho đến khi tìm ra một token hoàn chỉnh. Kỹ thuật này đôi khi cũng gây ra sự nhầm lẫn cho giai đoạn phân tích cú pháp, nhƣng nói chung là vẫn có thể sử dụng đƣợc. Một số chiến lƣợc khắc phục lỗi khác là: 1. Xóa đi một ký tự thừa. 2. Xen thêm một ký tự bị mất. 3. Thay thế một ký tự không đúng bằng một ký tự đúng. 4. Chuyển đổi hai ký tự kế tiếp nhau. 42
Chƣơng 2. Phân tích từ vựng 2.3. Kỹ thuật đọc chƣơng trình nguồn Một trong các yêu cầu quan trọng của bộ phân tích từ vựng là phải dò đọc nhanh chƣơng trình nguồn và phát hiện nhanh các từ vị để thay thế nó bằng các thẻ từ. Một chƣơng trình nguồn thông thƣờng có hàng trăm, hàng nghìn dòng lệnh và mỗi dòng lệnh lại chứa hàng chục, hàng trăm ký tự. Yêu cầu đặt ra cho việc đọc chƣơng trình nguồn là phải đáp ứng đƣợc các điều kiện sau: - Phải dò đọc từng ký tự để phân tích toàn bộ chƣơng trình nguồn có dung lƣợng lớn tuỳ ý. - Bộ nhớ trong của máy tính có dung lƣợng hạn chế; nói chung nó không chứa hết chƣơng trình nguồn. - Bảo đảm tốc độ phân tích, xử lý nhanh. Tuy nhiên, việc đọc nhƣ vậy cũng gặp một số trở ngại do không thể xác định một chuỗi nhƣ thế nào thì chứa trọn vẹn một token? Sau đây sẽ giới thiệu một số phƣơng pháp đọc chƣơng trình nguồn sử dụng bộ đệm có hiệu quả. 2.3.1. Cặp bộ đệm (Buffer Pairs) Một trong các kỹ thuật đáp ứng đƣợc các yêu cầu trên mà các chƣơng trình dịch hay sử dụng là kỹ thuật sử dụng cặp bộ đệm (Buffer Pairs). Ý tƣởng của kỹ thuật này nhƣ sau: - Sử dụng hai Buffer có kích thƣớc N là Buffer1 và Buffer2, mỗi lần đọc chƣơng trình nguồn vào bộ nhớ trong, máy đọc một khối gồm N ký tự lấp đầy một Buffer. Thông thƣờng, N là số ký tự trên một khối đĩa, N bằng 1024 hoặc 4096. - Mỗi lần đọc, N ký tự từ chƣơng trình nguồn sẽ đƣợc đọc vào mỗi nửa bộ đệm bằng một lệnh đọc (read) của hệ thống. Nếu số ký tự còn lại trong chƣơng trình nguồn ít hơn N thì một ký tự đặc biệt eof đƣợc đƣa vào buffer sau các ký tự vừa đọc để báo hiệu chƣơng trình nguồn đã đƣợc đọc hết. - Sử dụng hai con trỏ dò tìm trong buffer. Chuỗi ký tự nằm giữa hai con trỏ luôn luôn là trị từ vựng hiện hành. Khởi đầu, cả hai con trỏ đặt trùng nhau tại vị trí bắt đầu của mỗi trị từ vựng. Con trỏ p1 (lexeme_beginning) - con trỏ bắt đầu trị từ vựng - sẽ giữ cố định tại vị trí này cho đến khi con trỏ p2 (forwar) - con trỏ tới - di chuyển qua từng ký tự trong buffer để xác định một từ vị cho một token. Khi một 43
Chƣơng 2. Phân tích từ vựng từ vị cho một token đã đƣợc xác định, con trỏ p1 dời lên trùng với p2 và bắt đầu dò tìm một trị từ vựng mới. Buffer1 Buffer2 i f a > b t h e n a = b eof P1 P2 Hình 2.4. Mô phỏng cặp bộ đệm Khi con trỏ p2 tới ranh giới giữa 2 vùng đệm, nửa bên phải đƣợc lấp đầy bởi N ký tự tiếp theo trong chƣơng trình nguồn. Khi con trỏ p2 tới vị trí cuối bộ đệm, nửa bên trái sẽ đƣợc lấp đầy bởi N ký tự mới và p2 sẽ đƣợc dời về vị trí bắt đầu bộ đệm. Phƣơng pháp cặp bộ đệm này thƣờng họat động rất tốt nhƣng khi đó số lƣợng ký tự đọc trƣớc bị giới hạn và trong một số trƣờng hợp nó có thể không nhận dạng đƣợc token khi con trỏ p2 phải vƣợt qua một khoảng cách lớn hơn chiều dài 2 vùng đệm. Giải thuật hình thức cho họat động của con trỏ p2 trong bộ đệm : if p2 ở cuối nửa đầu then begin Ðọc vào nửa cuối; p2 := p2 + 1; end else if p2 ở cuối của nửa cuối then begin Ðọc vào nửa đầu; Dời p2 về đầu bộ đệm ; end else p2 := p2 + 1 2.3.2. Khóa cầm canh (Sentinel) Phƣơng pháp cặp bộ đệm đòi hỏi mỗi lần di chuyển p2 đều phải kiểm tra xem đã hết một nửa buffer chƣa nên kém hiệu quả vì phải mất hai lần kiểm tra. Ðể 44
Chƣơng 2. Phân tích từ vựng khắc phục điều này, mỗi lần chỉ đọc N-1 ký tự vào mỗi nửa buffer còn ký tự thứ N là một ký tự đặc biệt, thƣờng là eof. Nhƣ vậy đã rút ngắn một lần kiểm tra. Giải thuật hình thức cho họat động của con trỏ p2 trong bộ đệm p2 := p2 + 1; if p2↑ = eof then begin if p2 ở cuối của nửa đầu then begin Ðọc vào nửa cuối; p2 := p2 + 1; end else if p2 ở cuối của nửa sau then begin Ðọc vào nửa đầu; Dời p2 vào đầu của nửa đầu; end else {EOF ở giữa vùng đệm chỉ hết chƣơng trình nguồn} kết thúc phân tích từ vựng end 2.4. Kỹ thuật sử dụng Automat để phân tích từ vựng 2.4.1. Giải thuật sử dụng DFA Dƣới đây là giải thuật nhận biết từ vị bằng Automat hữu hạn đơn định. Giả sử w là từ vị cần nhận biết, đƣợc đƣa vào ở dạng xâu và đƣợc bổ sung thêm ký tự $ để đánh dấu kết thúc xâu. Input: DFA M và xâu w$ Ouput: M có đoán nhận đƣợc w? Process: q:= q0 ; c:= get_char(); {hàm đọc ký hiệu đầu tiên của xâu w} While c “$” do {$ ký hiệu kết thúc xâu} 45
Chƣơng 2. Phân tích từ vựng Begin q:= (q,c); {Chuyển sang trạng thái mới } c:= get_next_char(); {hàm đọc ký hiệu tiếp theo} End; If q F Then witeln (“nhan ra w”) Else writeln (“khong nhan ra w”) Giải thuật trên đây mô tả ở dạng giả Pascal với giả thiết từ vào w có đặt dấu kết thúc là ký hiệu „$‟. Hàm get_char() là hàm trả lại ký hiệu đầu tiên trong từ w; hàm get_next_char() là hàm trả lại ký hiệu tiếp theo trong từ w. Hình 2.5 là sơ đồ mô tả Automat đoán nhận đƣợc tất cả các từ w sinh ra từ biểu thức chính quy dạng b*a+bb. a Start a b b 0 1 2 3 b Hình 2.5. Sơ đồ mô tả Automat đoán nhận biểu thức b*a+bb Ví dụ 2.16: Sử dụng giải thuật trên với automat đƣợc cho ở hình trên để đoán nhận các từ sau: - w = bbaaabb Ta trình bày giải thuật sử dụng automat để đoán nhận w bằng bảng sau: Bƣớc q c khởi tạo 0 b 1 0 b 2 0 a 3 1 a 4 1 a 5 1 b 6 2 b 7 3 $ Bảng 2.3. Mô phỏng automat đoán nhận từ bbaaabb 46
Chƣơng 2. Phân tích từ vựng Ta có q = 3 F. Vậy automat trên đoán nhận đƣợc từ w = bbaaabb. - w = aaabba Ta có kết quả thực hiện giải thuật cho ở bảng sau: Bƣớc q c khởi tạo 0 a 1 1 a 2 1 a 3 1 b 4 2 b 5 3 a 6  $ Bảng 2.4. Mô phỏng automat đoán nhận từ aaabba Ta có q =  F. Vậy automat trên không đoán nhận đƣợc từ w = aaabba. Ví dụ 2.17: Cho Automat hữu hạn M = : S = 0, 1, 2, 3, 4;  = a, b; q0 = 0; F = 2, 4. Hàm chuyển trạng thái  cho ở dạng đồ thị nhƣ hình 2.6. Có thể kiểm tra lại rằng ngôn ngữ đoán nhận bởi Automat M là tập N(M) biểu diễn bằng biểu thức chính quy (a+ b+). a 1 a 2  Start 0  b 3 4 b Hình 2.6. Biểu diễn automat bằng đồ thị 47
Chƣơng 2. Phân tích từ vựng 2.4.2. Giải thuật sử dụng NFA Input: NFA M và xâu w$ Ouput: M có đoán nhận đƣợc w? Process q := q ; 0 c := getchar() ; {c là ký hiệu vào đầu tiên} While c $ do Begin q := δ(q, c); c := nextchar() ; {c là ký hiệu vào đƣợc đọc tiếp theo} End; If q  F ≠  then writeln (“nhan ra w”) Else writeln („ không nhận ra w‟) Ví dụ 2.18: Sử dụng giải thuật trên với automat hữu hạn đƣợc cho bằng đồ thị sau để đoán nhận các xâu: w = aaabbbb$ a b Start a b b 0 1 2 3 a Hình 2.7. Đồ thị biểu diễn Automat Ta trình bày giải thuật sử dụng automat hữu hạn không đơn định đoán nhận w bằng bảng sau: Bƣớc q c khởi tạo 0 a 1 {0, 1} a 2 {0, 1} a 3 {0, 1} b 4 {2} b 48
Chƣơng 2. Phân tích từ vựng 5 {2, 3} b 6 {2, 3} b 7 {2, 3} $ Bảng 2.5. Mô tả quá trình đoán nhận xâu Ta có q = {2, 3}  F = {3} . Vậy automat trên đoán nhận đƣợc từ w = aaabbbb. 2.4.3. Giải thuật sử dụng NFA Input: NFA M và xâu vào w đƣợc kết thúc bởi $. Output: M có đoán nhận đƣợc w? Process: q:= ε-closure(q0); c:= get_char(); While c <> “$” do Begin q:= ε-closure((q,c)); c:= get_next_char(); End; If q  F  then writeln (“nhan ra w”) Else writeln („ không nhận ra w‟); Ví dụ 2.19: Cho Automat đƣợc biểu diễn bằng đồ thị nhƣ hình vẽ. Sử dụng giải thuật trên để kiểm tra Automat đoán nhận từ w = aababb  a 2 3   Start   b 6 a b 0 1  7 8 9 10  b 4 5  Hình 2.8. NFA với ε - dịch chuyển 49
Chƣơng 2. Phân tích từ vựng Ta có thể trình bày giải thuật sử dụng automat trên đoán nhận w bằng bảng sau: Bƣớc q = ε -closure((q,c)) c khởi tạo {0, 1, 2, 4, 6, 7} a 1 {1, 2, 3, 4, 6, 7, 8} a 2 {1, 2, 3, 4, 6, 7, 8} b 3 {1, 2, 4, 5, 6, 7, 9} a 4 {1, 2, 3, 4, 6, 7, 8} b 5 {1, 2, 4, 5, 6, 7, 9} b 6 {1, 2, 4, 5, 6, 7, 10} $ Bảng 2.6. Mô tả quá trình đoán nhận xâu Ta có q  F = {10} . Vậy automat trên đoán nhận đƣợc w = aababb. NFA là trƣờng hợp đặc biệt của NFA. Vì vậy ta vẫn có thể sử dụng giải thuật trên đối với NFA để nhận biết từ vị và trong trƣờng hợp này ta luôn có ε-closure(T) = T với  T  Q. 2.5. Kỹ thuật biến đổi Automat Automat hữu hạn đơn định và Automat hữu hạn không đơn định tƣơng đƣơng nhau về mặt ngôn ngữ, nghĩa là chúng cùng đoán nhận một tập chính quy. Tuy nhiên về phƣơng diện cấu trúc và viết chƣơng trình dịch thì Automat hữu hạn không đơn định phức tạp hơn nhiều so với Automat hữu hạn đơn định, vì vậy cần phải biến đổi Automat hữu hạn không đơn định về Automat hữu hạn đơn định. Để biến đổi một Automat hữu hạn không đơn định thành một Automat đơn định tƣơng đƣơng với nó về mặt ngôn ngữ, trƣớc hết cùng nhau nhắc lại một vài kiến thức sau: Xét Automat hữu hạn M = không đơn định - Ta gọi tập ε-closure(q) là tập trạng thái mà M có thể đạt đến đƣợc từ trạng thái q Q khi Automat đọc vào từ rỗng . ε-closure(q) = p Q *(q, ) = p - Ta gọi tập ε-closure(T) là tập trạng thái mà M có thể đạt đến đƣợc từ một trạng thái bất kỳ q T với T  Q khi Automat đọc vào từ rỗng  là 50
Chƣơng 2. Phân tích từ vựng ε-closure(T) = p Q *(q, ) = p; q T; TQ =  ε-CLOSURE(q) với T Q q T - Ta gọi tập δ (T, a) là tập trạng thái mà M có thể đạt đến đƣợc từ một trạng thái bất kỳ q T với T  Q khi Automat đọc vào một ký hiệu vào a là δ (T, a) =  δ(q, a) q T 1) Ý tưởng của giải thuật Giả sử có Automat hữu hạn không đơn định M = . Ta cần phải xây dựng Automat hữu hạn đơn định là D = tƣơng đƣơng đoán nhận cùng một ngôn ngữ. Khi đó mỗi trạng thái của Automat đơn định D sẽ ứng với một tập các trạng thái của Automat không đơn định M mà M có thể đạt đến đƣợc sau khi đã đọc một ký tự của từ vào. Thoạt đầu D có trạng thái bắt đầu là ε-closure(q0) và trạng thái kết thúc của D là trạng thái có chứa một trạng thái kết thúc của M. Quá trình tính ε-closure(T) là quá trình tìm các nút có thể đạt đến đƣợc trên đồ thị từ tập các nút xuất phát cho trƣớc với các ký tự vào là các ký tự của bảng chữ cái vào . 2) Giải thuật biến đổi NFA về DFA Input: NFA M = . Output: DFA D = ; L(M) = L(D). Process: Bƣớc 1: Xác định q‟0; ‟ - ‟ = ; - Tính q‟0: A = ε-closure(q0); - Đƣa A vào tập trạng Q‟ và coi nó là trạng thái chƣa đánh dấu T. Bƣớc 2: Xác định Q‟ và ‟ Nếu trong Q‟ có trạng thái T chƣa đánh dấu thì đánh dấu T - Với mỗi a ‟ thực hiện + Tính B = ε-closure((T,a)); + Nếu B là trạng thái mới chƣa có trong Q‟ thì đƣa B vào Q‟; + Đƣa vào bảng hàm chuyển ‟: ‟(T, a) = B. Bƣớc 3: Lặp lại bƣớc 2 nếu Q‟còn trạng thái chƣa đánh dấu. Bƣớc 4: F‟ = {A Q‟ / A  F } Bƣớc 5: D = 51
Chƣơng 2. Phân tích từ vựng Hình 2.9 là sơ đồ khối của giải thuật xác định Q‟ và ‟. Giả sử ta đánh số các ký hiệu của ‟ là a1, a2, , an Begin Q‟: = e_closure(q0); ‟:=   T Q‟ s End chƣa đánh dấu đ Đánh dấu T i := 1 s i n đ B:= e-cloure((T, ai)) Q‟:= Q‟  {B}; ‟ := ‟  { ‟(T, a ) = B } i i := i+1 Hình 2.9. Sơ đồ giải thuật Ví dụ 2.20: a) Cho Automat hữu hạn NFA M = có đồ thị chuyển là hình 2.10. Hãy xây dựng Automat hữu hạn đơn định D đoán nhận cùng ngôn ngữ với M. a a b Start 0  1 2 3 b b  Hình 2.10. Biểu diễn automat bằng đồ thị 52
Chƣơng 2. Phân tích từ vựng Ta có thể nhận thấy M đoán nhận ngôn ngữ N(M) = b*(b|)a+(b|)=b*a+(b| ) Áp dụng giải thuật, ta có: D = . Trong đó: - ‟ = {a, b}; - q‟0 = ε-closure(0) = {0, 1} = A; Q‟ = {A}; - Xét A: + ε-closure( (A, a)) = ε-closure(({0, 1}, a)) = ε-closure ((0, a)  (1, a)) = ε-closure( {1, 2}) = ε-closure({1, 2}) = ε-closure(1)  ε-closure(2) = {1} {2, 3} = {1, 2, 3} = B Q‟ = {A, B} ; ‟ = {(A, a) = B} + ε-closure( (A, b)) = ε-closure(({0, 1}, b)) = ε-closure ( (0, b) (1, b)) = ε-closure({0,1} ) = ε-closure({0, 1}) = ε-closure(1)  ε-closure(1) = {0,1} {1} = {0, 1} = A Q‟ = {A, B} ; ‟ = {‟(A, a) = B; ‟(A, b) = A} - Xét B: + ε-closure( (B, a)) = ε-closure(({1, 2, 3}, a)) = ε-closure ( (1, a) (2, a) (3, a)) = ε-closure({1,2}  )= ε-closure({1, 2}) = {1, 2, 3} = B Q‟ = {A, B} ; ‟ = {‟(A, a) = B; ‟(A, b)) = A; ‟(B, a) = B} + ε-closure( (B, b)) = ε-closure(({1, 2, 3}, b)) = ε-closure ( (1, b) (2, b) (3, b)) = ε-closure( {3} ) = ε-closure({3}) = {3} = C Q‟ = {A, B, C} ; ‟ = {‟(A, a) = B; ‟(A, b)) = A; ‟(B, a) = B; ‟(B, b) = C} - Xét C: 53
Chƣơng 2. Phân tích từ vựng + ε-closure( (C, a)) = ε-closure((3, a)) =  + ε-closure( (C, b)) = ε-closure((3, b)) =  - F‟ = {B, C} Vậy D = . Trong đó: Q‟ = {A, B, C} ; ‟ = {a, b}; q‟0 = A; ‟: ‟(A, a)) = B; ‟(A, b)) = A; ‟(B, a) = B; ‟(B, b) = C F‟ = {B, C}. Đồ thị chuyển của automat D b a Start a b A B C Hình 2.11. Biểu diễn automat bằng đồ thị Ta có thể nhận thấy D đoán nhận ngôn ngữ L(M) = b*a+(b | ) Ta có thể tóm tắt kết quả của việc thực hiện giải thuật trên nhƣ sau: - q‟0 = ε-closure(q0) = ε-closure(0) = {0, 1} = A; - ‟ = {a, b}; - Xác định Q‟ và ‟ Bƣớc Đánh dấu T ai B = ε-closure((T, ai)) Bsung vào Q‟ Bsung vào ‟ Kt {0, 1} A 1 A a {1, 2, 3} B ‟(A, a) = B b {0, 1} ‟(A, b) = A 2 B a {1, 2, 3} ‟(B, a) = B b {3} C ‟(B, b) = C 3 C a  b  Bảng 2.7. Mô phỏng giải thuật - Xác định F‟ = {B, C} 54
Chƣơng 2. Phân tích từ vựng b) Xét Automat hữu hạn M = không đơn định có  dịch chuyển. Với Q = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10; q0 = 0; F = 10;  = a,b; hàm  cho trong hình 2.15. Có thể kiểm tra lại rằng tập ngôn ngữ đoán nhận bởi Automat hữu hạn M là tập N(M) = (a b)*abb.  a  2 3  Start   a b b 0 1 6 7 8 9 10  b  4 5  Hình 2.12. Biểu diễn automat bằng đồ thị Để xây dựng automat hữu hạn đơn định D đoán nhận cùng ngôn ngữ với Automat M, ta sử dụng giải thuật trên. - Tính q‟0 = ε-closure(q0) = ε-closure(0) = 0, 1, 2, 4, 7 = A; - ‟ = {a, b}; - Xác định Q‟ và ‟: Bƣớc Đánh dấu T ai B = ε-closure((T, ai)) Bổ sung vào Q‟ Bổ sung vào ‟ Kt {0, 1, 2, 4, 7} = A A 1 A a {1, 2, 3, 4, 6, 7, 8} = B B ‟(A, a) = B b {1, 2, 4, 5, 6, 7} = C C ‟(A, b) = C 2 B a {1, 2, 3, 4, 6, 7, 8} = B ‟(B, a) = B b {1, 2, 4, 5, 6, 7, 9} = D D ‟(B, b) = D 3 C a {1, 2, 3, 4, 6, 7, 8} = B ‟(C, a) = B b {1, 2, 4, 5, 6, 7} = C ‟(C, b) = C 4 D a {1, 2, 3, 4, 6, 7, 8}= B ‟(D, a) = B b {1, 2, 4, 5, 6, 7, 10} = E E ‟(D, b) = E 5 E a {1, 2, 3, 4, 6, 7, 8}= B ‟(E, a) = B b {1, 2, 4, 5, 6, 7} = C ‟(E, b) = C Bảng 2.8. Mô phỏng giải thuật 55
Chƣơng 2. Phân tích từ vựng - Xác định F‟ = {E} b C b a a b Start a b b A B D E a a Hình 2.13. Biểu diễn automat bằng đồ thị Chú ý: NFA là trƣờng hợp đặc biệt của NFA. Vì vậy ta vẫn có thể sử dụng giải thuật trên để biến đổi NFA về DFA. Tuy nhiên, trong trƣờng hợp này luôn luôn có ε-closure(T) = T với  T  Q. Vì vậy, có thể đƣa ra giải thuật cụ thể trong trƣờng hợp này nhƣ sau. 3) Giải thuật biến đổi NFA về DFA Input: NFA M = . Output: DFA D = ; L(M) = L(D). Process: Bƣớc 1: Xác định q‟0; ‟ - ‟ = ; - Tính q‟0: A = q0; - Đƣa A vào tập trạng Q‟ và coi nó là trạng thái chƣa đánh dấu T. Bƣớc 2: Xác định Q‟ và ‟ Nếu trong Q‟ có trạng thái T chƣa đánh dấu thì đánh dấu T - Với mỗi a ‟ thực hiện + Tính B = (T,a); + Nếu B là trạng thái mới chƣa có trong Q‟ thì đƣa B vào Q‟; + Đƣa vào bảng hàm chuyển ‟: ‟(T, a) = B. Bƣớc 3: Lặp lại bƣớc 2 nếu Q‟còn trạng thái chƣa đánh dấu. Bƣớc 4: F‟ = {A Q‟ / A  F } Bƣớc 5: D = 56
Chƣơng 2. Phân tích từ vựng Hình 2.14 là sơ đồ khối của giải thuật xác định Q‟ và ‟. Giả sử ta đánh số các ký hiệu của ‟ là a1, a2, , an Begin Q‟: = {q0}; ‟:=   T Q‟ s End chƣa đánh dấu đ Đánh dấu T i := 1 s i n đ B:= (T, ai) Q‟:= Q‟  {B}; ‟ := ‟  { ‟(T, a ) = B } i i := i+1 Hình 2.14. Sơ đồ giải thuật Ví dụ 2.21: a) Cho Automat hữu hạn NFA M = có đồ thị chuyển là hình 2.15. Hãy xây dựng Automat hữu hạn đơn định D đoán nhận cùng ngôn ngữ với M. a a a b Start 0 1 2 3 b b a Hình 2.15. Biểu diễn automat bằng đồ thị 57
Chƣơng 2. Phân tích từ vựng Ta có thể nhận thấy M đoán nhận ngôn ngữ N(M) = b*(a| b)a+(a| b) Áp dụng giải thuật, ta có: D = . Trong đó: - ‟ = {a, b}; - q‟0 = {0} = A; Q‟ = {A}; - Xét A: + (A, a) = ({0}, a) = (0, a) = {1} = B Q‟ = {A, B}; ‟ = {‟(A, a) = B} + (A, b) = ({0}, b)) = (0, b) = {0, 1} = C Q‟ = {A, B, C}; ‟ = {‟(A, a) = B; ‟(A, b) = C} - Xét B: + (B, a) = (1, a) = {1} = B Q‟ = {A, B, C}; ‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B} + (B, b)) = (1, b) =  Q‟ = {A, B, C}; ‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B} - Xét C: + (C, a)) = ({0, 1}, a) = (0, a)  (1, a) = {1, 2} = D Q‟ = {A, B, C, D}; ‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D} +  (C, b)) = ({0, 1}, b) = (0, b)  (1, b) = {0, 1} = C Q‟ = {A, B, C, D}; ‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D; ‟(C, b) = C} - Xét D: + (D, a)) = ({1, 2}, a) = (1, a)  (2, a) = {1, 2}  {3}= {1, 2, 3}= E Q‟ = {A, B, C, D, E}; ‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D; ‟(C, b) = C; ‟(D, a) = E} 58
Chƣơng 2. Phân tích từ vựng +  (D, b)) = ({1, 2}, b) = (1, b)  (2, b) = {3} = F Q‟ = {A, B, C, D, E, F}; ‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D; ‟(C, b) = C; ‟(D, a) = E; ‟(D, b) = F} - Xét E: + (E, a)) = ({1, 2, 3}, a) = (1, a)  (2, a)  (3, a) = {1, 2, 3}= E Q‟ = {A, B, C, D, E, F}; ‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D; ‟(C, b) = C; ‟(D, a) = E; ‟(D, b) = F; ‟(E, a) = E} + (E, b)) = ({1, 2, 3}, b) = (1, b)  (2, b)  (3, b) = {3}= F Q‟ = {A, B, C, D, E, F}; ‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D; ‟(C, b) = C; ‟(D, a) = E; ‟(D, b) = F; ‟(E, a) = E;‟(E, b) = F} - Xét F: (F, a)) = ({3}, a) = (3, a) =  Q‟ = {A, B, C, D, E, F}; ‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D; ‟(C, b) = C; ‟(D, a) = E; ‟(D, b) = F; ‟(E, a) = E;‟(E, b) = F} (F, b)) = ({3}, b) = (3, b) =  Q‟ = {A, B, C, D, E, F}; ‟ = {‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D; ‟(C, b) = C; ‟(D, a) = E; ‟(D, b) = F; ‟(E, a) = E;‟(E, b) = F} - F‟ = {E, F}. Vậy D = . Trong đó: Q‟ = {A, B, C, D, E, F} ; ‟ = {a, b}; q‟0 = A; ‟:{‟(A, a) = B; ‟(A, b)) = C; ‟(B, a) = B; ‟(C, a) = D; ‟(C, b) = C; ‟(D, a) = E; ‟(D, b) = F; ‟(E, a) = E; ‟(E, b) = F} 59
Chƣơng 2. Phân tích từ vựng F‟ = {E, F}. Đồ thị chuyển của automat D a b a a Start a a a D b A B C E F C b b Hình 2.16. Biểu diễn automat bằng đồ thị Ta có thể nhận thấy D đoán nhận ngôn ngữ L(M) = b*a+(b | ) Ta có thể tóm tắt kết quả của việc thực hiện giải thuật trên nhƣ sau: - q‟0 = {q0} = A; - ‟ = {a, b}; - Xác định Q‟ và ‟ Bƣớc Đánh dấu T ai B = (T, ai) Bổ sung vào Q‟ Bổ sung vào ‟ Kt {0} = A A 1 A a {1} = B B ‟(A, a) = B b {0, 1}= C C ‟(A, b) = C 2 B a {1} = B ‟(B, a) = B b  3 C a {1, 2}= D D ‟(C, a) = D b {0, 1}= C ‟(C, b) = C 4 D a {1, 2, 3}= E E ‟(D, a) = E b {3} = F F ‟(D, b) = F 5 E a {1, 2, 3}= E ‟(E, a) = E b {3}= F ‟(E, b) = F 6 F a  b  Bảng 2.9. Mô phỏng giải thuật - Xác định F‟ = {B, C}. 60
Chƣơng 2. Phân tích từ vựng 2.6. Giải thuật Thomson Với mục đích sử dụng Automat hữu hạn để phân tích từ vựng. Thomson đã đƣa ra giải thuật giải quyết bài toán sau: Cho trƣớc một biểu thức chính quy. Hãy xây dựng Automat đoán nhận ngôn ngữ đƣợc biểu diễn bởi biểu thức chính quy đó. Tƣ tƣởng của giải thuật dựa vào ý tƣởng, mọi biểu thức chính quy đều có thể phân tích thành các biểu thức chính quy đơn giản hơn. Từ đó đi xây dựng các Automat đơn giản đoán nhận các biểu thức chính quy đơn giản. Sau đó tổng hợp nó để đƣợc Automat cần xây dựng. 1) Phương pháp xây dựng các automat đoán nhận các biểu thức chính quy đơn giản a) Xây dựng Automat đoán nhận từ rỗng . Hình 2.17 là Automat đoán nhận từ rỗng với i là trạng thái bắt đầu, f là trạng thái kết thúc. Start  i f Hình 2.17. Automat đoán nhận biểu thức r=  b) Xây dựng Automat đoán nhận ký tự a . Start a i f Hình 2.18. Automat đoán nhận biểu thức r = a Hình 2.18 là sơ đồ biểu diễn Automat đoán nhận a, với i là trạng thái bắt đầu, f là trạng thái kết thúc. 2) Phương pháp xây dựng các automat tổng hợp từ các automat a) Giả sử s và t là hai biểu thức chính quy và N(s), N(t) là hai Automat đoán nhận s và t tƣơng ứng khi đó Automat đoán nhận biểu thức chính quy s + t có dạng nhƣ hình 2.19. N(s)   Start i f  N(t)  Hình 2.19. Automat đoán nhận biểu thức r = s+t 61
Chƣơng 2. Phân tích từ vựng Ở đây i, f là các trạng thái mới chƣa có trong N(s), N(t), từ trạng thái bắt đầu i Automat nhìn thấy từ rỗng; nó có thể chuyển sang trạng thái bắt đầu của N(r) hoặc trạng thái bắt đầu của N(t). Ngƣợc lại từ trạng thái cuối của N(s) hoặc N(t) nó có thể chuyển sang trạng thái kết thúc f khi gặp từ rỗng. b) Xây dựng Automat đoán nhận biểu thức chính quy st. Giả sử N(s), N(t) là hai Automat đoán nhận svà t tƣơng ứng khi đó Automat đoán nhận biểu thức chính quy st có dạng nhƣ hình 2.20. Start i N(s) N(t) f Hình 2.20. Automat đoán nhận biểu thức r=st Ở đây i là trạng thái mới chƣa có trong N(s) và N(t), khi gặp từ rỗng Automat chuyển đến trạng thái đầu của N(s), trạng thái kết thúc của N(s) và trạng thái bắt đầu của N(t) đƣợc kết hợp thành một trạng thái, trạng thái kết thúc của N(t) trở thành trạng thái kết thúc của Automat hợp thành. c) Giả sử s là biểu thức chính quy, và N(s) là Automat đoán nhận nó, ta xây dựng Automat đoán nhận s* và s+. Hình 2.21a mô tả Automat N(s*), Hình 2.21 b + mô tả Automat N(s )  Start   i N(s) f  Hình 2.21a. Automat đoán nhận biểu thức r = s*  Start   i N(s) f Hình 2.21b. Automat đoán nhận biểu thức r = s+ Ở đây i, f là trạng thái mới tƣơng ứng là trạng thái bắt đầu và trạng thái cuối cùng của Automat. 62
Chƣơng 2. Phân tích từ vựng 3) Giải thuật Thomson Input: r – biểu thức chính quy; Output: NFA  M ; N(M) = N(r). Process: Bước 1: Phân tích r thành các biểu thức chính quy đơn giản - Tìm trong biểu thức chính quy phép toán có thứ tự ƣu tiên thấp nhất - Nếu có thì phân tích biểu thức chính quy thành các toán hạng theo phép toán đó. Mỗi toán hàng – một biểu thức chính quy đơn giản hơn. - Quay lại bƣớc 1 cho đến khi đã phân tích tất cả các biểu thức chính quy thánh các biểu thức chính quy đơn giản dạng r = a. Bước 2: Xây dựng - Xây dựng các automat đơn giản đoán nhận các biểu thức chính quy đơn giản. - Xây dựng các automat tổng hợp theo thứ tự ngƣợc lại cho đến khi xây dựng automat tổng hợp đoán nhận biểu thức chính quy r. Nhận xét: - Với biểu thức chính quy r, Automat N(r) đoán nhận nó sẽ có số trạng thái nhiều nhất không vƣợt quá hai lần số ký tự có trong r và số phép toán có trong nó. Điều nhận xét này có đƣợc là do trong giải thuật Thomson với mỗi ký hiệu hoặc phép toán trong r ta thêm vào không quá hai trạng thái. - Mỗi Automat N(r) xây dựng theo giải thuật Thomson chỉ có một trạng thái đầu và một trạng thái kết thúc, và trạng thái kết thúc không bao giờ chuyển sang một trạng thái nào khác. - Mỗi trạng thái của Automat N(r) chỉ có một trạng thái chuyển đi theo ký hiệu của tập  và tối đa hai trạng thái chuyển đi theo ký hiệu rỗng , vì vậy nói chung Automat xây dựng theo giải thuật Thomson là Automat không đơn định. - Do mỗi lần xây dựng một Automat mới ta thêm vào trạng thái bắt đầu và kết thúc mới, cho nên Automat xây dựng theo giải thuật Thomson không có hai trạng thái trùng nhau. 63
Chƣơng 2. Phân tích từ vựng Ví dụ 2.22: Cho r = (a b)*abb. Hãy xây dựng NFA đoán nhận biểu thức chính quy r theo giải thuật Thomson. Bước 1: Phân tích r = (a + b)*abb - r = r1r2; * r1 = (a + b) ab; r2 = b; - r1 = r3r4; * r3 = (a + b) a; r4 = b; - r3 = r5r6; * r5 = (a + b) ; r6 = a; * - r5 = (r7) ; r7 = a + b; - r7 = r8r9; R8 = a ; r9 = b; Bước 2: Xây dựng - Xây dựng Automat đoán nhận r8= a; r9 = b Start a 2 3 Start b 4 5 Hình 2.22. Các automat đoán nhận a, b - Xây dựng Automat đoán nhận r7 = r8 + r9 a  2 3  Start 1 6   b 4 5 Hình 2.23. Automat đoán nhận r7 = a+b 64
Chƣơng 2. Phân tích từ vựng * - Xây dựng Automat đoán nhận r5 =(r7)  a  2 3  Start   0 1 6 7   b 4 5  * Hình 2.24. Automat đoán nhận r5 = (a+b) Thực hiện tƣơng tự với r6 = a; r3 = r5 r6; r4 = b; r1 = r3 r4; r2 = b; r = r1 r2. Thu đƣợc kết quả nhƣ hình sau:  a  2 3  Start  0 1  a b b 6 7 8 9 10   b 4 5  Hình 2.25. Automat đoán nhận r=(a b)*abb 65
Chƣơng 2. Phân tích từ vựng CÂU HỎI VÀ BÀI TẬP CHƢƠNG 2 2.1. - Nêu các khái niệm: thẻ từ, trị từ vựng, mẫu từ vựng; cho ví dụ. - Nêu các phƣơng pháp biểu diễn thẻ từ; cho ví dụ minh họa. 2.2. Nêu vị trí, chức năng, nhiệm vụ của giai đoạn phân tích từ vựng. 2.3. Nêu các kỹ thuật đọc chƣơng trình nguồn sử dụng buffer. 2.4. Nêu giải thuật nhận biết từ vị bằng automat đơn định DFA. Chạy ví dụ minh họa 2.5. Nêu giải thuật nhận biết từ vị bằng automat không đơn định NFA. Chạy ví dụ minh họa. 2.6. Nêu giải thuật nhận biết từ vị bằng automat không đơn định NFA. Chạy ví dụ minh họa. 2.7. Nêu giải thuật biến đổi automat không đơn định NFA về automat đơn định DFA đoán nhận cùng một ngôn ngữ. Cho ví dụ minh họa. 2.8. Nêu giải thuật biến đổi automat không đơn định NFA về automat đơn định DFA đoán nhận cùng một ngôn ngữ. Cho ví dụ minh họa. 2.9. Nêu giải thuật Thomson để xây dựng một automat đoán nhận một biểu thức chính quy. Cho ví dụ minh họa. 2.10. Hãy xác định các trị từ vựng và chỉ ra các token trong các đoạn chƣơng trình Pascal sau: function max2 (i, j : integer) : integer; { Trả về số nguyên lớn hơn trong 2 số i và j } begin If i > j then max2 : = i else max2 : = j; end; 2.11. Hãy xác định các trị từ vựng và chỉ ra các token trong các đoạn chƣơng trình Pascal sau: PROGRAM GPTB2; VAR a,b,c,x1,x2: real; FUNCTION Delta: real; 66
Chƣơng 2. Phân tích từ vựng Begin Delta:= Sqr(b) - 4*a*c; End; PROCEDURE Ptb2; VAR r: real; {r la bien cuc bo} BEGIN BEGIN r := Sqrt (delta); x1 := (-b-r)/(2*a); x2 := (-b+r)/(2*a); END; END; (* than chuong trinh *) BEGIN REPEAT Write(„a=‟); readln(a); UNTIL a 0 Then Begin Ptb2; Writeln ( „PT co 2 nghiem: x1=‟,x1:1:2,‟x2=‟,x2:1:2); Writeln ( „x2 = ‟, x2:1:2); End; Readln; END. 67
Chƣơng 2. Phân tích từ vựng 2.12. Trong ngôn ngữ lập trình bậc cao Pascal, cho một số thẻ từ đƣợc phát biểu bằng lời nhƣ sau: 1) Số nguyên không dấu là một xâu bắt đầu bằng một số, sau đó là không, một hoặc nhiều các chữ số. 2) Số nguyên là một xâu bắt đầu bằng phần dấu, sau đó là một số nguyên không dấu; phần dấu là dấu + hoặc dấu - hoặc không có ký tự nào. 3) Số thực dấu phảy tĩnh là một xâu bắt đầu bằng phần dấu; sau đó là phần nguyên rồi đến phần thập phân; phần thập phân có thể có, có thể không; nếu có phần thập phân thì hai phần này phân cách nhau bởi dấu chấm. Phần nguyên và phần thập phân là một số nguyên không dấu 4) Số thực dấu phảy động là một xâu bắt đầu bằng một số nguyên, tiếp đến là dấu chấm, sau đó là một số nguyên không dấu, tiếp theo là phấn mũ. Phần mũ bắt đầu bằng ký tự E, tiếp đến là một số nguyên. 5) Các toán tử số học là một trong các phép toán +, -, *, / , 6) Khoảng trắng là một hoặc nhiều ký tự trống hoặc dấu tab hoặc dấu xuống dòng. 7) Tên là một xâu các ký tự, bắt đầu bằng một chữ cái; sau đó là không, một hoặc nhiều các chữ cái hoặc chữ số. Có thể thay chữ cái hoặc chữ số bằng dấu gạch dƣới. a) Hãy biểu diễn mỗi thẻ từ trên bằng biểu thức chính quy và chỉ ra thẻ từ, mẫu từ vựng, trị từ vựng của mỗi từ đó. b) Xây dựng sơ đồ chuyển để nhận biết mỗi token trên. 2.13. Cho Automat M: 1 0, 1 Start 0 0 1 q1 q2 q3 q4 0 1 Hình BT 2.13 68
Chƣơng 2. Phân tích từ vựng a) Hãy xác định các thành phần của automat M. Automat trên thuộc loại nào? tại sao? b) Sử dụng giải thuật nhận biết từ vị bằng Automat tƣơng ứng với M; Kiểm tra xem M có nhận biết đƣợc các từ vị sau không? 1) 1010101100$ 2) 110011101$ 3) 000000000$ c) Chỉ ra ngôn ngữ đoán nhận bởi M 2.14. Cho Automat M 1 0 1 0 0 Start 1 0 1 A B C D Hình bt 2.14 a) Nêu các thành phần của M b) Dùng giải thuật đoán nhận từ vị tƣơng ứng với automat trên để đoán nhận các từ: + w = 1110011$ + w = 100001110$ + w = 111100000$ c) Chỉ ra ngôn ngữ đoán nhận bởi M d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 2.15. Cho Automat M a a b 1 2 b Start b 0 5 6 a b a 3 4 b b Hình BT 2.15 a) Nêu các thành phần của M b) Dùng giải thuật đoán nhận từ vị tƣơng ứng với automat trên để đoán nhận các từ: + w = baaaabb$ 69
Chƣơng 2. Phân tích từ vựng + w = aabbbab$ + w = aababbbb$ c) Chỉ ra ngôn ngữ đoán nhận bởi M d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 2.16. Cho Automat M.   1 0 0 1 Start q q q q 0 1 2 3  0 Hình BT 2.16 a) Hãy xác định các thành phần của automat M. Automat trên thuộc loại nào? tại sao? b) Sử dụng giải thuật nhận biết từ vị bằng Automat tƣơng ứng với M; Kiểm tra xem M có nhận biết đƣợc các từ vị sau không? 1) 00011111$ 2) 01111110$ 3) 000000001$ c) Chỉ ra ngôn ngữ đoán nhận bởi M d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M  2.17. Cho Automat M. 1 Start 0 0 1 q0 q1 q2 q3   0 0 Hình BT 2.17 a) Hãy xác định các thành phần của automat M. Automat trên thuộc loại nào? tại sao? b) Sử dụng giải thuật nhận biết từ vị bằng Automat tƣơng ứng với M; Kiểm tra xem M có nhận biết đƣợc các từ vị sau không? 1) 000101001$ 70
Chƣơng 2. Phân tích từ vựng 2) 01010100$ 3) 0000000010$ c) Chỉ ra ngôn ngữ đoán nhận bởi M d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 2.18. Cho Automat M b a 1 a 2  b Start 0 b  b 3 4 Hình BT 2.18 a) Nêu các thành phần của M b) Dùng giải thuật đoán nhận từ vị tƣơng ứng với automat trên để đoán nhận các từ: 1) w = bbbaaa$ 2) w = bbaaab$ c) Chỉ ra ngôn ngữ đoán nhận bởi M d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 2.19. Cho Automat M a 1 a  2  Start b 0 5 6  a  3 4 b b Hình BT 2.19 a) Nêu các thành phần của M b) Dùng giải thuật đoán nhận từ vị tƣơng ứng với automat trên để đoán nhận các từ: + w = aaaaab + w = bbbbab c) Chỉ ra ngôn ngữ đoán nhận bởi M 71
Chƣơng 2. Phân tích từ vựng d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 2.20. Cho Automat M 1 1   Start 1 0 1 A B C D   Hình BT 2.20 a) Nêu các thành phần của M b) Dùng giải thuật đoán nhận từ vị tƣơng ứng với automat trên để đoán nhận các từ: + w = 111110 + w = 111111 c) Chỉ ra ngôn ngữ đoán nhận bởi M d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 2.21. Cho Automat M a  b 1 2 a b Start 0  a 4 a 3 b Hình BT 2.21 a) Nêu các thành phần của M b) Dùng giải thuật đoán nhận từ vị tƣơng ứng với automat trên để đoán nhận các từ: + w = bbbaaaa + w = aaaabba c) Chỉ ra ngôn ngữ đoán nhận bởi M d) Xây dựng DFA đoán nhận cùng ngôn ngữ với Automat M 72
Chƣơng 2. Phân tích từ vựng 2.22. Cho các biểu thức chính quy a) 0(0 + 1)* 0+ * b) ((0+ 1) 0(0 + 1))+ c) (1+ 0)00 (0* + 1+) * d) (a + ba + aab) (ε + a)+ Hãy xây dựng các NFAε tƣơng đƣơng với mỗi biểu thức trên. 2.23. Cho các biểu thức chính quy sau: * + * a) ( a + b ) * + b) ((ε + a) b ) + * c) (a + b) abb (a + b) * * d) ab + (a + bb) a b 1) Xây dựng NFAε đoán nhận các biểu thức chính quy trên. 2) Hãy chuyển mỗi sang DFA tƣơng đƣơng. 2.24. Quá trình phân tích từ vựng dựa vào sơ đồ chuyển có thể đƣợc tiến hành theo giải thuật sau: Input: Sơ đồ chuyển của token và xâu vào w$ Output: phân tích xâu vào có từ vị của token? Process: Bƣớc 1: Xuất phát từ trạng thái bắt đầu của ký tự khởi đầu của token, con trỏ trỏ vào ký tự đầu tiên của xâu vào w. Bƣớc 2: Nếu trên sơ đồ chuyển đang ở nút i và cung đi ra có nhãn là  đang nối với nút j thì khi đó: - Nếu  là ký tự kết thúc (Terminal) và ký tự mà con trỏ đang trỏ trong w cũng là  thì con trỏ trỏ đến ký tự tiếp theo của xâu w và quá trình duyệt chuyển sang nút j. - Nếu  là token thì quá trình duyệt chuyển sang duyệt trạng thái bắt đầu trong sơ đồ chuyển của token . + Nếu quá trình duyệt đến đƣợc trạng thái kết thúc của biến  thì quá trình duyệt quay trở lại nút j. 73
Chƣơng 2. Phân tích từ vựng + Ngƣợc lại * Nếu ở nút i còn cung đi ra thì chọn cung đi ra tiếp theo và quay lại bƣớc 2. * Nếu đã xét hết các cung đi ra khỏi nút i và quá trình duyệt không đến đƣợc trạng thái kết thúc của token  thì báo lỗi. - Nếu từ nút i đến nút j có cung mang nhãn , thì quá trình duyệt chuyển thẳng đến nút j và con trỏ trỏ vào ký tự trên xâu vào w đứng yên. Bƣớc 3: Nếu quá trình duyệt đã duyệt hết xâu vào và: - Nếu quá trình duyệt đến đƣợc trạng thái kết thúc của sơ đồ chuyển của token thì thông báo thành công. - Ngƣợc lại thì thông báo lỗi. Cho các sơ đồ chuyển: 1) 0,1,2,3,4,5,6,7,8,9 Digit: Start q0 A, , Z, a, , z q1 digit 2) Start digit Digits: q q3 2 3) +, - sign: Start q4 q5  digit sign 4) Start digit Digitsign: q 6 q7 q8 digit digit 5) number: +,- ,  digit digit Start q q q . 9 10 11 q12 q13  =, - 74
Chƣơng 2. Phân tích từ vựng 6) digit digit digit num s: Start +,- , digit digit E +,- , digit q q q q19 q20 q21 14 15 16 . q17 q18 7) Letter: Start A, ,Z, a, ,z q22 q23 letter, digit id: Start letter q q25 24 8) Hình BT 2.24 Và các xâu: 1) 123; -23467; 123.56; +123.789; - 001.34256; 123b 2) X1, a23b5; 1b34a; bien12, anpha1 3) 123. 01E02; -021E-03; +23. 098E+04 a) Sử dụng các giải thuật trên, kiểm tra các xâu trên là từ vị của token nào trong các token sau: 1) Digits 2) Digitsign 3) Number 4) Nums 5) id b) Hãy tổng hợp các sơ đồ trên để có đƣợc các sơ đồ chuyển dùng để nhận biết các token: 1) Digits 2) Digitsign 3) Number 4) Nums 5) id c) Sử dụng các sơ đồ đã tổng hợp đƣợc, kiểm tra các xâu trên là từ vị của token nào trong các token trên. 75