Bài giảng Chương trình dịch - Bài 7: Các chiến lược phân tích cú pháp - Trương Xuân Nam

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. Suy dẫn
2. Biểu diễn suy dẫn bằng cấu trúc cây
3. Văn phạm có nhập nhằng
4. 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 NAM 5
Suy dẫn trái và suy dẫn phải
. Cho văn phạm G với các luật sinh:
 S → E + S | E
 E → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ( S )
. Xâu vào: W = (1 + 2 + (3 + 4)) + 5
. Suy dẫn trái từ S thành W như sau:
 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 6
Suy dẫn trái và suy dẫn phải
. Suy dẫn phải từ S thành W như sau:
 S E + S E + E E + 5 ( S ) + 5 ( E + S ) + 5 
 ( E + E + S ) + 5 ( E + E + E ) + 5
 ( E + E + ( S ) ) + 5 ( E + E + ( E + S ) ) + 5
 ( E + E + ( E + E ) ) + 5 ( E + E + ( E + 4 ) ) + 5
 ( E + E + ( 3 + 4 ) ) + 5 ( E + 2 + ( 3 + 4 ) ) + 5
 ( 1 + 2 + ( 3 + 4 ) ) + 5
. Câu hỏi: qua các ví dụ về quá trình biến đổi từ S thành 
 W, chúng ta nên sử dụng cách mã hóa như thế nào để 
 lưu trữ quá trình suy dẫn và sử dụng các thông tin đó để 
 in ra quá trình suy dẫn như thế nào?
 TRƯƠNG XUÂN NAM 7
Phần 2
Biểu diễn suy dẫn bằng cấu 
trúc cây
 TRƯƠNG XUÂN NAM 8
Cây phân tích (parse tree)
 S
. Cây phân tích thể hiện cấu trúc 
 S
 của một suy dẫn E +
 . Nút gốc là kí hiệu bắt đầu ( S ) E
 . Các nút lá luôn là kí hiệu kết thúc E + S 5
 . Các nút trong luôn là các kí hiệu 
 1 E + S
 trung gian
 . Cây không thể hiện thứ tự thực 2 E
 hiện các suy dẫn trực tiếp ( S )
 • Việc duyệt cây sẽ tạo thành thứ tự thực 
 hiện suy dẫn E + S
 • Suy dẫn trái tương đương với quá trình 3 E
 duyệt cây theo thứ tự giữa-trái-phải
 4
 TRƯƠNG XUÂN NAM 9
Cây cú pháp trừu tượng
 S
. Cây cú pháp trừu tượng (abstract 
 syntax tree) loại bỏ các thông tin E + S
 không cần thiết của cây phân tích ( S ) E
 . Minh họa quá trình nhóm các kí 
 hiệu với nhau E + S 5
 . Thích hợp với việc thực hiện tính 1 E + S
 toán và tổ hợp thông tin
 + 2 E
 + 5 ( S )
 1 + E + S
 2 + 3 E
 3 4 4
 TRƯƠNG XUÂN NAM 10
Suy dẫn vs các cấu trúc cây
. Suy dẫn là cách biểu diễn thông tin 1 chiều
. Cấu trúc cây là cách biểu diễn thông tin 2 chiều
. Cấu trúc cây minh họa tương quan giữa các thành 
 phần trong một cấu trúc không gian
. Cây phân tích mô tả đầy đủ nhất việc biến đổi từ kí 
 hiệu gốc thành chuỗi cần phân tích, phù hợp nhất 
 cho mọi mục đích sử dụng
. Cây cú pháp gạt bỏ các thành phần trung gian, tập 
 trung mô tả tương quan giữa các kí hiệu kết thúc, 
 cấu trúc này phù hợp với việc tổ hợp thông tin
 TRƯƠNG XUÂN NAM 11
Phần 3
Văn phạm có nhập nhằng
 TRƯƠNG XUÂN NAM 12
Văn phạm có nhập nhằng
. Một văn phạm thiếu chặt chẽ dẫn tới việc có nhiều 
 cây phân tích khác nhau với một chuỗi đầu vào
. Ví dụ văn phạm: S → S + S | S * S | number
. Phân tích xâu vào: 1 + 2 * 3
. Kết quả 1: +
 S S + S 1 + S 1 + S * S 1 *
 1 + 2 * S 1 + 2 * 3
 2 3
. Kết quả 2:
 S S * S S + S * S 1 + S * S *
 1 + 2 * S 1 + 2 * 3 + 3
 1 2
 TRƯƠNG XUÂN NAM 13
Văn phạm có nhập nhằng
. Văn phạm tồn tại ít nhất một chuỗi w có từ 2 cây 
 phân tích tương ứng trở lên gọi là văn phạm có 
 nhập nhằng
. Vấn đề lớn nhất của văn phạm có nhập nhằng là 
 tính đa nghĩa của chuỗi w (có nhiều cách hiểu), hệ 
 quả là không thể tính chính xác ngữ nghĩa của w
 + *
 1 * = 7 + 3 = 9
 2 3 1 2
 TRƯƠNG XUÂN NAM 14
Khử nhập nhằng
. Việc khử nhập nhằng thực ra tạo một văn phạm mới 
 dựa trên văn phạm cũ nhưng hai văn phạm không 
 hoàn toàn tương đương
. Có nhiều chiến lược khử nhập nhằng
 . Thêm vào các biến trung gian
 . Đưa ra các ràng buộc ngoài văn phạm (ví dụ như quy 
 định mức độ ưu tiên của các phép toán)
. Ví dụ văn phạm: S → S + S | S * S | number
. Khử nhập nhằng bằng cách thêm biến trung gian:
 S → S + T | T
 T → T * number | number
 TRƯƠNG XUÂN NAM 15
Phần 4
Các chiến lược phân tích cú 
pháp
 TRƯƠNG XUÂN NAM 16
Các chiến lược phân tích cú pháp
. Chiến lược phân tích cú pháp chia thành 3 nhóm:
 . 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,
. Ngoài ra còn có một số phương pháp khác dựa trên 
 đặc điểm của ngôn ngữ để áp dụng các kĩ thuật hiệu 
 quả (ví dụ như phân tích theo thứ bậc toán tử)
. Một số phương pháp tổng quát (như Earley chẳng 
 hạn), nhưng đa số các phương pháp chỉ làm việc với 
 những văn phạm có đặc thù riêng
 TRƯƠNG XUÂN NAM 17
Chiến lược thử-sai
. Chiến lược thử-sai hay là quay lui được nghĩ tới đầu 
 tiên khi giải quyết bài toán phân tích văn phạm
. Các chiến lược này đơn giản là thử áp dụng các luật 
 suy dẫn cho tới khi đạt được chuỗi suy dẫn mục tiêu
. Chia thành 2 cách tiếp cận ngược nhau:
 . Phương pháp top-down:
 • Nhìn từ cây phân tích thì đi từ trên xuống
 • Cố gắng từ S biến đổi dần ra w
 . Phương pháp bottom-up:
 • Nhìn từ cây phân tích thì đi từ dưới lên
 • Cố gắng thu gọn từ w về S
 TRƯƠNG XUÂN NAM 18
Chiến lược thử-sai
. Cả hai phương pháp này đều có hạn chế về văn 
 phạm đầu vào:
 . Top-down yêu cầu văn phạm đầu vào không đệ quy trái
 . Bottom-up yêu cầu văn phạm đầu vào không có sản xuất 
 rỗng (A → ) và không có suy dẫn dạng A + A
. Các chiến lược này chỉ có ý nghĩa về mặt lý thuyết 
 vì chậm và hạn chế văn phạm, tuy nhiên quá trình 
 thử-sai đem lại nhiều gợi ý cho các thuật toán khác
 . Loại bỏ hạn chế văn phạm: các phương pháp vạn năng
 . Loại bỏ sự quay lui: các phương pháp tất định
 TRƯƠNG XUÂN NAM 19
Chiến lược quy hoạch động
. Ý tưởng quy hoạch động nhắm tới mục tiêu:
 . Xây dựng các phương pháp không có hạn chế về văn 
 phạm đầu vào
 . Lưu trữ lại các chuỗi con đã phân tích để tránh phải 
 quay lui
. Thuật toán CYK:
 . Cần biến đổi văn phạm về dạng chuẩn Chomsky
 . Văn phạm không có suy dẫn rỗng
 . Không quay lui
. Thuật toán Earley: vạn năng hơn, không có ràng 
 buộc về văn phạm, không quay lui
 TRƯƠNG XUÂN NAM 20
Chiến lược tất định
. Ý tưởng tất định đi theo lựa chọn khác: hi sinh sự 
 phong phú của văn phạm để đổi lấy tốc độ
. Đặc điểm chung:
 . Các văn phạm có sự ràng buộc nhất định
 . Dựa trên phân tích trước văn phạm để tiên đoán các tình 
 huống có thể xảy ra
 . Xây dựng các bảng phương án, trong đó chỉ ra việc cần 
 thực hiện khi gặp các tình huống cụ thể
. Đây là chiến lược mà tất cả các chương trình dịch 
 đều sử dụng do ưu thế về tốc độ (không quay lui)
 TRƯƠNG XUÂN NAM 21