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

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.
Nội dung trích xuất từ tài liệu:
Bài giảng Chương trình dịch: Bài 7 - Trương Xuân NamCHƯƠNG TRÌNH DỊCHBài 7: Các chiến lược phân tích cúphápNội dung1.2.3.4.Suy dẫnBiểu diễn suy dẫn bằng cấu trúc câyVăn phạm có nhập nhằngCá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 NAM2Phần 1Suy dẫnTRƯƠNG XUÂN NAM3Suy 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ếpsuy dẫn ra qua 0 hoặc nhiều bướcsuy 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 NAM4Suy 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ìmchuỗ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ũngphả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áinhấ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ảiTRƯƠNG XUÂN NAM5