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

CHƯƠNG TRÌNH DỊCH
Bài 11: Phân tích văn phạm bằng 
thuật toán Earley
Nội dung
1. Giới thiệu
2. Ý tưởng cơ bản
3. Mã minh họa
4. Ví dụ
5. Đánh giá thuật toán
6. Bài tập
TRƯƠNG XUÂN NAM 2
Giới thiệu
Phần 1
TRƯƠNG XUÂN NAM 3
Tác giả Jay Earley
Được giới thiệu năm 1968 bởi 
Jay Earley (nhà khoa học máy 
tính và tâm lý học, người Mỹ)
 Công trình về phân tích văn 
phạm được đánh giá là một 
trong 25 bài báo xuất sắc nhất 
của tạp chí “Communications 
of the A.C.M” trong 1/4 thế kỷ
 Earley nổi tiếng hơn trong 
ngành tâm lý học lâm sàng, 
chuyên về trị liệu nhóm, tác 
giả của Pattern System
TRƯƠNG XUÂN NAM 4
Ý tưởng cơ bản
Phần 2
TRƯƠNG XUÂN NAM 5
Ý tưởng: automat tiến thẳng
Thuật toán Earley cụ thể hóa một automat tuyến tính 
không quay lui (đi từ trái qua phải)
 Trạng thái của automat: tập hợp các bộ quan sát, một bộ 
quan sát thực chất là một biến ghi nhận quá trình diễn 
tiến của việc phân tích văn phạm trong một tình huống 
cụ thể nào đó
 Khi nhận kí hiệu đầu vào, automat thực hiện việc cập 
nhật các bộ quan sát để xác định xem quá trình phân tích 
đã đến đâu
 Kết quả ở bước cuối cùng cho biết automat đoán nhận 
được những gì
TRƯƠNG XUÂN NAM 6
Ý tưởng: bộ quan sát
 Xét chuỗi vào w = w1w2wn
 Thuật toán sử dụng một automat xử lý từ trái sang 
phải (từ w1 sang đến wn)
 Thuật toán sử dụng dấu chấm để ngăn giữa 2 phần 
của luật sinh trong quá trình áp dụng luật đó
 Nói cách khác, khi viết A α • β, ta hiểu phần α đã phân 
tích xong, còn phần β thì chưa
 Một bộ quan sát [A α • β, i] có nghĩa đang xử lý 
luật A α • β từ vị trí wi trở đi
TRƯƠNG XUÂN NAM 7
Ý tưởng: tập các bộ quan sát
 Khi automat xét đến kí hiệu wm, có thể có nhiều 
phương án phân tích khác nhau, tất cả các phương 
án này đều được lưu lại để sử dụng trong các bước 
tính toán tiếp theo
 Tập hợp S(m): tập các bộ quan sát dừng tại vị trí m
 Như vậy, nếu [A α • β, i] thuộc S(m) có nghĩa là dãy 
wiwi+1wm được đoán nhận bởi phần α trong luật sinh 
A α • β
 Thuật toán cần phải sinh mọi thành phần trong S(m) 
trước khi chuyển sang kí hiệu wm+1
TRƯƠNG XUÂN NAM 8
Ý tưởng: quá trình tính toán
 Thuật toán sẽ tính lần lượt S(0), S(1),, S(n)
 Để dễ dàng thực hiện thuật toán, thuật toán bổ sung 
luật P S vào tập luật (gọi là start rule) và bổ sung 
bộ [P • S, 0] vào S(0)
 Khi nhận kí hiệu wm, automat sẽ bổ sung vào S(m) 
các bộ quan sát phù hợp, quá trình tính S(m) dừng 
khi không còn bộ quan sát nào có thể thêm vào
 Sau khi tính xong S(n), nếu bộ [P S •, 0] thuộc 
S(n) có nghĩa là dãy w1w2wn có thể sinh bởi S
TRƯƠNG XUÂN NAM 9
Ý tưởng: 3 lệnh cơ bản
1. Prediction (dự đoán): với mọi bộ [X α • Y β, j] 
thuộc S(k), ta tìm mọi luật sinh dạng Y γ và bổ 
sung bộ [Y • γ, k] vào S(k)
2. Scanning (xét duyệt): với kí hiệu kết thúc a = wk, 
tìm mọi bộ [X α • a β, j] thuộc S(k), bổ sung vào 
S(k+1) bộ [X α a • β, j]
3. Completion (hoàn thành): với mọi bộ [X γ •, j] 
thuộc S(k), tìm trong S(j) mọi bộ [Y α • X β, i], 
bổ sung [Y α X • β, i] vào S(k)
TRƯƠNG XUÂN NAM 10
Mã minh họa
Phần 3
TRƯƠNG XUÂN NAM 11
Mã minh họa: hàm chính
function EARLEY-PARSE(words, grammar)
ENQUEUE((γ → •S, 0), chart[0])
for i ← from 0 to LENGTH(words) do
for each state in chart[i] do
if INCOMPLETE?(state) then
if NEXT-CAT(state) is a nonterminal then
PREDICTOR(state, i, grammar)
else do
SCANNER(state, i)
else do
COMPLETER(state, i)
end
end
return chart
TRƯƠNG XUÂN NAM 12
Mã minh họa: 3 lệnh cơ bản
procedure PREDICTOR((A → α•B, i), j, grammar)
for each (B → γ) in GRAMMAR-RULES-FOR(B, grammar) do
ADD-TO-SET((B → •γ, j), chart[j])
end
procedure SCANNER((A → α•B, i), j)
if B ⊂ PARTS-OF-SPEECH(word[j]) then
ADD-TO-SET((B → word[j], i), chart[j + 1])
end
procedure COMPLETER((B → γ•, j), k)
for each (A → α•Bβ, i) in chart[j] do
ADD-TO-SET((A → αB•β, i), chart[k])
end
TRƯƠNG XUÂN NAM 13
Ví dụ
Phần 4
TRƯƠNG XUÂN NAM 14
Thuật toán Earley: ví dụ
Bộ luật:
P S // start rule
S S + M | M
M M * T | T
T 1 | 2 | 3 | 4
Chuỗi w = 2 + 3 * 4
TRƯƠNG XUÂN NAM 15
Thuật toán Earley: ví dụ
S(0): • 2 + 3 * 4
(1) P → • S (0) # start rule
(2) S → • S + M (0) # predict từ (1)
(3) S → • M (0) # predict từ (1)
(4) M → • M * T (0) # predict từ (3)
(5) M → • T (0) # predict từ (3)
(6) T → • number (0) # predict từ (5)
S(1): 2 • + 3 * 4
(1) T → number • (0) # scan từ S(0)(6)
(2) M → T • (0) # complete từ (1) và S(0)(5)
(3) M → M • * T (0) # complete từ (2) và S(0)(4)
(4) S → M • (0) # complete từ (2) và S(0)(3)
(5) S → S • + M (0) # complete từ (4) và S(0)(2)
(6) P → S • (0) # complete từ (4) và S(0)(1)
TRƯƠNG XUÂN NAM 16
Thuật toán Earley: ví dụ
S(1): 2 • + 3 * 4
(1) T → number • (0) # scan từ S(0)(6)
(2) M → T • (0) # complete từ (1) và S(0)(5)
(3) M → M • * T (0) # complete từ (2) và S(0)(4)
(4) S → M • (0) # complete từ (2) và S(0)(3)
(5) S → S • + M (0) # complete từ (4) và S(0)(2)
(6) P → S • (0) # complete từ (4) và S(0)(1)
S(2): 2 + • 3 * 4
(1) S → S + • M (0) # scan từ S(1)(5)
(2) M → • M * T (2) # predict từ (1)
(3) M → • T (2) # predict từ (1)
(4) T → • number (2) # predict từ (3)
TRƯƠNG XUÂN NAM 17
Thuật toán Earley: ví dụ
S(2): 2 + • 3 * 4
(1) S → S + • M (0) # scan từ S(1)(5)
(2) M → • M * T (2) # predict từ (1)
(3) M → • T (2) # predict từ (1)
(4) T → • number (2) # predict từ (3)
S(3): 2 + 3 • * 4
(1) T → number • (2) # scan từ S(2)(4)
(2) M → T • (2) # complete từ (1) và S(2)(3)
(3) M → M • * T (2) # complete từ (2) và S(2)(2)
(4) S → S + M • (0) # complete từ (2) và S(2)(1)
(5) S → S • + M (0) # complete từ (4) và S(0)(2)
(6) P → S • (0) # complete từ (4) và S(0)(1)
TRƯƠNG XUÂN NAM 18
Thuật toán Earley: ví dụ
S(3): 2 + 3 • * 4
(1) T → number • (2) # scan từ S(2)(4)
(2) M → T • (2) # complete từ (1) và S(2)(3)
(3) M → M • * T (2) # complete từ (2) và S(2)(2)
(4) S → S + M • (0) # complete từ (2) và S(2)(1)
(5) S → S • + M (0) # complete từ (4) và S(0)(2)
(6) P → S • (0) # complete từ (4) và S(0)(1)
S(4): 2 + 3 * • 4
(1) M → M * • T (2) # scan từ S(3)(3)
(2) T → • number (4) # predict từ (1)
TRƯƠNG XUÂN NAM 19
Thuật toán Earley: ví dụ
S(4): 2 + 3 * • 4
(1) M → M * • T (2) # scan từ S(3)(3)
(2) T → • number (4) # predict từ (1)
S(5): 2 + 3 * 4 •
(1) T → number • (4) # scan từ S(4)(2)
(2) M → M * T • (2) # complete từ (1) và S(4)(1)
(3) M → M • * T (2) # complete từ (2) và S(2)(2)
(4) S → S + M • (0) # complete từ (2) và S(2)(1)
(5) S → S • + M (0) # complete từ (4) và S(0)(2)
(6) P → S • (0) # complete từ (4) và S(0)(1)
Bộ [P → S •, 0] thuộc S(5), như vậy có thể kết luận 
chuỗi w được suy dẫn từ P
TRƯƠNG XUÂN NAM 20
Đánh giá thuật toán
Phần 5
TRƯƠNG XUÂN NAM 21
Đánh giá chung
 Nhiều phiên bản cài đặt sau này có sửa đổi chút ít 
so với thuật toán gốc (thuật toán được giới thiệu 
trong slide này cũng không phải thuật toán gốc)
 Là một sự kết hợp thông minh của 3 trường phái
 Tiếp cận top-down (bước prediction)
 Tiếp cận bottom-up (bước scanning và completion)
 Quy hoạch động (lưu lại trạng thái để dùng lại)
 Không bị hạn chế văn phạm đầu vào
 Do là top-down nên không bị hạn chế bởi suy dẫn rỗng
 Dùng quy hoạch động không bị hạn chế bởi ký hiệu đệ 
quy (hoặc đệ quy trái)
TRƯƠNG XUÂN NAM 22
Độ phức tạp tính toán
 Làm việc trực tiếp với luật dạng CFG: không cần 
phải tách thành các luật chuẩn Chomsky, vì vậy 
kích cỡ tập luật không quá lớn
 Trong tình huống tổng quát: có độ phức tạp tính 
toán O(n3) với n là độ dài chuỗi vào
 Nếu văn phạm không có nhập nhằng: độ phức tạp 
tính toán cỡ O(n2)
 Nếu văn phạm đơn giản (dạng LL, LR,): độ phức 
tạp cận tuyến tính ~O(n)
 Thực hiện đặc biệt tốt nếu văn phạm đệ quy trái
TRƯƠNG XUÂN NAM 23
Bài tập
Phần 6
TRƯƠNG XUÂN NAM 24
Bài tập
1. Chỉ ra kết quả các bước thực hiện thuật toán Earley với 
w = aaabbb và văn phạm G sau:
S → AB | XB X → AT
T → AB | XB A→ a B → b
2. Chỉ ra kết quả các bước thực hiện thuật toán Earley với 
w = abaab và văn phạm G sau:
S AA | AS | b A SA | AS | a
3. Chỉ ra kết quả các bước thực hiện thuật toán Earley với 
w = axaxyby và văn phạm G sau:
S a X Y | a X Y b Y X x Y S | y
TRƯƠNG XUÂN NAM 25