Bài giảng Chương trình dịch - Bài 10: Phân tích văn phạm bằng thuật toán CYK - Trương Xuân Nam

CHƯƠNG TRÌNH DỊCH
Bài 10: Phân tích văn phạm bằng 
thuật toán CYK
Nội dung
1. Khắc phục hạn chế của các phương pháp thử-sai
2. Các phương pháp phân tích cú pháp vạn năng
3. Áp dụng quy hoạch động vào phân tích cú pháp
4. Thuật toán Cocke – Younger – Kasami (CYK)
 Dạng chuẩn Chomsky (CNF)
 Ý tưởng
 Mã minh họa
 Đánh giá thuật toán
5. Bài tập
TRƯƠNG XUÂN NAM 2
Khắc phục hạn chế của các 
phương pháp thử-sai
Phần 1
TRƯƠNG XUÂN NAM 3
Các hạn chế của thử-sai
 Hai thuật toán thử-sai cơ bản top-down và bottom-
up đều có những hạn chế về văn phạm đầu vào
 Top-down: văn phạm không có đệ quy trái
 Bottom-up: văn phạm không có suy dẫn rỗng và không 
có kí hiệu đệ quy (A⇒+ A)
 Các thuật toán thử-sai có hạn chế về mặt tốc độ
 Tốc độ chấp nhận được với một số văn phạm đơn giản 
và đơn nghĩa, đầu vào ngắn
 Trường hợp xấu có độ phức tạp tính toán hàm mũ
 Không có cơ chế hiệu quả loại bỏ sự trùng lặp về 
kết quả (chẳng hạn như nhiều suy dẫn tương đương)
TRƯƠNG XUÂN NAM 4
Các hạn chế của thử-sai
 Nguyên nhân của những hạn chế này
 Hạn chế do bản thân cơ chế hoạt động của thử-sai
 Không có cơ chế loại bỏ các phương án chắc-chắn-sai
 Ví dụ: quá trình suy dẫn S thành w = abcdefg
S ⇒⇒ abcAx ⇒ ⇒ abcdefg
 Ta nhận thấy phương án có chuỗi trung gian abcAx
hoàn toàn không thể đạt được chuỗi w mong muốn
 Vì x là kí hiệu không kết thúc, nó luôn luôn tồn tại trong 
các suy dẫn tiếp theo, trong khi chuỗi w không chứa x
 Câu hỏi: thuật toán thử sai tốt ~ cắt nhánh sớm?
TRƯƠNG XUÂN NAM 5
Các phương pháp phân tích cú 
pháp vạn năng
Phần 2
TRƯƠNG XUÂN NAM 6
Phương pháp phân tích vạn năng
 Như vậy các thuật toán thử-sai có 2 điểm yếu
1. Hệ luật văn phạm bị hạn chế
2. Yêu cầu nhiều thời gian tính toán 
 Vì vậy chúng ta cũng có 2 mục tiêu
1. Tạo ra thuật toán phân tích vạn năng (không bị hạn chế 
bởi luật văn phạm)
2. Tạo ra thuật toán phân tích tốc độ cao
 Tất nhiên nếu có thuật toán đạt được cả 2 mục tiêu 
trên thì quá tốt
 Trong phần này ta nhắm tới mục tiêu thứ nhất
TRƯƠNG XUÂN NAM 7
Phương pháp phân tích vạn năng
 Có 2 chiến lược:
1. Biến đổi văn phạm G thành văn phạm G’ tương đương 
nhưng không có những hạn chế của thuật toán
2. Thay đổi cơ chế của thuật toán, nói cách khác là không 
sử dụng cơ chế thử-sai hiện có
 Chiến lược thứ nhất không có lời giải trọn vẹn
 Thuật toán khử đệ quy trái có thể thay đổi ý nghĩa của 
văn phạm, kết quả là văn phạm G’ thực chất không hoàn 
toàn tương đương G
 Khử suy dẫn rỗng hoặc kí hiệu đệ quy làm cho văn 
phạm khó hiểu, các kí hiệu trung gian mất ý nghĩa ban 
đầu của nó
TRƯƠNG XUÂN NAM 8
Áp dụng quy hoạch động vào 
phân tích cú pháp
Phần 3
TRƯƠNG XUÂN NAM 9
Ý tưởng quy hoạch động
 Quy hoạch động gồm hai ý tưởng cơ bản
 Chia bài toán lớn thành các bài toán con độc lập
 Sử dụng bộ nhớ để lưu trữ lại các lời giải của các bài 
toán con (để tránh việc phải giải nhiều lần một bài toán)
 Áp dụng vào bài toán phân tích văn phạm
 Cây phân tích S ⇒* w thực chất gồm các cây con, mỗi 
cây con phân tích một chuỗi con liên tiếp trong w
 Sử dụng bộ nhớ để lưu trữ lại các kết quả suy dẫn ra các 
chuỗi con của w (có nhiều chiến lược, chẳng hạn như 
lưu trữ các chuỗi từ wiwi+1wj hoặc chuỗi w0w1wk, 
tùy vào mục tiêu cần lưu trữ)
TRƯƠNG XUÂN NAM 10
Thuật toán Cocke – Younger –
Kasami (CYK)
Phần 4
TRƯƠNG XUÂN NAM 11
Dạng chuẩn Chomsky (CNF)
 Văn phạm phi ngữ cảnh ở dạng chuẩn Chomsky 
nếu mọi luật sinh đều có dạng A → BC hoặc A → a
 Dễ thấy mọi văn phạm phi ngữ cảnh không chứa 
suy dẫn rỗng (A → ) đều có thể chuyển về dạng 
chuẩn Chomsky bằng thuật toán đơn giản sau
 Nếu luật sinh sẵn ở dạng chuẩn Chomsky thì giữ nguyên
 Nếu luật sinh không ở dạng chuẩn Chomsky thì sẽ có 
dạng A → B1B2Bn, với n > 2
• Ta bổ sung các kí hiệu trung gian mới C1, C2,, Cn-2
• Thay thế luật trên bằng các luật mới A → C1Bn, C1 → C2Bn-1, 
Cn-2 → B1B2, các luật mới này thỏa mãn chuẩn Chomsky
TRƯƠNG XUÂN NAM 12
Thuật toán CYK: ý tưởng
 CYK không phải là thuật toán vạn năng vì không 
chấp nhận văn phạm có suy dẫn rỗng
 CYK minh họa một cách đơn giản ý tưởng quy 
hoạch động:
 Giả thiết chuỗi w = w1w2wn
 Ta định nghĩa tập Xij là tập tất cả các kí hiệu có thể suy 
dẫn ra chuỗi con wiwi+1wi+j-1 (chuỗi con bắt đầu từ wi
và có độ dài j)
 Bài toán đoán nhận S ⇒* w tương đương với việc trả lời 
S có thuộc tập X1n hay không?
 Vấn đề bây giờ là tính Xij như thế nào?
TRƯƠNG XUÂN NAM 13
Thuật toán CYK: mã minh họa
// tính X của các chuỗi độ dài 1
for (int i = 1; i <= n; i++)
X[i,1] = { A | A → wi }
// tính X của các chuỗi độ dài 2,3,,n
for (int j = 2; j <= n; j++)
for (int i = 1; i <= n-j+1; i++) {
X[i,j] = {}
for (int k = 1; k <= j-1; k++)
X[i,j] += { A | nếu A → BC
| và B thuộc X[i,k]
| và C thuộc X[i+k,j-k] }
}
TRƯƠNG XUÂN NAM 14
Thuật toán CYK: ví dụ
Văn phạm:
S → AB | BC
A → BA | a
B → CC | b
C → AB | a
Chuỗi w = baaba
TRƯƠNG XUÂN NAM 15
Thuật toán CYK: đánh giá
 Hạn chế:
 Thuật toán không làm việc với suy dẫn rỗng
 Số lượng kí hiệu trung gian (non-terminal) nhiều, do 
việc chuyển đổi từ CFG sang chuẩn Chomsky
 Độ phức tạp tính toán (xấu nhất) là O(n3 x |G|)
 Số n là độ dài của chuỗi w
 |G| là kích thước của văn phạm dạng CNF
 Bản chất là ý tưởng bottom-up nhưng áp dụng các 
kĩ thuật quy hoạch động
 Dễ dàng liệt kê mọi cây phân tích khác nhau và loại 
bỏ các suy dẫn trùng lặp
TRƯƠNG XUÂN NAM 16
Bài tập
Phần 5
TRƯƠNG XUÂN NAM 17
Bài tập
1. Cho văn phạm G:
S → AB | XB
T → AB | XB
X → AT
A→ a
B → b
Chỉ ra quá trình thực hiện thuật toán CYK với w = aaabbb
2. Cho văn phạm G:
S AA | AS | b
A SA | AS | a
Chỉ ra quá trình thực hiện thuật toán CYK với w = abaab
TRƯƠNG XUÂN NAM 18
Bài tập
3. Sử dụng thuật toán CYK để chỉ ra cây phân tích cho 
chuỗi (5+7)*3 thuộc văn phạm G
E→ E + T | T
T→ T * F | F
F→ ( E ) | số
4. Chỉ ra cây phân tích của chuỗi true and not false sinh 
bởi thuật toán CYK với tập luật văn phạm G
E→ E and T | T
T→ T or F | F
F→ not F | ( E ) | true | false
TRƯƠNG XUÂN NAM 19