intTypePromotion=3

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

Chia sẻ: Nguyen Nguyen | Ngày: | Loại File: PDF | Số trang:19

0
5
lượt xem
0
download

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

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Xử lý ngôn ngữ tự nhiên: Phân tích cú pháp" cung cấp cho người học các kiến thức: Bài toán PTCP, khái niệm về văn phạm, văn phạm, dạng chuẩn Chomsky, cấu trúc ngữ pháp, các ứng dụng của PTCP,... Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Xử lý ngôn ngữ tự nhiên: 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ể điểm câu P Bộ môn Hệ thống Thông tin 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 h G: 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  2. Cấu trúc ngữ pháp Các ứng dụng của PTCP 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. ƒ Dịch máy (Alshawi 1996, Wu 1997, ...) C các thao tác CN với cây VN tiếng Anh tiếng Việt DN ĐgN DT TT ĐgT DN Bò vàng gặm ƒ Nhận dạng tiếng nói sử dụng PTCP (Chelba et al 1998) DT TT Put the file in the folder. cỏ non Put the file and the folder. 7 8 Văn phạm phi ngữ cảnh Các ứng dụng của PTCP (Context-Free Grammar) … còn gọi là văn phạm cấu trúc đoạn z G = ƒ Kiểm tra ngữ pháp (Microsoft) 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) ƒ Trích rút thông tin (Hobbs 1996) 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, thúc P⊂ So với Nphạm cảm ngữ cảnh văn z S – ký hiệu bắt đầu R: αAγ ⇒ αβγ z R: X → γ , X là ký hiệu không kết thúc; γ là chuỗi các Kho văn bản CSDL ký hiệu kết thúc và không kết thúc (có thể rỗng) NY Times z Văn phạm G sinh ra ngôn ngữ L z Bộ nhận dạng: trả về yes hoặc no câu truy vấn z Bộ PTCP: trả về tập các cây cú pháp 9 10 z Văn phạm ngữ cấu: z α→β, với α ∈ V+ , β ∈ V* Văn phạm phi ngữ cảnh 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, z ới θ ∈ V*= với V* ( T ∪ N )* z Văn phạm chính qui: z A → aB, VPCQ z A → Ba, VPPNC z A → a, VPCNC với A, B ∈ N, a ∈ T. VPNC 11 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  3. Á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 slept p 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 0 John 2 snow z Nếu 1 đích có nhiều cách viết lại Æ chọn 1 luật để áp 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 S→NP X1 S→NP X2 …… S→NP X600 S→VP Y1 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 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  4. Khó khăn với PTCP dưới lên Thuật toán CKY (bộ nhận dạng) z Không hiệu quả khi có nhiều nhập nhằng mức ƒ Vào: xâu n từ từ vựng ƒ Ra: yes/no z Lặp lại công việc: bất cứ khi nào có cấu trúc con chung ƒ Cấu trúc ngữ g pháp: p p bảng g n x n ((chart table)) ƒ hàng đánh số 0 đến n-1 z Cả PTCP TD (LL) và BU (LR) đều có độ phức tạp là hàm mũ của độ dài câu. ƒ 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 19 20 Thuật toán CKY (bottom-up) Ví dụ ƒ for i := 1 to n Bò vàng gặm cỏ non ƒ Thêm tất cả từ loại của từ thứ i vào ô [i-1,i] 1 2 3 4 5 ƒ for width := 2 to n ƒ for start := 0 to n-width 0 CN C DT DN ƒ end := start + width 1 ƒ for mid := start+1 to end-1 TT ƒ for mọi nhãn cú pháp X trong [start,mid] 2 VN ƒ for mọi nhãn cú pháp Y trong [mid,end] ĐgT ĐgN 3 ƒ for mọi cách kết hợp X và Y (nếu có) DT DN ƒ Thêm nhãn kết quả vào [start,end] nếu chưa 4 có nhãn này TT 21 22 Văn phạm phi ngữ cảnh Luật kết hợp 1. Start→ S 9. V → ate Name → John z Ô Cell[i,j] chứa nhãn X nếu 2. S → NP VP 10. 3. NP → Det Noun 11. Name → ice-cream, snow z Có luật X→YZ; 4. NP → Name 12. Noun → ice-cream, pizza z Cell[i,k] chứa nhãn Y và ô Cell[k,j] chứa nhãn Z, Noun → table, guy, campus với k nằm ằ giữa i và j; 5. NP → Name PP 13. 6. PP → Prep NP 14. Det → the 7. VP → V NP 15. Prep → on z VD: NP → DT [0,1] NN[1,2] 8. VP → V NP PP 23 24 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  5. CKY phải sử dụng luật nhị CKY chart phân “ The guy ate the ice-cream on the table” 1 2 3 4 5 6 7 8 z Chuyển VP→V NP PP thành: 0 DT 8.a. VP→V Arguments 1 NN 8 b Arguments → NP PP 8.b. 2 VBD 3 DT 4 NN 5 IN 6 DT 7 NN 25 26 5. NP → NN PP Áp dụng thao tác ‘dán’ Nhập nhằng! 8.a. VP→V Arguments 8.b. Arguments → NP PP 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 0 DT NP S 0 DT NP 1 NN 1 NN 2 VBD VP 2 VBD 3 DT NP NP, 3 DT Args 4 NN 4 NN 5 IN 5 IN PP 6 DT 6 DT NP 7 NN 7 NN 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 → S NP → Papa z A → B C . D E là nhãn thiếu: S → NP VP N → caviar A D A NP → Det N N → spoon + = NP → NP PP V → ate VP → VP PP P → with B C D E B C D E VP → V NP Det → the PP → P NP Det →a A→BC.DE A→BCD.E 29 30 z Tiến hành dần từ trái sang phải CuuDuongThanCong.com https://fb.com/tailieudientucntt
  6. 0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7 0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7 Recursive Descent (Đệ quy) Recursive Descent ROOT →S VP → VP PP NP → Papa V → ate ROOT →S VP → VP PP NP → Papa V → ate S → NP VP VP → V NP N → caviar P → with S → NP VP VP → V NP N → caviar P → with NP → Det N PP → P NP N → spoon Det → the NP → Det N PP → P NP N → spoon Det → the NP → NP PP Det → a NP → NP PP Det → a z 0 ROOT → . S 0 z 0S → NP . VP 1 z 0 S → . NP VP 0 z 1 VP → . VP PP 1 z 0 NP → . Papa 0 ƒ 1 VP → . VP PP 1 z 0 NP → Papa . 1 ƒ 1 VP → . VP PP 1 z 0 S → NP . VP 1 1 VP → . VP PP 1 stack overflowed ROOT→ S S → NP VP NP → Papa Papa VP→ VP PP VP→ VP PP VP→ VP PP VP→ VP PP NP Papa VP VP VP Root S VP VP VP VP PP PP PP PP PP PP PP Goal stack 31 32 PP PP 0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7 0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7 Recursive Descent Recursive Descent ROOT →S VP → V NP NP → Papa V → ate ROOT →S VP → V NP NP → Papa V → ate S → NP VP VP → VP PP N → caviar P → with S → NP VP VP → VP PP N → caviar P → with NP → Det N PP → P NP N → spoon Det → the NP → Det N PP → P NP N → spoon Det → the NP → NP PP Det → a NP → NP PP Det → a z 0 ROOT → . S 0 ƒ 0 ROOT → . S 0 z 0S → . NP VP 0 thực hiện bằng lời gọi hàm: ƒ 0 S → . NP VP 0 z 0 NP → . Papa p 0 S() gọi NP() và VP(), VP được triển khai 1 ƒ 0 NP → . Papa P 0 z 0 NP → Papa . 1 cách đệ qui ƒ 0 NP → Papa . 1 z 0S → NP . VP 1 ƒ 0 S → NP . VP 1 z → . V NP 1 1 VP cần quay lại để thử 1 luật VP khác 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 ƒ 1 V → . ate 1 sau . = terminal, tìm nó ở đầu vào (“scan”) ƒ 1 V → ate . 2 ƒ 1 V → ate . 2 sau . = rỗng, đích con của cha nó đã hoàn chỉnh (“attach”) z 1 VP → V . NP 2 z 1 VP → V . NP 2 predict (đích con tiếp theo) ƒ 2 NP → . ... 2 ƒ 2 NP → . ... 2 phân tích tiếp và cuối cùng … ƒ 2 NP → ... . 7 ƒ 2 NP → ... . 7 we hoàn thành đích con NP của cha nó Æ attach z 1 VP → V NP . 7 z 1 VP → V NP . 7 attach 33 z 0 S → NP VP . 7 34 z 0S → NP VP . 7 attach 0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7 0 Papa 1 ate 2 the 3 caviar 4 with 5 a 6 spoon 7 Recursive Descent Recursive Descent ROOT →S VP → V NP NP → Papa V → ate ROOT →S VP → V NP NP → Papa V → ate S → NP VP VP → VP PP N → caviar P → with S → NP VP VP → VP PP N → caviar P → with NP → Det N PP → P NP N → spoon Det → the NP → Det N PP → P NP N → spoon Det → the NP → NP PP Det → a NP → NP PP Det → a ƒ 0 ROOT → . S 0 ƒ 0 ROOT → . S 0 ƒ 0 S → . NP VP 0 ƒ 0 S → . NP VP 0 ƒ 0 NP → . Papa 0 ƒ 0 NP → . Papa P 0 ƒ 0 NP → Papa . 1 ƒ 0 NP → Papa . 1 ƒ 0 S → NP . VP 1 ƒ 0 S → NP . VP 1 ƒ 1 VP → . VP PP 1 ƒ 1 VP → . VP PP 1 ƒ 1 VP → . V NP 1 chỗ này cũng cần quay lại ƒ 1 VP → . VP PP 1 ƒ 1 V → . ate 1 ƒ 1 VP → . VP PP 1 ƒ 1 V → ate . 2 1 VP → . VP PP 1 ƒ 1 VP → V . NP 2 1 VP → . VP PP 1 ƒ 2 NP → . ... 2 phân tích tiếp và cuối cùng… stack overflowed ƒ 2 NP → ... . 4 ... đoạn NP đúng là từ 2 đến 4 35 không giải quyết được gì 36 – cần thay đổi tập luật để loại trừ đệ qui trái CuuDuongThanCong.com https://fb.com/tailieudientucntt
  7. 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 NP . NP PP (0, S → . NP VP) 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! 0D Dett . th the 0D Dett . th the Chú ý: ta phải làm lại việc này với luật đệ qui trái 0 Det . a 0 Det . a 41 42 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  8. 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 NP . Det N 0 NP . Det N 0 NP . NP PP 0 NP . NP PP 0 NP . Papa scan: từ phù hợp từ đầu vào 0 NP . Papa 0D Dett . th the 0D Dett . th the scan: không khô phù hù hợp hợ 0 Det . a 0 Det . a 43 44 0 Papa 1 0 Papa 1 0 ROOT . S 0 NP Papa . 0 ROOT . S attach NP mới tạo (bắt đầu từ 0) với 0 NP Papa . 0 S . NP VP 0 S . NP VP các phần liên quan (các phần chưa 0 S NP . VP 0 NP . Det N 0 NP . Det N 0 NP NP . PP hoàn thành kết thúc tại 0 và có NP sau 0 NP . NP PP 0 NP . NP PP dấu . ) 0 NP . Papa 0 NP . Papa 0D Dett . th the 0D Dett . th the 0 Det . a scan: không phù hợp 0 Det . a 45 46 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 predict 0 S . NP VP 0 S NP . VP 0 NP . Det N 0 NP NP . PP 0 NP . Det N 0 NP NP . PP predict 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 0D Dett . th the 0D Dett . th the 1 PP . P NP 0 Det . a 0 Det . a 47 48 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  9. 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 0D Dett . th the 1 PP . P NP 0D Dett . th 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 0D Dett . th the 1 PP . P NP predict 0D Dett . th 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 0D Dett . th the 1 PP . P NP 0D Dett . th 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  10. 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 . 0 S . NP VP 0 S NP . VP 1 VP V . NP predict 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 . Det N 0 NP NP . PP 2 NP . Det N predict (các bước sau tương tự) 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0D Dett . th the 1 PP . P NP 0D Dett . th the 1 PP . P NP 2D Dett . th the 0 Det . a 1 V . ate 0 Det . a 1 V . ate 2 Det . a 1 P . with 1 P . with 55 56 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 . 0 S . NP VP 0 S NP . VP 1 VP V . NP 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 . Det N 0 NP NP . PP 2 NP . Det N 0 NP . NP PP 1 VP . V NP 2 NP . NP PP predict 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 NP . Papa 1 VP . VP PP 2 NP . Papa scan (lúc này thất bại vì 0D Dett . th the 1 PP . P NP 2D Dett . th the 0D Dett . th the 1 PP . P NP 2D Dett . th the P Papa khô không phải hải là từ tiếp tiế 0 Det . a 1 V . ate 2 Det . a 0 Det . a 1 V . ate 2 Det . a theo) 1 P . with 1 P . with 57 58 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 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 . Det N 0 NP NP . PP 2 NP . Det N 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 0 NP . NP PP 1 VP . V NP 2 NP . NP PP 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0D Dett . th the 1 PP . P NP 2D Dett . th the scan: thành thà h công! ô ! 0D Dett . th the 1 PP . P NP 2D Dett . th 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 59 60 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  11. 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 0D Dett . th the 1 PP . P NP 2D Dett . th the 0D Dett . th the 1 PP . P NP 2D Dett . th 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 0D Dett . th the 1 PP . P NP 2D Dett . th the 0D Dett . th the 1 PP . P NP 2D Dett . th 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 0D Dett . th the 1 PP . P NP 2D Dett . th the 0D Dett . th the 1 PP . P NP 2D Dett . th 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  12. 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 2 NP Det N . 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 . attach 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 . 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 0 Det . a 1 V . ate 2 Det . a 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 1 P . with 1 P . with 67 68 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 2 NP Det N . 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 . 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 . attach 0 NP . Papa 1 VP . VP PP 2 NP . Papa 0 S NP VP . 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 0D Dett . th the 1 PP . P NP 2D Dett . th 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 . 69 70 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 2 NP Det N . 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 . 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 . 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 0D Dett . th the 1 PP . P NP 2D Dett . th 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 71 72 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  13. 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 . 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 0D Dett . th the 1 PP . P NP 2D Dett . th 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 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 5 D Dett . th 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 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 5 D Dett . th the 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 5 D Dett . th 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  14. 0 Papa 1 ate 2 the 3 caviar 4 with 5 ate 2 the 3 caviar 4 with 5 a 6 0 ROOT . S 0 NP Papa . 1 V ate . 2 Det the . 3 N caviar . 4 P with . . 1 V ate . 2 Det the . 3 N caviar . 4 P with . 5 Det a . 0 S . NP VP 0 S NP . VP 1 VP V . NP 2 NP Det . N 2 NP Det N . 4 PP P . NP P 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 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 P 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 PP 2 NP . Papa 0 S NP VP . 5 NP . Papa 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 5 D Dett . th the P 2D Dett . th the 1 VP VP . PP 5 D Dett . th the 0 Det . a 1 V . ate 2 Det . a 4 PP . P NP 5 Det . a 2 Det . a 4 PP . P NP 5 Det . a 1 P . with 0 ROOT S . 0 ROOT S . 4 P . with 4 P . with 79 80 ate 2 the 3 caviar 4 with 5 a 6 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 . . 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 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 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 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 PP 2 NP . Papa 0 S NP VP . 5 NP . Papa P 2D Dett . th the 1 VP VP . PP 5 D Dett . th the P 2D Dett . th the 1 VP VP . PP 5 D Dett . th 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 81 82 ate 2 the 3 caviar 4 with 5 a 6 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 . . 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 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 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 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 PP 2 NP . Papa 0 S NP VP . 5 NP . Papa P 2D Dett . th the 1 VP VP . PP 5 D Dett . th the P 2D Dett . th the 1 VP VP . PP 5 D Dett . th 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 83 84 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  15. 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 2D Dett . th the 1 VP VP . PP 5 D Dett . th the P 2D Dett . th the 1 VP VP . PP 5 D Dett . th 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 . 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 1 VP VP PP . 0D Dett . th the 1 PP . P NP 2D Dett . th 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 . 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 1 VP VP PP . 0D Dett . th the 1 PP . P NP 2D Dett . th 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  16. 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 . 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 1 VP VP PP . 0D Dett . th the 1 PP . P NP 2D Dett . th 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 91 92 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 . 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 1 VP VP PP . 0D Dett . th the 1 PP . P NP 2D Dett . th 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 93 0 ROOT94S . 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 . 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 1 VP VP PP . 0D Dett . th the 1 PP . P NP 2D Dett . th 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 ROOT95S . 0 ROOT96S . CuuDuongThanCong.com https://fb.com/tailieudientucntt
  17. 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 . 0D Dett . th the 1 PP . P NP 2D Dett . th the 1 VP VP . PP 1 VP VP PP . 0D Dett . th the 1 PP . P NP 2D Dett . th 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 ROOT97S . 0 ROOT98S . 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 PP PPs attach VP PP Æ cần đoán trước số PP VP 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  18. … nhưng thuật toán Earley Ok! Phục hồi cây cú pháp [s,itrong tập trạng thái j Sử dụng thuật toán dùng queue đơn giản, VP dựa trên các thành phần có ích 1 VP → . VP PP • 1 thành phần ở trạng thái kết thúc là có ích VP PP có thể dùng lại q r • If s=[A →α•Β,i] trong tập đích k & có ích (cột1) VP α γ • then q=[A →αΒ •,k] & item r= [B →γ •,j] là attach 1 VP → VP . PP có ích VP PP i k j [s,i] : một thành phần với luật s & trả về con trỏ i. VP PP in his bed Đánh dấu tất cả các thành phần trong tập trạng thái Sn ở dạng VP PP Start → αS•, 0 with a spoon for j=n downto 0 do NP for i=0 to j do V ate the caviar for mọi bộ đã đánh dấu [s,i] trong tập trạng thái j do for k=i to j do (cột10) 103 if [q,i]∈Sk & [r,k] ∈Sj & s= q⊗r then 104 đánh dấu [q,i] và [r,k] Ưu điểm Nhược điểm z Thuật toán Earley thực hiện một vài phép lọc z Biểu diễn luật: Explicit representation of top-down: bất cứ thành phần nào (state, or rules: wastes time building them. triple) được đưa vào tập trạng thái cần tương z Thực hiện phép lọc bên trái nhưng không lọc thích với phần đã được sinh ra ở bên trái trái. Ví * w trong đó w là phần của câu đã bên phải dụ: S⇒ i i được duyệt qua S 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 wi v.d., FIRST(S)= who, did, the, etc. 105 106 Các phương pháp khác PTCP là việc tìm kiếm 0 the 1 guy 2 saw 3 ice-cream 4 on 5 the 6 hill 7 S(0, 7) 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 NP(0, 1) VP(1, 8) NP(0, 2) VP(2, 7) z Đoạn X[i, j] là đoạn có nhãn X phủ đầu vào từ I đến j Name (0, 1) V(1, 2) Det(0,1) Noun(1, 2) Example: V(2, ( 3)) NP(3,7) ( , ) NP(3, 0 John 1 ate 2 ice-cream ice cream 3 on 4 the 5 table 6 NP(3 4) the guy PP[3,6]; S[0,6]; … saw Name(3, 4) PP(4, 7) 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 ice-cream Prep(4, 5) z Conjuncts (and) = vế phải của luật, ví dụ vế phải của S là NP VP on NP(5,7) NP(5, 7) Name(5,6) Det(5,6) Noun(6,7) 107 the hill 108 CuuDuongThanCong.com https://fb.com/tailieudientucntt
  19. 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 còn lại theo kiểu trên NP VP VP→ ate NP xuống ố z Tìm cách kết hợp các 2 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. CuuDuongThanCong.com https://fb.com/tailieudientucntt

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản