tailieunhanh - Bài giảng Chương trình dịch - Bài 12: Thuật toán phân tích CYK

Bài giảng Chương trình dịch - Bài 12: Thuật toán phân tích CYK bao gồm những nội dung về 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. | CHƯƠNG TRÌNH DỊCH BÀI 12: THUẬT TOÁN PHÂN TÍCH 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 Thuật toán thử sai tốt ~ cắt nhánh sớm? TRƯƠNG XUÂN .

• Kỹ thuật lập trình
• Chương trình dịch
• Bài giảng Chương trình dịch
• Thuật toán phân tích CYK
• Phương pháp thử sai
• Cú pháp vạn năng
• Thuật toán Cocke Younger Kasami
• Ứng dụng chương trình dịch
• Chương trình dịch điển hình
• Một hệ thống dịch
• Đặc trưng của chương trình dịch
• Biên dịch chương trình
• Ngữ cảnh của trình biên dịch
• Phân tích từ vựng
• Phân tích cú pháp
• Nhập môn chương trình dịch
• Khái niệm chương trình dịch
• Cấu trúc một chương trình dịch
• Bài toán chương trình dịch
• Bài giảng Nhập môn chương trình dịch
• Kỹ thuật dịch
• Quá trình biên dịch
• Ngôn ngữ lập trình cấp cao
• Ngôn ngữ học
• Phương pháp dịch
• Xây dựng chương trình dịch
• Đề thi Xây dựng chương trình dịch
• Ôn thi Xây dựng chương trình dịch
• Ôn tập Xây dựng chương trình dịch
• Các loại chương trình dịch
• Ngôn ngữ máy
• Ngôn ngữ bậc cao
• Kiến trúc của một chương trình dịch
• Bài giảng Xây dựng chương trình dịch
• Máy ngăn xếp
• Xây dựng bảng ký hiệu
• Chương trình đích được dịch từ
• Cài đặt chương trình dịch
• Sinh mã trung gian
• Trình biên dịch
• Bài giảng Trình biên dịch
• Ngôn ngữ lập trình
• Đặc tả ngôn ngữ lập trình
• Các giai đoạn của trình biên dịch
• Trình biên dịch trực tiếp cú pháp
• Phân tích ngữ nghĩa
• Biên dịch trực tiếp cú pháp
• Máy trừu tượng kiểu chồng
• Ngữ nghĩa của trình biên dịch
• Cú pháp của trình biên dịch
• Trình biên dịch đơn giản
• Thiết kế trình biên dịch
• Bộ xử lý ngôn ngữ
• Dịch trực tiếp cú pháp
• Định nghĩa trực tiếp cú pháp
• Đồ thị phụ thuộc
• Xây dựng cây cú pháp
• Kiểm tra kiểu
• Sinh mã cho lệnh gán
• Biểu thức logic
• Cấu trúc lập trình
• Quản lý dịch hại tổng hợp
• Giáo trình Quản lý dịch hại tổng hợp
• Xây dựng chương trình huấn luyện
• Huấn luyện quản lý dịch hại
• Quản lý dịch hại tổng hợp MĐ07
• Tiêu diệt dịch hại
• Văn phạm sản sinh
• Suy dẫn trái
• Suy dẫn phải
• Sơ đồ cú pháp
• Công thức siêu ngữ Backus
• Sơ đồ cú pháp của KPL
• Bộ phân tích từ vựng
• Từ tố của KPL
• Từ tố có cấu trúc cú pháp
• Bài toán phân tích cú pháp
• Giải thuật phân tích top down quay lui
• Ký hiệu không kết thúc A
• Điều kiện để thực hiện giải thuật
• Phân tích cú pháp tiền định
• bảng phân tích tiền định
• Văn phạm LL
• Văn phạm G phi ngữ cảnh
• Ngôn ngữ phi ngữ cảnh
• Phương pháp đệ quy trên xuống
• bộ phân tích cú pháp
• Bộ phân tích cú pháp KPL
• Cú pháp của lệnh KPL