Bài giảng Chương trình dịch: Bài 8 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 top-down đơn giản, đánh giá về top-down. | CHƯƠNG TRÌNH DỊCH Bài 8: Phân tích văn phạm bằng thuật toán top-down Nội dung 1. Ý tưởng & thuật toán 2. Ví dụ minh họa 3. Cài đặt top-down đơ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 Thử nghiệm 4. Đánh giá về top-down 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 Top-down: ý 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 Tìm suy dẫn từ S thành W. S E+S (S)+S (E+S)+S (1+S)+S (1+E+S)+S (1+2+S)+S (1+2+E)+S (1+2+(S))+S (1+2+(E+S))+S (1+2+(3+S))+S (1+2+(3+E))+S (1+2+(3+4))+S (1+2+(3+4))+E (1+2+(3+4))+5 TRƯƠNG XUÂN NAM 4 Top-down: ý tưởng Xét quá trình suy dẫn S W1 W2 W Wi luôn chứa ít nhất một non-terminal Xét X là non-terminal trái nhất của Wi: W không chứa non-terminal nên X sẽ phải “biến mất” Cách làm “biến mất” X chỉ có thể do sử dụng luật văn phạm mà vế trái là X Nhận xét: trước sau gì X cũng sẽ “biến mất” bởi một luật văn phạm có dạng X → α Top-down sử dụng năng lực tính toán của máy tính để tìm ra luật đó bằng phương pháp thử-sai-quay-lui TRƯƠNG XUÂN .