Bài giảng Chương trình dịch: Bài 10 - Trương Xuân Nam

Bài giảng Chương trình dịch: Bài 10 do Trương Xuân Nam biên soạn, cùng nắm kiến thức trong bài học này thông qua tìm hiểu các nội dung sau: Khắc phục hạn chế của các phương pháp thử-sai, các phương pháp phân tích cú pháp vạn năng, áp dụng quy hoạch động vào phân tích cú pháp.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương trình dịch: Bài 10 - Trương Xuân Nam CHƯƠNG TRÌNH DỊCH Bài 10: Phân tích văn phạm bằng thuật toán CYK Nội dung 1. 2. 3. 4. Khắc phục hạn chế của các phương pháp thử-sai Các phương pháp phân tích cú pháp vạn năng Áp dụng quy hoạch động vào phân tích cú pháp Thuật toán Cocke – Younger – Kasami (CYK)     Dạng chuẩn Chomsky (CNF) Ý tưởng Mã minh họa Đánh giá thuật toán 5. Bài tập TRƯƠNG XUÂN NAM 2 Phần 1 Khắc phục hạn chế của các phương pháp thử-sai TRƯƠNG XUÂN NAM 3 Các hạn chế của thử-sai  Hai thuật toán thử-sai cơ bản top-down và bottomup đều có những hạn chế về văn phạm đầu vào  Top-down: văn phạm không có đệ quy trái  Bottom-up: văn phạm không có suy dẫn rỗng và không có kí hiệu đệ quy (A ⇒+ A)  Các thuật toán thử-sai có hạn chế về mặt tốc độ  Tốc độ chấp nhận được với một số văn phạm đơn giản và đơn nghĩa, đầu vào ngắn  Trường hợp xấu có độ phức tạp tính toán hàm mũ  Không có cơ chế hiệu quả loại bỏ sự trùng lặp về kết quả (chẳng hạn như nhiều suy dẫn tương đương) TRƯƠNG XUÂN NAM 4 Các hạn chế của thử-sai  Nguyên nhân của những hạn chế này  Hạn chế do bản thân cơ chế hoạt động của thử-sai  Không có cơ chế loại bỏ các phương án chắc-chắn-sai  Ví dụ: quá trình suy dẫn S thành w = abcdefg S ⇒ … ⇒ abcAx ⇒ … ⇒ abcdefg  Ta nhận thấy phương án có chuỗi trung gian abcAx hoàn toàn không thể đạt được chuỗi w mong muốn  Vì x là kí hiệu không kết thúc, nó luôn luôn tồn tại trong các suy dẫn tiếp theo, trong khi chuỗi w không chứa x  Câu hỏi: thuật toán thử sai tốt ~ cắt nhánh sớm? TRƯƠNG XUÂN NAM 5