Bài giảng Chương trình dịch: Bài 9 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: Ý tưởng & thuật toán, ví dụ minh họa, cài đặt bottom-up đơn giản, đánh giá về bottom-up. | CHƯƠNG TRÌNH DỊCH Bài 9: Phân tích văn phạm bằng thuật toán bottom-up Nội dung 1. Ý tưởng & thuật toán 2. Ví dụ minh họa 3. Cài đặt bottom-up đơn giản Cấu trúc một luật văn phạm Cấu trúc một suy diễn trực tiếp Máy phân tích: các hàm hỗ trợ Máy phân tích: các hàm chính 4. Đánh giá về bottom-up 5. Bài tập TRƯƠNG XUÂN NAM 2 Phần 1 Ý tưởng & thuật toán TRƯƠNG XUÂN NAM 3 Bottom-up: ý tưởng Cho văn phạm G với các luật sinh: S→E+S|E E→1|2|3|4|5|(S) Xâu vào: W = (1 + 2 + (3 + 4)) + 5 Thu gọn W thành S: (1+2+(3+4))+5 (E+2+(3+4))+5 (E+E+(3+4))+5 (E+E+(E+4))+5 (E+E+(E+E))+5 (E+E+(E+S))+5 (E+E+(S))+5 (E+E+E)+5 (E+E+S)+5 (E+S)+5 (S)+5 E+5 E+E E+S S TRƯƠNG XUÂN NAM 4 Bottom-up: mục tiêu & ý tưởng Mục tiêu: trong số nhiều suy dẫn dạng S * w, thuật toán sẽ tìm suy dẫn phải Ý tưởng chính: Thử sai và quay lui bằng năng lực tính toán của máy tính Dò ngược quá trình suy dẫn w wn-1 w1 S bằng kĩ thuật thu-gọn: tìm xem wi có chứa vế phải của luật hay không, nếu có thì thay thế phần vế phải đó bằng vế trái tương ứng Nếu một wi S thì chắc chắn nó cần phải được thu-gọn, nếu wi không chứa vế phải của luật nào đó thì nhánh thử sai này cần quay lui, ngược lại thì thu-gọn và thử tiếp TRƯƠNG XUÂN .
