Bài giảng Chương trình dịch: Bài 7 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: Suy dẫn, biểu diễn suy dẫn bằng cấu trúc cây, văn phạm có nhập nhằng, các chiến lược phân tích cú pháp. | CHƯƠNG TRÌNH DỊCH Bài 7: Các chiến lược phân tích cú pháp Nội dung 1. 2. 3. 4. Suy dẫn Biểu diễn suy dẫn bằng cấu trúc cây Văn phạm có nhập nhằng Các chiến lược phân tích cú pháp Chiến lược thử-sai (quay lui): top-down, bottom-up Chiến lược quy hoạch động: CYK, Earley, Chiến lược tất định (deterministic): LL, LR, TRƯƠNG XUÂN NAM 2 Phần 1 Suy dẫn TRƯƠNG XUÂN NAM 3 Suy dẫn Khái niệm: αAβ ⇒ αγβ (gọi là αAβ suy dẫn ra αγβ) nếu A → γ là một luật sinh, α và β là các chuỗi ký hiệu thuộc ngôn ngữ L nào đó Nếu α1 ⇒ α2 ⇒ ⇒ αn ta nói α1 suy dẫn ra αn Hệ thống kí hiệu: ⇒ ⇒* ⇒+ suy dẫn trực tiếp suy dẫn ra qua 0 hoặc nhiều bước suy dẫn ra qua 1 hoặc nhiều bước Một số tính chất: α ⇒* α với ∀α α ⇒* β và β ⇒* γ thì α ⇒* γ TRƯƠNG XUÂN NAM 4 Suy dẫn trái và suy dẫn phải Bài toán phân tích cú pháp thực chất là bài toán tìm chuỗi suy dẫn S ⇒* α ⇒* β, trong đó: S là kí hiệu gốc α là chuỗi có chứa kí hiệu trung gian β là chuỗi chỉ gồm các kí hiệu kết thúc Dễ nhận thấy trong quá trình suy dẫn trên: Có nhiều phương án suy dẫn từ S thành β Một kí hiệu trung gian thuộc α thì trước sau gì nó cũng phải bị biến đổi bởi một luật sinh nào đó Nếu kí hiệu trung gian được chọn để biến đổi luôn là trái nhất của α thì ta gọi phương án này là suy dẫn trái Định nghĩa tương tự cho suy dẫn phải TRƯƠNG XUÂN .
