Nội dung chính trong bài này tập trung các kiến thức về phân tích cú pháp trong xử lý ngôn ngữ tự nhiên như: Bài toán phân tích cú pháp, khái niệm về văn phạm, dạng chuẩn Chomsky, cấu trúc ngữ pháp, các ứng dụng của phân tích cú pháp,. | Bài toán PTCP cây PTCP mẫu Phân tích cú pháp P Lê Thanh Hương Bộ môn Hệ thống Thông tin Viện CNTT &TT – Trường ĐHBKHN Email: huonglt-fit@ T tính C điể điểm câu P cây cú pháp Văn phạm độ chính xác Các bộ PTCP hiện nay có độ chính xác cao (Eisner, Collins, Charniak, etc.) 1 Khái niệm về văn phạm z z z Văn phạm Phân tích câu “Bò vàng gặm cỏ non” Cây cú pháp: Tập luật z z z z z 2 z z z C Æ CN VN CN Æ DN VN Æ ĐgN ĐgN Æ ĐgT DN DN Æ DT TT z z z z z Một văn phạm sản sinh là một hệ thống G = ( T, N, S, R ), trong đó T (terminal) – tập ký hiệu kết thúc N (non terminal) – tập ký hiệu không kết thúc S (start) – ký hiệu khởi đầu R (rule) – tập luật R = { α Æ β | α, β ∈ (T∪N) } α Æ β gọi là luật sản xuất 3 Nhắc lại về văn phạm Dạng chuẩn Chomsky z 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 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 z z 4 S Æ bA|aB A ÆbAA|aS|a B Æ aBB|bS|b z z z z Văn phạm: 1 tập luật viết lại Ký hiệu kết thúc: các ký hiệu không thể phân rã được nữa. Ký hiệu không kết thúc: các ký hiệu có thể phân rã được. Xét văn ă phạm h G: G 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. 5 6 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 DT Bò CN VN DN ĐgN ĐgT gặm TT vàng tiếng Anh DN DT cỏ các thao tác với cây tiếng Việt 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. TT non 7 Văn phạm phi ngữ cảnh (Context-Free Grammar) Các ứng dụng của PTCP Kiểm tra ngữ pháp Trích rút thông tin (Hobbs 1996) 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 .
