Bài giảng Xử lý ngôn ngữ tự nhiên (Natural Language Processing) - Bài: Phân tích cú pháp - Lê Thanh Hương

Nội dung text: Bài giảng Xử lý ngôn ngữ tự nhiên (Natural Language Processing) - Bài: Phân tích cú pháp - Lê Thanh Hương

1. Bài toán PTCP cây PTCP mẫu Phân tích cú pháp P T tính độ chính xác Lê Thanh Hương C điểm câu Bộ môn Hệ thống Thông tin P Các bộ PTCP Viện CNTT &TT – Trường ĐHBKHN cây cú pháp hiện nay có độ Email: huonglt-fit@mail.hut.edu.vn Văn phạm chính xác cao (Eisner, Collins, Charniak, etc.) 1 2 Khái niệm về văn phạm Văn phạm z Phân tích câu “Bò vàng gặm cỏ non” z Một văn phạm sản sinh là một hệ thống z Cây cú pháp: z G = ( T, N, S, R ), trong đó z Tập luật z T (terminal) – tập ký hiệu kết thúc z C Æ CN VN z N (non terminal) – tập ký hiệu không kết thúc z CN Æ DN z S (start) – ký hiệu khởi đầu z VN Æ ĐgN z R (rule) – tập luật z ĐgN Æ ĐgT DN z R = { α Æ β | α, β∈(T∪N) } z DN Æ DT TT z α Æ β gọi là luật sản xuất 3 4 Dạng chuẩn Chomsky Nhắc lại về văn phạm z Văn phạm: 1 tập luật viết lại z Mọi NNPNC không chứa ε đều có thể sinh từ z Ký hiệu kết thúc: các ký hiệu không thể phân rã được một văn phạm tnđó mọi sản xuất đều có nữa. z Ký hiệu không kết thúc: các ký hiệu có thể phân rã dạng A Æ BC hoặc A Æ a, với A,B,C∈N và a được. ∈T z Xét văn phạm G: z Ví dụ: Tìm dạng chuẩn Chomsky cho văn S → NP VP phạm G với T = {a,b}, N ={S,A,B}, R như sau: NP → John, garbage VP → laughed, walks z S Æ bA|aB z A ÆbAA|aS|a G có thể sinh ra các câu sau: John laughed. John walks. z B Æ aBB|bS|b Garbage laughed. Garbage walks. 5 6
2. Áp dụng tập luật ngữ pháp Cấu trúc đoạn đệ qui z S → NP VP → DT NNS VBD → The children sleptp z S → NP VP → DT NNS VBD NP → DT NNS VBD DT NN → The children ate the cake 13 14 Văn phạm cho ngôn ngữ tự nhiên S có nhập nhằng PTCP kiểu trên xuống NP VP John saw snow on the campus . z Hướng đích S Nhập nhằng - PP z Khởi đầu với 1 danh sách các ký hiệu cần triển khai (S, có thể gắn tại 2 điểm (với VP NP,VP, ) hoặc với NP) z Viết lại các đích trong tập đích bằng cách: NP VP z tìm luật có vế trái trùng với đích cần triển khai z triểu khai nó với vế phải luật, tìm cách khớp với câu đầu vào 1 saw NP 2 snow z Nếu 1 đích có nhiều cách viết lại Æ chọn 1 luật để áp 0 John PP dụng (bài toán tìm kiếm) NP z Có thể sử dụng tìm kiếm rộng (breadth-first search) hoặc 3 on tìm kiếm sâu (depth-first search) 4 the 5 campus 6 15 16 Khó khăn với PTCP trên xuống S PTCP dưới lên NP VP z Các luật đệ qui trái z PTCP trên xuống rất bất lợi khi có nhiều luật có cùng vế trái . z Hướng dữ liệu z Khởi tạo với xâu cần phân tích z Nếu chuỗi trong tập đích phù hợp với vế phải của 1 luật S→NP X1 S→NP X2 S→NP X600 S→VP Y1 → thay nó bằng vế trái củalua luật. z Kết thúc khi tập đích = {S}. z Nhiều thao tác thừa: triển khai tất cả các nút có thể phân tích trên z Nếu vế phải của các luật khớp với nhiều luật trong tập xuống đích, cần lựa chọn luật áp dụng (bài toán tìm kiếm) z PTCP trên xuống sẽ làm việc tốt khi có chiến lược điều khiển ngữ z Có thể sử dụng tìm kiếm rộng (breadth-first search) hoặc pháp phù hợp tìm kiếm sâu (depth-first search) z PTCP trên xuống không thể triển khai các ký hiệu tiền kết thúc thành các ký hiệu kết thúc. Trên thực tế, người ta thường sử dụng phương pháp dưới lên để làm việc này. 17 18 z Lặp lại công việc: bất cứ chỗ nào có cấu trúc giống nhau
3. CKY phải sử dụng luật nhị CKY chart phân “ The guy ate the ice-cream on the table” 12345 678 z Chuyển VP→V NP PP thành: 0DT 8.a. VP→V Arguments 1NN 8. b. Arguments → NP PP 2 VBD 3DT 4NN 5IN 6DT 7NN 25 26 5. NP → NN PP Nhập nhằng! 8.a. VP→V Arguments Áp dụng thao tác ‘dán’ 8.b. Arguments → NP PP 12 3 45 6 7 8 12 3 45 6 7 8 0DTNP S 0DTNP 1NN 1NN 2 VBD VP 2 VBD 3DTNPNP, 3DT Args 4NN 4NN 5IN 5INPP 6DT6DTNP 7NN7NN 27 28 Thuật toán Earley (top-down) Ví dụ z Tìm các nhãn và các nhãn thiếu (partial constituents) từ đầu vào ROOT → SNP→ Papa z A → B C . D E là nhãn thiếu: S → NP VP N → caviar A A + D = NP → Det N N → spoon NP → NP PP V → ate BC DE BC DE VP → VP PP P → with VP → V NP Det → the PP → P NP Det → a A → B C . D E A → B C D . E 29 30 z Tiến hành dần từ trái sang phải
4. Thuật toán Earley 0 khởi tạo 0 ROOT . S z Thuật toán Earley giống thuật toán đệ qui nói trên, nhưng giải quyết được vấn đề đệ qui trái. z Sử dụng bảng phân tích giống thuật toán CKY, nhằm lưu lại các tương đương với (0, ROOT → . S) thông tin đã tìm thấy Æ lập trình động “Dynamic programming.” Các thao tác của thuật toán z Xử lý phần đi sau dấu . theo kiểu đệ qui : z Nếu là từ, quét (scan) đầu vào để xem có phù hợp không z Nếu là ký hiệu không kết thúc, đoán (predict) các khả năng để khớp nó (giảm số phép tiên đoán bằng cách nhìn trước k ký hiệu từ đầu vào và chỉ sử dụng các luật phù hợp với k ký hiệu đó) z Nếu rỗng, ta đã hoàn thành một thành phần ngữ pháp, gắn (attach) nó vào những chỗ liên quan 37 38 0 0 0 ROOT . S predict luật có vế trái là S 0 ROOT . S 0 S . NP VP 0 S . NP VP predict luật có VT = NP 0 NP . Det N (có 3 luật phù hợp) (0, S → . NP VP) 0 NP . NP PP 0 NP . Papa 39 40 0 0 0 ROOT . S 0 ROOT . S 0 S . NP VP 0 S . NP VP 0 NP . Det N predict luật có VT = Det (2 luật) 0 NP . Det N 0 NP . NP PP 0 NP . NP PP predict luật có VT = NP 0 NP . Papa 0 NP . Papa ta đã làm việc này ở bước trước, vì vậy không làm lại! 0 De t . the 0 De t . the Chú ý: ta ph ảiilàml làm lạiivi việccnàyv này vớiilu luật đệ qui trái 0 Det . a 0 Det . a 41 42
5. 0 Papa 1 0 Papa 1 0 ROOT . S 0 NP Papa . 0 ROOT . S 0 NP Papa . 0 S . NP VP 0 S NP . VP 0 S . NP VP 0 S NP . VP 0 NP . Det N 0 NP NP . PP 0 NP . Det N 0 NP NP . PP 0 NP . NP PP 1 VP . V NP predict 0 NP . NP PP 1 VP . V NP 0 NP . Papa 1 VP . VP PP 0 NP . Papa 1 VP . VP PP predict 0 De t . the 1 PP . P NP 0 De t . the 1 PP . P NP 0 Det . a 1 V . ate 0 Det . a 1 V . ate 49 50 0 Papa 1 0 Papa 1 ate 2 0 ROOT . S 0 NP Papa . 0 ROOT . S 0 NP Papa . 1 V ate . 0 S . NP VP 0 S NP . VP 0 S . NP VP 0 S NP . VP 0 NP . Det N 0 NP NP . PP 0 NP . Det N 0 NP NP . PP 0 NP . NP PP 1 VP . V NP 0 NP . NP PP 1 VP . V NP 0 NP . Papa 1 VP . VP PP 0 NP . Papa 1 VP . VP PP 0 De t . the 1 PP . P NP predict 0 De t . the 1 PP . P NP 0 Det . a 1 V . ate 0 Det . a 1 V . ate scan: thành công! 1 P . with 1 P . with 51 52 0 Papa 1 ate 2 0 Papa 1 ate 2 0 ROOT . S 0 NP Papa . 1 V ate . 0 ROOT . S 0 NP Papa . 1 V ate . attach 0 S . NP VP 0 S NP . VP 0 S . NP VP 0 S NP . VP 1 VP V . NP 0 NP . Det N 0 NP NP . PP 0 NP . Det N 0 NP NP . PP 0 NP . NP PP 1 VP . V NP 0 NP . NP PP 1 VP . V NP 0 NP . Papa 1 VP . VP PP 0 NP . Papa 1 VP . VP PP 0 De t . the 1 PP . P NP 0 De t . the 1 PP . P NP 0 Det . a 1 V . ate 0 Det . a 1 V . ate 1 P . with scan: không hợp 1 P . with 53 54
6. 0 Papa 1 ate 2 the 3 0 Papa 1 ate 2 the 3 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 0 NP . Det N 0 NP NP . PP 2 NP . Det N 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 De t . the 1 PP . P NP 2 De t . the 0 De t . the 1 PP . P NP 2 De t . the 0 Det . a 1 V . ate 2 Det . a 0 Det . a 1 V . ate 2 Det . a 1 P . with 1 P . with 61 62 0 Papa 1 ate 2 the 3 caviar 4 0 Papa 1 ate 2 the 3 caviar 4 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 De t . the 1 PP . P NP 2 De t . the 0 De t . the 1 PP . P NP 2 De t . the 0 Det . a 1 V . ate 2 Det . a 0 Det . a 1 V . ate 2 Det . a 1 P . with 1 P . with 63 64 0 Papa 1 ate 2 the 3 caviar 4 0 Papa 1 ate 2 the 3 caviar 4 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . attach 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . attach 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 De t . the 1 PP . P NP 2 De t . the 0 De t . the 1 PP . P NP 2 De t . the 0 Det . a 1 V . ate 2 Det . a 0 Det . a 1 V . ate 2 Det . a 1 P . with 1 P . with 65 66
7. 0 Papa 1 ate 2 the 3 caviar 4 with 5 0 Papa 1 ate 2 the 3 caviar 4 with 5 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 0 De t . the 1 PP . P NP 2 De t . the 1 VP VP . PP 0 De t . the 1 PP . P NP 2 De t . the 1 VP VP . PP 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 1 P . with 0 ROOT S . 1 P . with 0 ROOT S . 4 P . with 4 P . with 73 74 0 Papa 1 ate 2 the 3 caviar 4 with 5 0 Papa 1 ate 2 the 3 caviar 4 with 5 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 5 NP . Papa 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 5 NP . Papa 0 De t . the 1 PP . P NP 2 De t . the 1 VP VP . PP 0 De t . the 1 PP . P NP 2 De t . the 1 VP VP . PP 5 De t . the 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 5 Det . a 1 P . with 0 ROOT S . 1 P . with 0 ROOT S . 4 P . with 4 P . with 75 76 0 Papa 1 ate 2 the 3 caviar 4 with 5 0 Papa 1 ate 2 the 3 caviar 4 with 5 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 5 NP . Papa 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 5 NP . Papa 0 De t . the 1 PP . P NP 2 De t . the 1 VP VP . PP 5 De t . the 0 De t . the 1 PP . P NP 2 De t . the 1 VP VP . PP 5 De t . the 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 5 Det . a 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 5 Det . a 1 P . with 0 ROOT S . 1 P . with 0 ROOT S . 4 P . with 4 P . with 77 78
8. ate 2 the 3 caviar 4 with 5 a 6 spoon 7 ate 2 the 3 caviar 4 with 5 a 6 spoon 7 . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a . 6 N spoon . . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a . 6 N spoon . P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 5 NP Det . N 5 NP Det N . P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 5 NP Det . N 5 NP Det N . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 6 N . caviar PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 6 N . caviar 4 PP P NP . P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 6 N . spoon P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 6 N . spoon 5 NP NP . PP PP 2 NP . Papa 0 S NP VP . 5 NP . Papa PP 2 NP . Papa 0 S NP VP . 5 NP . Papa P 2 De t . the 1 VP VP . PP 5 De t . the P 2 De t . the 1 VP VP . PP 5 De t . the 2 Det . a 4 PP . P NP 5 Det . a 2 Det . a 4 PP . P NP 5 Det . a 0 ROOT S . 0 ROOT S . 4 P . with 4 P . with 85 86 0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7 0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 6 N spoon . 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 6 N spoon . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N . 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP . 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP . 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP . 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP . 0 De t . the 1 PP . P NP 2 De t . the 1 VP VP . PP 1 VP VP PP . 0 De t . the 1 PP . P NP 2 De t . the 1 VP VP . PP 1 VP VP PP . 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP 1 P . with 0 ROOT S . 1 P . with 0 ROOT S . 4 P . with 4 P . with 87 88 0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7 0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 6 N spoon . 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 6 N spoon . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N . 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP . 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP . 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP . 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP . 0 De t . the 1 PP . P NP 2 De t . the 1 VP VP . PP 1 VP VP PP . 0 De t . the 1 PP . P NP 2 De t . the 1 VP VP . PP 1 VP VP PP . 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP 1 P . with 0 ROOT S . 1 VP V NP . 1 P . with 0 ROOT S . 1 VP V NP . 4 P . with 2 NP NP . PP 4 P . with 2 NP NP . PP 0 S NP VP . 1 VP VP . PP 89 90
9. 0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7 0 Papa 1 ate 2 the 3 caviar 4 with a spoon 7 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 6 N spoon . 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 6 N spoon . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 5 NP Det N . 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP . 0 NP . Det N 0 NP NP . PP 2 NP . Det N 3 N . caviar 1 VP V NP . 4 PP P NP . 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP NP . PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP . 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 2 NP NP PP . 0 De t . the 1 PP . P NP 2 De t . the 1 VP VP . PP 1 VP VP PP . 0 De t . the 1 PP . P NP 2 De t . the 1 VP VP . PP 1 VP VP PP . 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP 1 P . with 0 ROOT S . 1 VP V NP . 1 P . with 0 ROOT S . 1 VP V NP . 4 P . with 2 NP NP . PP 4 P . with 2 NP NP . PP 0 S NP VP . 0 S NP VP . 1 VP VP . PP 1 VP VP . PP 7 P . with 7 P . with 0 ROOT97 S . 0 ROOT98 S . Vấn đề với PTCP trên xuống: đệ qui trái nhưng thuật toán Earley Ok! VP 1 VP → . VP PP VP VP PP gắn liên tục các luật mới (cột 1) VP PP vào cây trước khi thấy VP PP PPs attach Æ cần đoán trước số PP VP VP PP 1 VP → VP . PP cần ở đầu vào VP PP V NP ate the caviar (cột 4) 99 100 nhưng thuật toán Earley Ok! nhưng thuật toán Earley Ok! VP VP 1 VP → . VP PP 1 VP → . VP PP VP PP có thể dùng lại VP PP có thể dùng lại (cột1) (cột1) VP VP attach 1 VP → VP . PP 1 VP → VP PP . VP PP VP PP in his bed VP PP VP PP with a spoon with a spoon V NP V NP ate the caviar ate the caviar (cột 7) (cột 10) 101 102
10. PTCP góc trái (Left-corner parsing) z Nhìn từ dưới lên để S S→ NP VP tìm ký hiệu đầu tiên (left-corner) của đoạn, NP→ the Noun sau đó phân tích phần NP còn lại theo kiểu trên VP VP→ ate NP xuống 2 z Tìm cách kết hợp các predict đặc trưng tốt nhất của 1 tìm phân tích trên the xuống và dưới lên tìm Noun ate Phương pháp này làm việc tốt với ngôn ngữ với thành phần quan trọng đặt ở đầu như tiếng Anh. Các tiếng Đức, 109 Hà Lan, Nhật là ngôn ngữ có phần quan trọng đặt cuối.