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
Suy dẫn
Phần 1
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
Biểu diễn suy dẫn bằng cấu 
trúc cây
Phần 2
TRƯƠNG XUÂN NAM 8
Cây phân tích (parse tree)
 Cây phân tích thể hiện cấu trúc 
của một suy dẫn
 Nút gốc là kí hiệu bắt đầu
 Các nút lá luôn là kí hiệu kết thúc
 Các nút trong luôn là các kí hiệu 
trung gian
 Cây không thể hiện thứ tự thực 
hiện các suy dẫn trực tiếp
• Việc duyệt cây sẽ tạo thành thứ tự thực 
hiện suy dẫn
• Suy dẫn trái tương đương với quá trình 
duyệt cây theo thứ tự giữa-trái-phải
S
E + S
E
4
( S )
E + S
E + S
E
( S )
E + S
2
1
3
E
5
TRƯƠNG XUÂN NAM 9
Cây cú pháp trừu tượng
 Cây cú pháp trừu tượng (abstract 
syntax tree) loại bỏ các thông tin 
không cần thiết của cây phân tích
 Minh họa quá trình nhóm các kí 
hiệu với nhau
 Thích hợp với việc thực hiện tính 
toán và tổ hợp thông tin
S
E + S
E
4
( S )
E + S
E + S
E
( S )
E + S
2
1
3
E
5
+
+
+
+
1
2
3 4
5
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
Văn phạm có nhập nhằng
Phần 3
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 + 2 * S 1 + 2 * 3
 Kết quả 2:
S S * S S + S * S 1 + S * S
 1 + 2 * S 1 + 2 * 3
+
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 *
2 3
*
3+
1 2
= 7 = 9
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
Các chiến lược phân tích cú 
pháp
Phần 4
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