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
Phần 1
Giới thiệu
 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
Phần 2
Ý tưởng cơ bản
 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
Phần 3
Mã minh họa
 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
Phần 4
Ví dụ
 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
Phần 5
Đánh giá thuật toán
 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
Phần 6
Bài tập
 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