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

Phân tích cú pháp 1 Lê Thanh Hương Bộ môn Hệ thống Thông tin Viện CNTT &TT – Trường ĐHBKHN Email: huonglt-fit@mail.hut.edu.vn Bài toán PTCP P T C cây PTCP mẫu độ chính xác tính điể 2 P Văn phạm câu Các bộ PTCP hiện nay có độ chính xác cao (Eisner, Collins, Charniak, etc.) cây cú pháp m Khái niệm về văn phạm z Phân tích câu “Bò vàng gặm cỏ non” z Cây cú pháp: z Tập luật z C Æ CN VN z CN Æ DN z VN Æ ĐgN z ĐgN Æ ĐgT DN z DN Æ DT TT 3 Văn phạm z Một văn phạm sản sinh là một hệ thống z G = ( T, N, S, R ), trong đó z T (terminal) – tập ký hiệu kết thúc z N (non terminal) – tập ký hiệu không kết thúc z S (start) – ký hiệu khởi đầu z R (rule) – tập luật z R = { αÆ β | α, β ∈ (T∪N) } z αÆ β gọi là luật sản xuất 4 Dạng chuẩn Chomsky z Mọi NNPNC không chứa ε đều có thể sinh từ một văn phạm tnđó mọi sản xuất đều có dạng A Æ BC hoặc A Æ a, với A,B,C∈N và a ∈T z Ví dụ: Tìm dạng chuẩn Chomsky cho văn phạm G với T = {a,b}, N ={S,A,B}, R như sau: z S Æ bA|aB z A ÆbAA|aS|a z B Æ aBB|bS|b 5 Nhắc lại về văn phạm z Văn phạm: 1 tập luật viết lại z Ký hiệu kết thúc: các ký hiệu không thể phân rã được nữa. z Ký hiệu không kết thúc: các ký hiệu có thể phân rã được. Xét ă h G 6 z v n p ạm : S → NP VP NP → John, garbage VP → laughed, walks G có thể sinh ra các câu sau: John laughed. John walks. Garbage laughed. Garbage walks. Cấu trúc ngữ pháp Cây cú pháp biểu diễn cấu trúc ngữ pháp của một câu. Bò vàng gặm cỏ non. C CN VN 7 DT Bò ĐgT gặm DT cỏ TT non TT vàng DN ĐgN DN Các ứng dụng của PTCP ƒ Dịch máy (Alshawi 1996, Wu 1997, ...) tiếng Anh tiếng Việt các thao tác với cây 8 ƒ Nhận dạng tiếng nói sử dụng PTCP (Chelba et al 1998) Put the file in the folder. Put the file and the folder. Các ứng dụng của PTCP ƒ Kiểm tra ngữ pháp (Microsoft) ƒ Trích rút thông tin (Hobbs 1996) 9 Kho văn bản NY Times CSDL câu truy vấn Văn phạm phi ngữ cảnh (Context-Free Grammar) còn gọi là văn phạm cấu trúc đoạn z G = z T – tập các ký hiệu kết thúc (terminals) z N - tập các ký hiệu không kết thúc (non-terminals) z P – ký hiệu tiền kết thúc (preterminals), khi viết lại trở thành ký hiệu kết thúc P ⊂ N 10 , z S – ký hiệu bắt đầu z R: X → γ , X là ký hiệu không kết thúc; γ là chuỗi các ký hiệu kết thúc và không kết thúc (có thể rỗng) z Văn phạm G sinh ra ngôn ngữ L z Bộ nhận dạng: trả về yes hoặc no z Bộ PTCP: trả về tập các cây cú pháp So với văn phạm cảm ngữ cảnh R: αAγ ⇒ αβγ z Văn phạm ngữ cấu: z α→β, với α ∈ V+ , β ∈ V* z Văn phạm cảm ngữ cảnh: z r = α→β, với α ∈ V+ , β ∈ V* , ⏐α⏐≤⏐β⏐ z và α1Aα2→α1β’α2 với β’≠ε z Văn phạm phi ngữ cảnh: z A → θ, A ∈ N, ới θ V* ( T N )* 11 z v ∈ = ∪ z Văn phạm chính qui: z A → aB, z A → Ba, z A → a, với A, B ∈ N, a ∈ T. VPCQ VPPNC VPCNC VPNC Văn phạm phi ngữ cảnh 12 Áp dụng tập luật ngữ pháp z S → NP VP → DT NNS VBD → The children slept 13 z S → NP VP → DT NNS VBD NP → DT NNS VBD DT NN → The children ate the cake Cấu trúc đoạn đệ qui 14 Văn phạm cho ngôn ngữ tự nhiên có nhập nhằng S NP VP Nhập nhằng - PP có thể gắn tại 2 điểm (với VP hoặc với NP) John saw snow on the campus 15 0 John PP NP 1 saw NP 2 snow 3 on 4 the 5 campus 6 PTCP kiểu trên xuống z Hướng đích z Khởi đầu với 1 danh sách các ký hiệu cần triển khai (S, NP,VP,) z Viết lại các đích trong tập đích bằng cách: S NP VP . 16 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 z Nếu 1 đích có nhiều cách viết lại Æ chọn 1 luật để áp dụng (bài toán tìm kiếm) z Có thể sử dụng tìm kiếm rộng (breadth-first search) hoặc tìm kiếm sâu (depth-first search) Khó khăn với PTCP trên xuống 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 S→NP X1 S→NP X2 S→NP X600 S→VP Y1 17 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 xuống z PTCP trên xuống sẽ làm việc tốt khi có chiến lược điều khiển ngữ pháp phù hợp 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. z Lặp lại công việc: bất cứ chỗ nào có cấu trúc giống nhau PTCP dưới lên 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 → thay nó bằng vế trái của luật . S NP VP 18 . z Kết thúc khi tập đích = {S}. z Nếu vế phải của các luật khớp với nhiều luật trong tập đích, cần lựa chọn luật áp dụng (bài toán tìm kiếm) z Có thể sử dụng tìm kiếm rộng (breadth-first search) hoặc tìm kiếm sâu (depth-first search) Khó khăn với PTCP dưới lên z Không hiệu quả khi có nhiều nhập nhằng mức từ vựng z Lặp lại công việc: bất cứ khi nào có cấu trúc con chung 19 z Cả PTCP TD (LL) và BU (LR) đều có độ phức tạp là hàm mũ của độ dài câu. Thuật toán CKY (bộ nhận dạng) ƒ Vào: xâu n từ ƒ Ra: yes/no ƒ Cấu trúc ngữ pháp: bảng n x n (chart table) 20 ƒ hàng đánh số 0 đến n-1 ƒ cột đánh số 1 đến n ƒ cell [i,j] liệt kê tất cả các nhãn cú pháp giữa i và j Thuật toán CKY (bottom-up) ƒ for i := 1 to n ƒ Thêm tất cả từ loại của từ thứ i vào ô [i-1,i] ƒ for width := 2 to n ƒ for start := 0 to n-width end := start + width 21 ƒ ƒ for mid := start+1 to end-1 ƒ for mọi nhãn cú pháp X trong [start,mid] ƒ for mọi nhãn cú pháp Y trong [mid,end] ƒ for mọi cách kết hợp X và Y (nếu có) ƒ Thêm nhãn kết quả vào [start,end] nếu chưa có nhãn này Ví dụ Bò vàng gặm cỏ non 1 2 3 4 5 0 DT CN DN C 22 1 TT 2 ĐgT VN ĐgN 3 DT DN 4 TT Văn phạm phi ngữ cảnh 1. Start→ S 2. S → NP VP 3. NP → Det Noun 4. NP → Name 9. V → ate 10. Name → John 11. Name → ice-cream, snow 12. Noun → ice-cream, pizza 23 5. NP → Name PP 6. PP → Prep NP 7. VP → V NP 8. VP → V NP PP 13. Noun → table, guy, campus 14. Det → the 15. Prep → on Luật kết hợp z Ô Cell[i,j] chứa nhãn X nếu z Có luật X→YZ; z Cell[i,k] chứa nhãn Y và ô Cell[k,j] chứa nhãn Z, ằ 24 với k n m giữa i và j; z VD: NP → DT [0,1] NN[1,2] CKY phải sử dụng luật nhị phân z Chuyển VP→V NP PP thành: 8.a. VP→V Arguments 8 b Arguments → NP PP 25 . . CKY chart 1 2 3 4 5 6 7 8 0 DT 1 NN 2 VBD “ The guy ate the ice-cream on the table” 26 3 DT 4 NN 5 IN 6 DT 7 NN Áp dụng thao tác ‘dán’ 1 2 3 4 5 6 7 8 0 DT NP 1 NN 27 2 VBD 3 DT 4 NN 5 IN 6 DT 7 NN Nhập nhằng! 1 2 3 4 5 6 7 8 0 DT NP S 1 NN 2 VBD VP 5. NP → NN PP 8.a. VP→V Arguments 8.b. Arguments → NP PP 28 3 DT NP NP, Args 4 NN 5 IN PP 6 DT NP 7 NN Thuật toán Earley (top-down) z Tìm các nhãn và các nhãn thiếu (partial constituents) từ đầu vào z A → B C . D E là nhãn thiếu: A D+ = A 29 z Tiến hành dần từ trái sang phải B C D E A → B C . D E B C D E A → B C D . E Ví dụ ROOT → S NP→ Papa S → NP VP N → caviar NP → Det N N → spoon 30 NP → NP PP V → ate VP → VP PP P → with VP → V NP Det → the PP → P NP Det → a Recursive Descent (Đệ quy) z 0 ROOT → . S 0 z 0 S → . NP VP 0 ROOT → S VP → VP PP NP → Papa V → ate S → NP VP VP → V NP N → caviar P → with NP → Det N PP → P NP N → spoon Det → the NP → NP PP Det → a 0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7 31 z 0 NP → . Papa 0 z 0 NP → Papa . 1 z 0 S → NP . VP 1 Root S VP NP VP Papa ROOT→ S S → NP VP NP → Papa VP Papa Goal stack Recursive Descent z 0 S → NP . VP 1 z 1 VP → . VP PP 1 ROOT → S VP → VP PP NP → Papa V → ate S → NP VP VP → V NP N → caviar P → with NP → Det N PP → P NP N → spoon Det → the NP → NP PP Det → a 0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7 32 ƒ 1 VP → . VP PP 1 ƒ 1 VP → . VP PP 1 1 VP → . VP PP 1 stack overflowed VP→ VP PP VP→ VP PP PP VP PP VP PP PP VP PP PP VP→ VP PP VP PP PP PP VP→ VP PP Recursive Descent ROOT → S VP → V NP NP → Papa V → ate S → NP VP VP → VP PP N → caviar P → with NP → Det N PP → P NP N → spoon Det → the NP → NP PP Det → a 0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7 ƒ 0 ROOT → . S 0 ƒ 0 S → . NP VP 0 NP P 33 z 1 VP → . V NP 1 sau . = nonterminal, lặp đi lặp lại việc tìm ký hiệu này (“predict”) ƒ 1 V → . ate 1 sau . = terminal, tìm nó ở đầu vào (“scan”) ƒ 1 V → ate . 2 sau . = rỗng, đích con của cha nó đã hoàn chỉnh (“attach”) z 1 VP → V . NP 2 predict (đích con tiếp theo) ƒ 2 NP → . ... 2 phân tích tiếp và cuối cùng ƒ 2 NP → ... . 7 we hoàn thành đích con NP của cha nó Æ attach z 1 VP → V NP . 7 attach z 0 S → NP VP . 7 attach ƒ 0 → . apa 0 ƒ 0 NP → Papa . 1 ƒ 0 S → NP . VP 1 Recursive Descent z 0 ROOT → . S 0 z 0 S → . NP VP 0 z 0 NP → . Papa 0 ROOT → S VP → V NP NP → Papa V → ate S → NP VP VP → VP PP N → caviar P → with NP → Det N PP → P NP N → spoon Det → the NP → NP PP Det → a 0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7 thực hiện bằng lời gọi hàm: S() gọi NP() và VP(), VP được triển khai 1 34 z 0 NP → Papa . 1 z 0 S → NP . VP 1 z 1 VP → . V NP 1 ƒ 1 V → . ate 1 ƒ 1 V → ate . 2 z 1 VP → V . NP 2 ƒ 2 NP → . ... 2 ƒ 2 NP → ... . 7 z 1 VP → V NP . 7 z 0 S → NP VP . 7 cần quay lại để thử 1 luật VP khác cách đệ qui Recursive Descent ROOT → S VP → V NP NP → Papa V → ate S → NP VP VP → VP PP N → caviar P → with NP → Det N PP → P NP N → spoon Det → the NP → NP PP Det → a 0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7 ƒ 0 ROOT → . S 0 ƒ 0 S → . NP VP 0 ƒ 0 NP → . Papa 0 35 ƒ 1 VP → . V NP 1 ƒ 1 V → . ate 1 ƒ 1 V → ate . 2 ƒ 1 VP → V . NP 2 ƒ 2 NP → . ... 2 phân tích tiếp và cuối cùng ƒ 2 NP → ... . 4 ... đoạn NP đúng là từ 2 đến 4 chỗ này cũng cần quay lại ƒ 0 NP → Papa . 1 ƒ 0 S → NP . VP 1 ƒ 1 VP → . VP PP 1 Recursive Descent ROOT → S VP → V NP NP → Papa V → ate S → NP VP VP → VP PP N → caviar P → with NP → Det N PP → P NP N → spoon Det → the NP → NP PP Det → a 0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7 ƒ 0 ROOT → . S 0 ƒ 0 S → . NP VP 0 NP P 36 ƒ 1 VP → . VP PP 1 1 VP → . VP PP 1 1 VP → . VP PP 1 stack overflowed không giải quyết được gì – cần thay đổi tập luật để loại trừ đệ qui trái ƒ 0 → . apa 0 ƒ 0 NP → Papa . 1 ƒ 0 S → NP . VP 1 ƒ 1 VP → . VP PP 1 ƒ 1 VP → . VP PP 1 Thuật toán Earley 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 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 37 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 0 0 ROOT . S khởi tạo tương đương với (0, ROOT → . S) 38 0 0 ROOT . S 0 S . NP VP predict luật có vế trái là S (0, S → . NP VP) 39 0 0 ROOT . S 0 S . NP VP 0 NP . Det N 0 NP . NP PP 0 NP . Papa predict luật có VT = NP (có 3 luật phù hợp) 40 0 0 ROOT . S 0 S . NP VP 0 NP . Det N 0 NP . NP PP 0 NP . Papa 0 D t th predict luật có VT = Det (2 luật) 41 e . e 0 Det . a 0 0 ROOT . S 0 S . NP VP 0 NP . Det N 0 NP . NP PP 0 NP . Papa 0 D t th predict luật có VT = NP ta đã làm việc này ở bước trước, vì vậy không làm lại! Chú ý: ta phải làm lại việc này với luật đệ qui trái 42 e . e 0 Det . a 0 Papa 1 0 ROOT . S 0 NP Papa . 0 S . NP VP 0 NP . Det N 0 NP . NP PP 0 NP . Papa 0 D t th scan: từ phù hợp từ đầu vào 43 e . e 0 Det . a 0 Papa 1 0 ROOT . S 0 NP Papa . 0 S . NP VP 0 NP . Det N 0 NP . NP PP 0 NP . Papa 0 D t th khô hù hợ 44 e . e 0 Det . a scan: ng p p 0 Papa 1 0 ROOT . S 0 NP Papa . 0 S . NP VP 0 NP . Det N 0 NP . NP PP 0 NP . Papa 0 D t th 45 e . e 0 Det . a scan: không phù hợp 0 Papa 1 0 ROOT . S 0 NP Papa . 0 S . NP VP 0 S NP . VP 0 NP . Det N 0 NP NP . PP 0 NP . NP PP 0 NP . Papa 0 D t th attach NP mới tạo (bắt đầu từ 0) với các phần liên quan (các phần chưa hoàn thành kết thúc tại 0 và có NP sau dấu . ) 46 e . e 0 Det . a 0 Papa 1 0 ROOT . S 0 NP Papa . 0 S . NP VP 0 S NP . VP 0 NP . Det N 0 NP NP . PP 0 NP . NP PP 1 VP . V NP 0 NP . Papa 1 VP . VP PP 0 D t th predict 47 e . e 0 Det . a 0 Papa 1 0 ROOT . S 0 NP Papa . 0 S . NP VP 0 S NP . VP 0 NP . Det N 0 NP NP . PP 0 NP . NP PP 1 VP . V NP 0 NP . Papa 1 VP . VP PP 0 D t th 1 PP P NP predict 48 e . e . 0 Det . a 0 Papa 1 0 ROOT . S 0 NP Papa . 0 S . NP VP 0 S NP . VP 0 NP . Det N 0 NP NP . PP 0 NP . NP PP 1 VP . V NP 0 NP . Papa 1 VP . VP PP 0 D t th 1 PP P NP predict 49 e . e . 0 Det . a 1 V . ate 0 Papa 1 0 ROOT . S 0 NP Papa . 0 S . NP VP 0 S NP . VP 0 NP . Det N 0 NP NP . PP 0 NP . NP PP 1 VP . V NP 0 NP . Papa 1 VP . VP PP 0 D t th 1 PP P NP predict 50 e . e . 0 Det . a 1 V . ate 0 Papa 1 0 ROOT . S 0 NP Papa . 0 S . NP VP 0 S NP . VP 0 NP . Det N 0 NP NP . PP 0 NP . NP PP 1 VP . V NP 0 NP . Papa 1 VP . VP PP 0 D t th 1 PP P NP predict 51 e . e . 0 Det . a 1 V . ate 1 P . with 0 Papa 1 ate 2 0 ROOT . S 0 NP Papa . 1 V ate . 0 S . NP VP 0 S NP . VP 0 NP . Det N 0 NP NP . PP 0 NP . NP PP 1 VP . V NP 0 NP . Papa 1 VP . VP PP 0 D t th 1 PP P NP 52 e . e . 0 Det . a 1 V . ate 1 P . with scan: thành công! 0 Papa 1 ate 2 0 ROOT . S 0 NP Papa . 1 V ate . 0 S . NP VP 0 S NP . VP 0 NP . Det N 0 NP NP . PP 0 NP . NP PP 1 VP . V NP 0 NP . Papa 1 VP . VP PP 0 D t th 1 PP P NP 53 e . e . 0 Det . a 1 V . ate 1 P . with scan: không hợp 0 Papa 1 ate 2 0 ROOT . S 0 NP Papa . 1 V ate . 0 S . NP VP 0 S NP . VP 1 VP V . NP 0 NP . Det N 0 NP NP . PP 0 NP . NP PP 1 VP . V NP 0 NP . Papa 1 VP . VP PP 0 D t th 1 PP P NP attach 54 e . e . 0 Det . a 1 V . ate 1 P . with 0 Papa 1 ate 2 0 ROOT . S 0 NP Papa . 1 V ate . 0 S . NP VP 0 S NP . VP 1 VP V . NP 0 NP . Det N 0 NP NP . PP 2 NP . Det N 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 D t th 1 PP P NP predict 55 e . e . 0 Det . a 1 V . ate 1 P . with 0 Papa 1 ate 2 0 ROOT . S 0 NP Papa . 1 V ate . 0 S . NP VP 0 S NP . VP 1 VP V . NP 0 NP . Det N 0 NP NP . PP 2 NP . Det N 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 D t th 1 PP P NP 2 D t th predict (các bước sau tương tự) 56 e . e . e . e 0 Det . a 1 V . ate 2 Det . a 1 P . with 0 Papa 1 ate 2 0 ROOT . S 0 NP Papa . 1 V ate . 0 S . NP VP 0 S NP . VP 1 VP V . NP 0 NP . Det N 0 NP NP . PP 2 NP . Det N 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 D t th 1 PP P NP 2 D t th predict 57 e . e . e . e 0 Det . a 1 V . ate 2 Det . a 1 P . with 0 Papa 1 ate 2 0 ROOT . S 0 NP Papa . 1 V ate . 0 S . NP VP 0 S NP . VP 1 VP V . NP 0 NP . Det N 0 NP NP . PP 2 NP . Det N 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 D t th 1 PP P NP 2 D t th scan (lúc này thất bại vì P khô hải là từ tiế 58 e . e . e . e 0 Det . a 1 V . ate 2 Det . a 1 P . with apa ng p p theo) 0 Papa 1 ate 2 the 3 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 0 S . NP VP 0 S NP . VP 1 VP V . NP 0 NP . Det N 0 NP NP . PP 2 NP . Det N 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 D t th 1 PP P NP 2 D t th thà h ô ! 59 e . e . e . e 0 Det . a 1 V . ate 2 Det . a 1 P . with scan: n c ng 0 Papa 1 ate 2 the 3 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 0 S . NP VP 0 S NP . VP 1 VP V . NP 0 NP . Det N 0 NP NP . PP 2 NP . Det N 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 D t th 1 PP P NP 2 D t th 60 e . e . e . e 0 Det . a 1 V . ate 2 Det . a 1 P . with 0 Papa 1 ate 2 the 3 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 NP . Det N 0 NP NP . PP 2 NP . Det N 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 D t th 1 PP P NP 2 D t th 61 e . e . e . e 0 Det . a 1 V . ate 2 Det . a 1 P . with 0 Papa 1 ate 2 the 3 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 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 . Papa 1 VP . VP PP 2 NP . Papa 0 D t th 1 PP P NP 2 D t th 62 e . e . e . e 0 Det . a 1 V . ate 2 Det . a 1 P . with 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 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 . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 D t th 1 PP P NP 2 D t th 63 e . e . e . e 0 Det . a 1 V . ate 2 Det . a 1 P . with 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 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 . NP PP 1 VP . V NP 2 NP . NP PP 3 N . spoon 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 D t th 1 PP P NP 2 D t th 64 e . e . e . e 0 Det . a 1 V . ate 2 Det . a 1 P . with 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 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 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 3 N . spoon 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 D t th 1 PP P NP 2 D t th attach 65 e . e . e . e 0 Det . a 1 V . ate 2 Det . a 1 P . with 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 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 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 . Papa 1 VP . VP PP 2 NP . Papa 0 D t th 1 PP P NP 2 D t th attach 66 e . e . e . e 0 Det . a 1 V . ate 2 Det . a 1 P . with 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 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 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 . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 0 D t th 1 PP P NP 2 D t th 1 VP VP PP attach 67 e . e . e . e . 0 Det . a 1 V . ate 2 Det . a 1 P . with 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 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 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 . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 0 D t th 1 PP P NP 2 D t th 1 VP VP PP 68 e . e . e . e . 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 1 P . with 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 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 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 . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 0 D t th 1 PP P NP 2 D t th 1 VP VP PP attach 69 e . e . e . e . 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 1 P . with 0 ROOT S . 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 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 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 . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 0 D t th 1 PP P NP 2 D t th 1 VP VP PP 70 e . e . e . e . 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 1 P . with 0 ROOT S . 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 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 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 . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 0 D t th 1 PP P NP 2 D t th 1 VP VP PP 71 e . e . e . e . 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 1 P . with 0 ROOT S . 4 P . with 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 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 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 . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 0 D t th 1 PP P NP 2 D t th 1 VP VP PP 72 e . e . e . e . 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 1 P . with 0 ROOT S . 4 P . with 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 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 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 . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 0 D t th 1 PP P NP 2 D t th 1 VP VP PP 73 e . e . e . e . 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 1 P . with 0 ROOT S . 4 P . with 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 74 e . e . e . e . 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 1 P . with 0 ROOT S . 4 P . with 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 75 e . e . e . e . 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 1 P . with 0 ROOT S . 4 P . with 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 5 D t th 76 e . e . e . e . e . e 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 5 Det . a 1 P . with 0 ROOT S . 4 P . with 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 5 D t th 77 e . e . e . e . e . e 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 5 Det . a 1 P . with 0 ROOT S . 4 P . with 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 5 D t th 78 e . e . e . e . e . e 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 5 Det . a 1 P . with 0 ROOT S . 4 P . with 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 5 D t th 79 e . e . e . e . e . e 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 5 Det . a 1 P . with 0 ROOT S . 4 P . with ate 2 the 3 caviar 4 with 5 a 6 . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a . P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP PP 2 NP . Papa 0 S NP VP . 5 NP . Papa P 2 D t th 1 VP VP PP 5 D t th 80 e . e . e . e 2 Det . a 4 PP . P NP 5 Det . a 0 ROOT S . 4 P . with ate 2 the 3 caviar 4 with 5 a 6 . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a . P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 5 NP Det . N PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP PP 2 NP . Papa 0 S NP VP . 5 NP . Papa P 2 D t th 1 VP VP PP 5 D t th 81 e . e . e . e 2 Det . a 4 PP . P NP 5 Det . a 0 ROOT S . 4 P . with ate 2 the 3 caviar 4 with 5 a 6 . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a . P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 5 NP Det . N PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 6 N . caviar P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 6 N . spoon PP 2 NP . Papa 0 S NP VP . 5 NP . Papa P 2 D t th 1 VP VP PP 5 D t th 82 e . e . e . e 2 Det . a 4 PP . P NP 5 Det . a 0 ROOT S . 4 P . with ate 2 the 3 caviar 4 with 5 a 6 . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a . P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 5 NP Det . N PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 6 N . caviar P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 6 N . spoon PP 2 NP . Papa 0 S NP VP . 5 NP . Papa P 2 D t th 1 VP VP PP 5 D t th 83 e . e . e . e 2 Det . a 4 PP . P NP 5 Det . a 0 ROOT S . 4 P . with 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 . P 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP 5 NP Det . N PP 2 NP . Det N 3 N . caviar 1 VP V NP . 5 NP . Det N 6 N . caviar P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 6 N . spoon PP 2 NP . Papa 0 S NP VP . 5 NP . Papa P 2 D t th 1 VP VP PP 5 D t th 84 e . e . e . e 2 Det . a 4 PP . P NP 5 Det . a 0 ROOT S . 4 P . with 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 . 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 P 2 NP . NP PP 3 N . spoon 2 NP NP . PP 5 NP . NP PP 6 N . spoon PP 2 NP . Papa 0 S NP VP . 5 NP . Papa P 2 D t th 1 VP VP PP 5 D t th 85 e . e . e . e 2 Det . a 4 PP . P NP 5 Det . a 0 ROOT S . 4 P . with 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 . 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 4 PP P NP . 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 P 2 D t th 1 VP VP PP 5 D t th 86 e . e . e . e 2 Det . a 4 PP . P NP 5 Det . a 0 ROOT S . 4 P . with 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 87 e . e . e . e . . 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 1 P . with 0 ROOT S . 4 P . with 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 88 e . e . e . e . . 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 7 PP . P NP 1 P . with 0 ROOT S . 4 P . with 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 89 e . e . e . e . . 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 . 4 P . with 2 NP NP . PP 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 90 e . e . e . e . . 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 . 4 P . with 2 NP NP . PP 0 S NP VP . 1 VP VP . PP 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 91 e . e . e . e . . 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 . 4 P . with 2 NP NP . PP 0 S NP VP . 1 VP VP . PP 7 P . with 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 92 e . e . e . e . . 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 . 4 P . with 2 NP NP . PP 0 S NP VP . 1 VP VP . PP 7 P . with 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 93 e . e . e . e . . 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 . 4 P . with 2 NP NP . PP 0 S NP VP . 1 VP VP . PP 7 P . with 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 94 e . e . e . e . . 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 . 4 P . with 2 NP NP . PP 0 S NP VP . 1 VP VP . PP 7 P . with 0 ROOT S . 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 95 e . e . e . e . . 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 . 4 P . with 2 NP NP . PP 0 S NP VP . 1 VP VP . PP 7 P . with 0 ROOT S . 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 96 e . e . e . e . . 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 . 4 P . with 2 NP NP . PP 0 S NP VP . 1 VP VP . PP 7 P . with 0 ROOT S . 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 97 e . e . e . e . . 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 . 4 P . with 2 NP NP . PP 0 S NP VP . 1 VP VP . PP 7 P . with 0 ROOT S . 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 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 . 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 D t th 1 PP P NP 2 D t th 1 VP VP PP 1 VP VP PP 98 e . e . e . e . . 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 . 4 P . with 2 NP NP . PP 0 S NP VP . 1 VP VP . PP 7 P . with 0 ROOT S . Vấn đề với PTCP trên xuống: đệ qui trái VP VP PP gắn liên tục các luật mới vào cây trước khi thấy PP 99 VP PP VP PP s Æ cần đoán trước số PP cần ở đầu vào nhưng thuật toán Earley Ok! VP PPVP 1 VP → . VP PP (cột 1) 100 attach VP V NP VP PP ate the caviar 1 VP → VP . PP (cột 4) nhưng thuật toán Earley Ok! VP VP PPVP 1 VP → . VP PP (cột1) attach có thể dùng lại 101 VP V NP VP PP PP 1 VP → VP . PP ate the caviar with a spoon (cột 7) nhưng thuật toán Earley Ok! VP VP PPVP 1 VP → . VP PP có thể dùng lại (cột1) 102 VP V NP VP PP PP ate the caviar with a spoon in his bed 1 VP → VP PP . (cột 10) nhưng thuật toán Earley Ok! VP PPVP 1 VP → . VP PP có thể dùng lại VP VP PP 1 VP → VP . PP(cột1) attach 103 VP V NP VP PP PP ate the caviar with a spoon in his bed (cột10) Phục hồi cây cú pháp Sử dụng thuật toán dùng queue đơn giản, dựa trên các thành phần có ích • 1 thành phần ở trạng thái kết thúc là có ích • If s=[A →α•Β,i] trong tập đích k & có ích • then q=[A →αΒ •,k] & item r= [B →γ •,j] là có ích [s,itrong tập trạng thái j i k j q r α γ 104 Đánh dấu tất cả các thành phần trong tập trạng thái Sn ở dạng Start → αS•, 0 for j=n downto 0 do for i=0 to j do for mọi bộ đã đánh dấu [s,i] trong tập trạng thái j do for k=i to j do if [q,i]∈Sk & [r,k] ∈Sj & s= q⊗r then đánh dấu [q,i] và [r,k] [s,i] : một thành phần với luật s & trả về con trỏ i. Ưu điểm z Thuật toán Earley thực hiện một vài phép lọc top-down: bất cứ thành phần nào (state, or triple) được đưa vào tập trạng thái cần tương thích với phần đã được sinh ra ở bên trái Ví 105 . dụ: S⇒ wi trong đó wi là phần của câu đã được duyệt qua wi S * Nhược điểm z Biểu diễn luật: Explicit representation of rules: wastes time building them. z Thực hiện phép lọc bên trái nhưng không lọc 106 bên phải Phép lọc nhìn trước cho ký hiệu không kết thúc A: FIRST(A)= {x|A ⇒ xδ }, x= 1 token v.d., FIRST(S)= who, did, the, etc. Các phương pháp khác z Các phương pháp khác ứng với các cách khác nhau để tìm các đoạn z Đoạn X[i, j] là đoạn có nhãn X phủ đầu vào từ I đến j Example: John ate ice cream on the table 107 0 1 2 - 3 4 5 6 PP[3,6]; S[0,6]; z Biểu diễn không gian tìm kiếm như cây and-or z Disjuncts (or) = các đường phân tích khác nhau z Conjuncts (and) = vế phải của luật, ví dụ vế phải của S là NP VP PTCP là việc tìm kiếm Det(0,1) Noun(1, 2) S(0, 7) 0 the 1 guy 2 saw 3 ice-cream 4 on 5 the 6 hill 7 NP(0, 1) VP(1, 8) NP(0, 2) V(1, 2) VP(2, 7) V(2, 3) NP(3,7) NP(3 4) Name (0, 1) 108 NP(5, 7) Det(5,6) Noun(6,7) the hill NP(5,7) Name(5,6) Name(3, 4) PP(4, 7) the guy saw , Prep(4, 5) on ice-cream PTCP góc trái (Left-corner parsing) z Nhìn từ dưới lên để tìm ký hiệu đầu tiên (left-corner) của đoạn, sau đó phân tích phần còn lại theo kiểu trên ố S NP VP S→ NP VP NP→ the Noun VP→ ate NP 109 xu ng z Tìm cách kết hợp các đặc trưng tốt nhất của tìm phân tích trên xuống và dưới lên the Noun 1 2 tìm predict 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, Hà Lan, Nhật là ngôn ngữ có phần quan trọng đặt cuối.