Đề tài Nghiên cứu việc vận dụng các mô hình phân tích cú pháp tiếng Việt

LỜI NÓI ĐẦU Xử lý ngôn ngữ tự nhiên nói chung và phân tích cú pháp ngôn ngữ tự nhiên nói riêng là những vấn đề quan trọng của trí tuệ nhân tạo, được nhiều nhà khoa học trên thế giới quan tâm nghiên cứu trong suốt 50 năm qua. Các ứng dụng trong lĩnh vực này rất phong phú. Ta có thể điểm qua một số ứng dụng chính như dịch máy, kiểm tra và chữa lỗi văn bản, chuyển giao diện người – máy sang ngôn ngữ tự nhiên, nhận dạng chữ viết, thiết kế người máy có khả năng hiểu và nói được tiếng của con người… Bài toán phân tích cú pháp ngôn ngữ tự nhiên bằng máy tính là bài toán lớn và phức tạp. Với tiếng Việt - một ngôn ngữ rất phức tạp thì dường như bài toán này lại càng khó khăn hơn. Chúng ta đã có một số công trình nghiên cứu về xử lý tiếng Việt và đã đạt được một số thành công nhất định. Tuy nhiên, cho đến nay bài toán phân tích cú pháp tiếng Việt vẫn chưa được giải quyết triệt để. Một trong những lý do chính là vì chúng ta chưa nghiên cứu một cách có hệ thống ngữ pháp tiếng Việt và cơ sở lý thuyết về xây dựng những trình phân tích cú pháp cho tiếng Việt còn tương đối ít và chưa hoàn chỉnh. Các mô hình văn phạm phi ngữ cảnh và mạng chuyển được sử dụng rộng rãi trong mô tả cú pháp không chỉ của các ngôn ngữ lập trình mà cả các ngôn ngữ tự nhiên. Trong khoá luận này, em sẽ tập trung nghiên cứu việc vận dụng các mô hình này cho bài toán cụ thể là phân tích cú pháp tiếng Việt. Ngôn ngữ Việt có nhiều điểm khác so với các ngôn ngữ phổ biến, đã được nghiên cứu nhiều như tiếng Anh hay tiếng Pháp. Do đó, chúng ta không thể áp dụng hoàn toàn những kết quả đã đạt được đối với các ngôn ngữ này vào tiếng Việt. Khoá luận trình bày các vấn đề sau: • Khái quát vấn đề phân tích văn bản • Vận dụng các mô hình văn phạm phi ngữ cảnh và mạng chuyển đệ quy để mô tả ngôn ngữ tự nhiên • Nghiên cứu các thuật toán phân tích đối với các văn phạm phi ngữ cảnh và các mạng chuyển • Nghiên cứu một cách hệ thống các đặc điểm của ngữ pháp tiếng Việt • Xây dựng một trình phân tích câu tiếng Anh đơn giản • Xây dựng một trình phân tích câu tiếng Việt đơn giản Khoá luận tốt nghiệp 1 • Đánh giá kết quả đã đạt được và hướng phát triển Để thực hiện được đề tài này, em đã vận dụng những kiến thức được học trong giai đoạn đại cương và chuyên ngành, đồng thời học hỏi và nghiên cứu thêm lĩnh vực ngôn ngữ học và tiếng Việt. Để tạo ra một sản phẩm phần mềm tương đối khả quan cần có sự nghiên cứu lâu dài và có hệ thống trên cả ba lĩnh vực toán học, tin học và ngôn ngữ học. Nếu chỉ có những kiến thức tin học thì sản phẩm tạo ra sẽ không thể mang ứng dụng trong thực tế. Vì vậy, việc đồng thời trau dồi những kiến thức toán học, tin học và ngôn ngữ học là rất cần thiết. Những công việc em đã thực hiện mới chỉ là bước đầu trong việc xử lý các văn bản tiếng Việt. Em rất mong muốn tiếp tục nhận được sự hỗ trợ và chỉ bảo tận tình của các thầy cô giáo, các nhà chuyên môn cùng toàn thể các bạn sinh viên quan tâm, yêu thích công việc xử lý ngôn ngữ tự nhiên, vốn rất khó khăn và phức tạp, cần có lòng kiên trì và say mê cao độ. Em xin được bày tỏ lòng cảm ơn sâu sắc tới TS. Lương Chi Mai và ThS. Nguyễn Thị Minh Huyền đã tận tình hướng dẫn và giúp đỡ, tạo mọi điều kiện thuận lợi về tài liệu và phương tiện để em hoàn thành khoá luận này. Trong quá trình thực hiện khoá luận, em còn nhận được sự ủng hộ, giúp đỡ và động viên của các anh chị ở Phòng Nhận dạng và Công nghệ Tri thức, Viện Công nghệ Thông tin, Trung tâm Khoa học Tự nhiên và Công nghệ Quốc gia, nơi em thực tập trong thời gian qua. Em xin chân thành cảm ơn. Em xin chân thành cảm ơn các thầy cô giáo trong và ngoài Khoa Toán-Cơ-Tin học đã truyền đạt cho em những kiến thức, trang bị cho em những hành trang quý giá trước khi em ra trường. Em xin chân thành cảm ơn các thầy cô giáo trong Bộ môn Tin học đã tạo điều kiện cho em được thực hiện một số xêmina khoa học liên quan đến đề tài, và đóng góp nhiều ý kiến quý báu, kịp thời. Xin cảm ơn các bạn sinh viên đã động viên, giúp đỡ tôi thực hiện đề tài này. Hà Nội, ngày 10 tháng 5 năm 2002 Sinh viên Lê Hồng Phương Khoá luận tốt nghiệp 2 Mục lục LỜI NÓI ĐẦU ..................................................................1 Danh mục hình .............................................................................................5 Danh mục bảng.............................................................................................5 Chương 1. Mở đầu...........................................................7 1.1. Tổng quan về vấn đề phân tích văn bản........................................... 7 1.2. Bài toán phân tích cú pháp ............................................................... 7 1.3. Nội dung khoá luận .......................................................................... 8 Chương 2. Văn phạm phi ngữ cảnh .................................9 2.1. Văn phạm và ngôn ngữ sinh bởi văn phạm...................................... 9 2.2. Văn phạm phi ngữ cảnh ................................................................. 10 2.3. Biểu diễn cấu trúc câu .................................................................... 11 2.4. Phân tích từ trên xuống .................................................................. 14 2.5. Phân tích từ dưới lên ...................................................................... 15 2.6. Đánh giá hai phương pháp phân tích trên ...................................... 20 2.7. Phương pháp phân tích tổng hợp ................................................... 21 Chương 3. Các mạng chuyển.........................................27 3.1. Văn phạm và ôtômát ...................................................................... 27 3.2. Các yếu tố cơ sở của mạng chuyển đệ quy .................................... 29 3.3. Tính thủ tục của các RTN .............................................................. 33 3.4. Phân tích từ trên xuống cho mạng chuyển đệ quy ......................... 34 Chương 4. Xây dựng văn phạm tiếng Việt .....................37 4.1. Xây dựng tập từ loại tiếng Việt...................................................... 37 4.2. Xây dựng văn phạm tiếng Việt ...................................................... 38 Khoá luận tốt nghiệp 3 4.2.1. Danh ngữ ..........................................................................................39 4.2.2. Động ngữ ..........................................................................................41 4.2.3. Tính ngữ............................................................................................44 4.2.4. Câu đơn hai thành phần ...................................................................45 4.2.5. Văn phạm tiếng Việt .........................................................................47 Chương 5. Cài đặt chương trình ....................................49 5.1. Cấu trúc dữ liệu .............................................................................. 49 5.2. Cài đặt thuật toán ........................................................................... 51 5.3. Thể hiện kết quả phân tích ............................................................. 52 5.4. Đánh giá kết quả............................................................................. 57 Phụ lục .........................................................................58 Bài toán tách từ vựng tiếng Việt ........................................................... 58 1. Đặt bài toán............................................................................................58 2. Các bước giải quyết................................................................................58 3. Đánh giá kết quả ....................................................................................60 Tài liệu tham khảo......................................................................................63 Khoá luận tốt nghiệp 4 Danh mục hình Hình 1. Phân loại văn phạm của Chomsky ...............................................................11 Hình 2. Cây biểu diễn câu John ate the cat .................................................14 Hình 3. Biểu đồ sau khi tìm thấy một ADJ tại vị trí 2 ..............................................16 Hình 4. Sau khi phân tích can là NOUN .................................................................18 Hình 5. Biểu đồ sau khi thêm hold .........................................................................19 Hình 6. Biểu đồ sau khi tìm được tất cả các NP .......................................................19 Hình 7. Biểu đồ cuối cùng ........................................................................................20 Hình 8. Vị trí và biểu đồ ban đầu..............................................................................22 Hình 9. Biểu đồ sau khi phân tích cụm NP đầu tiên .................................................24 Hình 10. Sau khi phân tích khả năng thứ hai của NP đầu tiên .................................25 Hình 11. Sau khi tìm kiếm một S theo quy tắc 1 bị thất bại .....................................25 Hình 12. Cấu trúc của câu cần phân tích...................................................................26 Hình 13. Mạng chuyển đệ quy làm ví dụ trong phân tích từ trên xuống ..................35 Hình 14. Giao diện chương trình phân tích cú pháp tiếng Anh ................................53 Hình 15. Phương pháp xây dựng ôtômát âm tiết ......................................................59 Hình 16. Phương pháp xây dựng ôtômát từ vựng.....................................................59 Hình 17. Một tình huống nhập nhằng .......................................................................60 Hình 18. Các phương án phân tích cho một câu tiếng Việt nhập nhằng ..................62 Hình 19. Cây phân tích ứng với cách tách từ đúng...................................................62 Danh mục bảng Bảng 1. Phân tích từ trên xuống, ưu tiên chiều sâu cho văn phạm phi ngữ cảnh .....15 Bảng 2. Một văn phạm phi ngữ cảnh đơn giản .........................................................20 Bảng 3. Quá trình phân tích từ trên xuống................................................................35 Bảng 4. Phân tích từ trên xuống kết hợp quay lui cho mạng chuyển đệ quy............36 Khoá luận tốt nghiệp 5 Bảng 5. Tập luật của văn phạm tiếng Việt ................................................................48 Bảng 6. Tập luật của văn phạm tiếng Anh................................................................50 Khoá luận tốt nghiệp 6 Chương 1. Mở đầu Khoá luận tốt nghiệp Chương 1. Mở đầu 1.1. Tổng quan về vấn đề phân tích văn bản Phân tích và kiểm tra tính chính xác của văn bản là một vấn đề lớn và phức tạp. Quá trình này thường được chia thành 4 giai đoạn chính: phân tích từ vựng, phân tích cú pháp, phân tích ngữ nghĩa và phân tích thực chứng. • • • • Phân tích từ vựng. Là quá trình phân tích hình thái các từ vựng tạo nên văn bản, từ đó kiểm tra được tính đúng đắn của âm tiết và từ. Phân tích cú pháp. Là quá trình đưa ra mô tả quan hệ về vai trò ngữ pháp của các từ, các cụm từ (hoặc ngữ) trong câu, từ đó xây dựng cấu trúc câu. Phân tích ngữ nghĩa. Mục đích của phân tích ngữ nghĩa là kiểm tra ý nghĩa của câu có mâu thuẫn với ý nghĩa cả đoạn hay không. Dựa trên mối liên hệ logic về nghĩa giữa các cụm từ trong câu và mối liên hệ giữa các câu trong đoạn, hệ thống sẽ xác định được một phần ý nghĩa của câu trong ngữ cảnh của cả đoạn. Phân tích thực chứng. Là quá trình phân tích nhằm xác định ý nghĩa của câu dựa trên mối liên hệ của câu với hiện thực. Ý nghĩa thực tế của câu phụ thuộc rất nhiều vào ngữ cảnh diễn ra lời nói. Do vậy, quá trình phân tích này rất khó thực hiện được bằng máy tính. Thường thì việc phân tích câu chỉ dừng ở phân tích ngữ nghĩa, còn việc phân tích thực chứng do người dùng tự quyết định. 1.2. Bài toán phân tích cú pháp Phân tích cú pháp đưa ra mô tả về quan hệ và vai trò ngữ pháp của các từ, các cụm từ (hoặc ngữ) trong câu, đồng thời đưa ra hình thái của câu. Đầu vào của giai đoạn này là câu đã được phân tách từ, trong đó mỗi từ có đặc điểm hình thái xác định. Quá trình kiểm tra cú pháp tiến hành phân tích và tổ hợp các từ ở đầu vào, dựa trên các luật cú pháp để loại bỏ các trường hợp bất quy tắc và từng bước dựng lên cấu trúc cú pháp (cây phân tích) của câu. Kết quả cần đạt được là hình thái của câu. Cú pháp là chủ đề nghiên cứu của hai cộng đồng gồm những người làm ngôn ngữ và những người làm tin học. Với những người làm ngôn ngữ thì ngôn ngữ là đối tượng nghiên cứu, cú pháp là một trong các cấp độ phải mô tả. Với những người làm tin học thì cần làm cho máy tính phân tích được cú pháp với hai mục tiêu là xây dựng các ứng dụng, qua đó phục vụ việc nghiên cứu ngôn ngữ; đối tượng nghiên cứu của họ là các hệ hình thức và các thuật toán. Chương 1. Mở đầu Khoá luận tốt nghiệp 8 Khi xét về cấu trúc cú pháp có hai khía cạnh, một là thứ tự của các từ, trong đó có những ràng buộc về cấu tạo câu đúng và chức năng của các thành phần trong câu (chủ ngữ, vị ngữ...); hai là những biến tố (về hình thái, ví dụ các thì, số ít, số nhiều, giống...) quy định ràng buộc về cấu tạo và chức năng ngữ pháp. Với tiếng Việt, không có khía cạnh thứ hai. Để phân tích cấu trúc của một câu ta cần đến hai thứ: Thứ nhất là ngữ pháp của ngôn ngữ, là đặc tả hình thức cấu trúc của ngôn ngữ và thứ hai là các kỹ thuật phân tích, là các phương thức phân tích để tìm ra cấu trúc ngữ pháp của câu, hoặc kết luận câu sai ngữ pháp. Để đặc tả ngữ pháp, người ta đưa ra các mô hình cú pháp của ngôn ngữ. 1.3. Nội dung khoá luận Khoá luận gồm hai nội dung chính. Nội dung thứ nhất là trình bày hai mô hình truyền thống dùng để phân tích cú pháp của ngôn ngữ tự nhiên, gồm các văn phạm phi ngữ cảnh và các mạng chuyển đệ quy. Trong khuôn khổ của khoá luận, em chỉ thực hiện phần nghiên cứu, cài đặt các thuật toán phân tích cho văn phạm phi ngữ cảnh và mạng chuyển đệ quy nhằm nắm chắc và làm chủ các kỹ thuật phân tích, các phần khác là triển vọng nghiên cứu trong tương lai gần. Có ba kỹ thuật phân tích được nghiên cứu là phân tích từ trên xuống, phân tích từ dưới lên và phân tích tổng hợp. Ðể tiện trong việc trình bày, toàn bộ các thuật toán được giải thích và minh hoạ trên bộ văn phạm đơn giản của tiếng Anh. Nội dung thứ hai là xây dựng tập từ loại và văn phạm đơn giản cho tiếng Việt, thiết kế cấu trúc dữ liệu và cài đặt các thuật toán phân tích, đánh giá kết quả. Vì khuôn khổ của khoá luận có hạn, nên em chỉ trình bày phần cài đặt thuật toán phân tích từ trên xuống cho văn phạm phi ngữ cảnh. Kết quả cần đạt được là hoàn thiện một chương trình phân tích cú pháp tiếng Việt đơn giản viết bằng ngôn ngữ lập trình Java, thể hiện kết quả phân tích bằng giao diện đồ hoạ dạng cây. Phần phụ lục của khoá luận trình bày bài toán tách từ vựng tiếng Việt - vấn đề tiền xử lý quan trọng trước khi bước vào phân tích cú pháp. Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp Chương 2. Văn phạm phi ngữ cảnh 2.1. Văn phạm và ngôn ngữ sinh bởi văn phạm Một tập hợp Χ ≠ φ (vô hạn hoặc hữu hạn) các đối tượng được gọi là một bảng chữ cái. Mỗi phần tử thuộc tập Χ được gọi là một chữ cái hay một ký hiệu. Ví dụ, bảng chữ cái tiếng Việt là Σ = {a, b, c, ..., y}. Mỗi dãy ký hiệu các phần tử của Χ: α = ai1ai2...ait, aij ∈ Χ, 1 ≤ j ≤ t được gọi là một từ hay một xâu trên bảng chữ cái Χ. Ví dụ ba, ca, con,... Tổng số vị trí của tất cả các ký hiệu xuất hiện trong từ α được gọi là độ dài của α, ký hiệu là |α|. Từ có độ dài bằng 0 được gọi là từ rỗng (trống), được ký hiệu là ε. Gọi Σ* là tập hợp gồm tất cả các từ trên bảng chữ cái Σ, kể cả từ rỗng. Mỗi một tập con của tập Σ* được gọi là một ngôn ngữ trên bảng chữ cái Σ. Tập rỗng cũng là một ngôn ngữ trên bảng chữ cái tuỳ ý, được ký hiệu bằng φ. Giả sử có bảng chữ cái Σ, một văn phạm là một bộ bốn G = (Σ, V, σ, P), trong đó: ¾ Σ là bảng chữ cái chính hay bảng chữ cái từ hay tập ký hiệu kết ¾ V là bảng chữ cái phụ hay bảng chữ cái làm việc hay tập ký hiệu không kết ¾ σ ∈ V là một ký hiệu phụ, gọi là tiền đề hay ký hiệu xuất phát hay ký hiệu khởi đầu ¾ P = {ϕ → ψ⎪ϕ∈(Σ ∪V)*\{e}, ψ ∈(Σ ∪V)*, → ∉ (Σ ∪V)} gọi là tập quy tắc sinh hay tập quy tắc thế của văn phạm G. r = ϕ → ψ là một quy tắc sinh hay quy tắc thế của văn phạm G, ϕ, ψ theo thứ tự được gọi là vế trái và vế phải của quy tắc r. Ví dụ, G = ({a, b, c}, {S, A, B}, S, P), trong đó P là S → ABBA AB → BAA AA → BcBa BcB → Aab A → B B → A B → C Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 10 Từ xâu ban đầu α = ΑΒ, bằng các quy tắc sinh đã cho ta có α = AB → β = BAA → γ = BBcBa. Ta nói rằng xâu α dẫn trực tiếp ra xâu β, dẫn gián tiếp ra xâu γ và viết là α ⇒ β. Tổng quát, giả sử α = α1ϕα2, β = α1ψα2, ϕ → ψ ∈ P thì ta nói rằng xâu α dẫn trực tiếp ra xâu β hoặc xâu β được dẫn trực tiếp từ xâu α. Một dãy từ ω0, ω1, ..., ωi, ωi+1, ..., ωm được gọi là một dẫn xuất trong văn phạm G nếu ∀i, ωi ⇒ ωi+1. Ta nói rằng xâu α dẫn gián tiếp ra xâu β hay xâu β được dẫn gián tiếp từ α trong văn phạm G, và viết là α β nếu hoặc α = β hoặc tồn tại một dẫn xuất ω mà từ đầu tiên là α và từ cuối cùng là β. *⇒ Tập {x ∈ Σ* | σ x} gồm tất cả các từ thuộc bảng chữ cái chính mà mỗi từ này được dẫn gián tiếp từ tiền đề gọi là ngôn ngữ sinh bởi văn phạm G, ký hiệu là L(G). *⇒ Để việc trình bày được ngắn gọn và phân biệt ý nghĩa của các ký hiệu trong văn phạm, ta quy ước: dùng các chữ cái in hoa để chỉ các ký hiệu không kết, các chữ cái thường để chỉ các ký hiệu kết và dùng các ký tự Hy Lạp để chỉ các xâu. 2.2. Văn phạm phi ngữ cảnh Theo cách phân loại của Chomsky, văn phạm được chia thành ba loại, gồm ¾ Văn phạm cảm ngữ cảnh, hoặc văn phạm biến đổi. Độ dài của xâu α bên trái mỗi quy tắc phải nhỏ hơn hoặc bằng độ dài của xâu β bên vế phải của quy tắc đó. Nghĩa là mọi sản xuất đều có dạng λAρ → λαρ, trong đó λ và ρ là các xâu bất kỳ (có thể rỗng). λ và ρ có thể coi như vế trái và vế phải của văn cảnh ở đó ký hiệu không kết A được viết lại thành xâu không rỗng α, chính vì vậy nên văn phạm loại này được gọi là cảm ngữ cảnh. Các quy tắc sinh cảm ngữ cảnh có thể dùng để chuyển một câu từ dạng chủ động sang dạng bị động tương ứng. ¾ Văn phạm phi ngữ cảnh, hay văn phạm cấu trúc cụm. Mọi quy tắc đều có dạng A → α, trong đó A là ký hiệu không kết và α là xâu bất kỳ. ¾ Văn phạm chính quy, hay văn phạm tuyến tính phải. Mọi quy tắc đều có một trong hai dạng sau: A → t hoặc A → tN, trong đó A và N là các ký hiệu không kết, t là ký hiệu kết. Các văn phạm chính quy không đủ mạnh để mô tả ngôn ngữ tự nhiên (thậm chí cả các ngôn ngữ lập trình). Chúng thường được dùng để mô tả các bộ phận của ngôn ngữ và có thế mạnh là tốc độ phân tích nhanh. Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 11 Hình 1. Phân loại văn phạm của Chomsky Các quy tắc sinh của văn phạm phi ngữ cảnh G có thể được chuẩn hoá theo hai cách mà không làm thay đổi khả năng sinh của nó, gồm dạng chuẩn Chomsky và dạng chuẩn Greibach. Trong dạng chuẩn Chomsky, các quy tắc có dạng A → BC hoặc A → a. Với dạng chuẩn Greibach, các qui tắc có dạng A → aα. Cây dẫn xuất của văn phạm là một cây được đánh dấu bởi các ký hiệu kết thúc hoặc không kết thúc sao cho mỗi nút mẹ là vế trái của một qui tắc sinh mà vế trái của qui tắc đó lập nên bởi dãy các kí hiệu của các nút con. Hầu hết các ngôn ngữ lập trình đều được mô tả bằng văn phạm phi ngữ cảnh. Chẳng hạn, câu lệnh lặp while được mô tả bởi các quy tắc phi ngữ cảnh sau: WhileStatement → while Condition do StatementList end StatementList → Statement StatementList → Statement ; StatementList Văn phạm phi ngữ cảnh cũng được lựa chọn để biểu diễn cấu trúc cú pháp của các ngôn ngữ tự nhiên bởi hai lý do: ¾ Nó đủ mạnh để mô tả hầu hết những cấu trúc của ngôn ngữ tự nhiên ¾ Nó vừa đủ hạn chế để xây dựng những trình phân tích câu hiệu quả Sau đây ta đi vào tìm hiểu việc vận dụng các văn phạm phi ngữ cảnh và các thuật toán phân tích để biểu diễn ngôn ngữ tự nhiên và xây dựng các trình phân tích cú pháp. 2.3. Biểu diễn cấu trúc câu Văn phạm phi ngữ cảnh khi được sử dụng để biểu diễn cấu trúc cú pháp thì các ký hiệu kết thúc tương ứng với các từ trong ngôn ngữ, các ký hiệu không kết thúc tương ứng với các phân loại cú pháp (hay từ loại). Tiên đề biểu diễn phân loại "câu". Các quy tắc sinh biểu diễn các quy tắc ngữ pháp. Ta có thể chia chúng thành các qui tắc từ Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 12 vựng (chứa ít nhất một ký hiệu kết thúc) và các qui tắc ngữ đoạn (không chứa ký hiệu kết thúc nào). Với mỗi từ trong từ vựng có một tập các qui tắc sinh chứa từ này trong vế phải. Một cây dẫn xuất cũng được gọi là cây cú pháp cho một phân tích của một ngữ đoạn thành các thành phần kế tiếp. Với lớp câu kể đơn giản nhất trong tiếng Anh, ta dùng bộ quy tắc sinh sau đây: S → NP VP VP → VERB NP NP → NAME NP → ART NOUN Các ký hiệu không thể phân tách thêm được nữa như NOUN, ART, VERB trong văn phạm ví dụ trên là các ký hiệu kết. Các ký hiệu khác, gồm S, NP, VP là các ký hiệu không kết. Mỗi ký hiệu kết biểu diễn một từ loại. Thông thường, một từ có nhiều kiểu từ loại khác nhau, ví dụ, từ can có thể là VERB hoặc NOUN. Có hai phương pháp điển hình dùng để phân tích văn phạm phi ngữ cảnh, là phân tích từ trên xuống và phân tích từ dưới lên. ¾ Phân tích từ trên xuống: Xuất phát từ ký hiệu đầu S, áp dụng các suy dẫn tiến hành từ trái qua phải thử tạo ra câu cần phân tích ¾ Phân tích từ dưới lên: Xuất phát từ chính câu vào, áp dụng thu gọn các suy dẫn phải, tiến hành từ phải qua trái để đi tới ký hiệu đầu. Ví dụ, xét câu "John ate the cat". Phân tích từ trên xuống như sau S → NP VP → NAME VP → John VP → John VERB NP → John ate NP → John ate ART NOUN → John ate the NOUN → John ate the cat Phân tích từ dưới lên thì ngược lại. Một văn phạm rộng hơn dùng cho lớp câu kể của tiếng Anh là Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 13 1. S → NP VP 2. NP → ART NOUN 3. NP → NAME 4. PP → PREP NP 5. VP → VERB 6. VP → VERB NP 7. VP → VERB NP NP 8. VP → VERB PP Trong đó, các ký hiệu và từ loại tương ứng được cho trong bảng sau: Ký hiệu Từ loại tương ứng S Câu NP cụm danh từ VP cụm động từ PP cụm giới từ NOUN danh từ ART mạo từ VERB động từ NAME tên riêng Theo văn phạm này thì một số câu như ¾ John saw the cat by the pond ¾ The dog barked in the house là chấp nhận được, nhưng nó cũng chấp nhận những câu không có nghĩa như ¾ The dog allows the house ¾ John barked the cat by the pond Với câu John ate the cat, ta có cây phân tích như Hình 2. Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 14 Hình 2. Cây biểu diễn câu John ate the cat 2.4. Phân tích từ trên xuống Bây giờ ta xây dựng trình phân tích từ trên xuống cho văn phạm phi ngữ cảnh. Để mô tả một trạng thái của trình phân tích ta dùng hai thông tin: ¾ Vị trí hiện tại. Lưu lại phần nào của câu đã được phân tích rồi ¾ Trạng thái hiện tại. Là một xâu các ký hiệu sinh ra từ các quy tắc của văn phạm Ở mỗi bước, trình phân tích xét ký hiệu nằm bên trái nhất của danh sách. Nếu nó có tên là một từ loại của từ kế tiếp thì xoá ký hiệu này và cập nhật lại vị trí hiện tại một cách thích hợp. Sử dụng văn phạm tiếng Anh gồm 8 quy tắc đã nêu ở phần trước, để tiện theo dõi, ta viết lại ở đây: 1. S → NP VP 5. VP → VERB 2. NP → ART NOUN 6. VP → VERB NP 3. NP → NAME 7. VP → VERB NP PP 4. PP → PREP NP 8. VP → VERB PP Ta có phân tích từ trên xuống của câu 1 The 2 dogs 3 cried 4 như trên Bảng 1. Bước Trạng thái hiện tại Trạng thái lưu Vị trí Nhận xét 1. (S) 1 vị trí khởi tạo 2. (NP VP) 1 viết lại S theo quy tắc 1 3. (ART NOUN VP) 1 viết lại NP theo các quy tắc 2, 3 Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 15 (NAME VP) 1 4. (NOUN VP) 2 so khớp ART với the (NAME VP) 1 5. (VP) 3 so khớp NOUN với dogs (NAME VP) 1 6. (VERB) 3 viết lại VP theo các quy tắc 5-8 (VERB NP) 3 (VERB NP PP) 3 (VERB PP) 3 (NAME VP) 1 7. quá trình phân tích thành công, vì VERB so khớp với cried, và lúc này, danh sách các ký hiệu của văn phạm là rỗng, câu cần phân tích rỗng. Bảng 1. Phân tích từ trên xuống, ưu tiên chiều sâu cho văn phạm phi ngữ cảnh Chú ý rằng trình phân tích đưa các trạng thái được sao lưu vào một ngăn xếp. 2.5. Phân tích từ dưới lên Ðiểm khác nhau chủ yếu giữa phân tích từ trên xuống và phân tích từ dưới lên là cách sử dụng các quy tắc sinh. Ví dụ, xét quy tắc NP → ART ADJ NOUN Trong phân tích từ trên xuống, khi gặp NP, ta thay nó bằng dãy ART ADJ NOUN. Trong phân tích từ dưới lên, ta sử dụng quy tắc này theo cách ngược lại, tức nếu gặp dãy ART ADJ NOUN thì ta thay nó bằng NP. Như vậy, công việc cơ bản của phân tích từ dưới lên là lấy ra một dãy các ký hiệu và so sánh nó với vế phải của các quy tắc. Việc so khớp luôn được xem xét từ một ký hiệu, gọi là khoá. Ðể tìm ra những quy tắc khớp với một xâu gồm cả khoá, ta tìm những quy tắc bắt đầu bằng khoá này, hoặc tìm những quy tắc bắt đầu bằng các khoá trước đó và cần khoá hiện tại để hoàn thành quy tắc hoặc thác triển quy tắc. Ví dụ, xét văn phạm sau: 1. S → NP VP 2. NP → ART ADJ NOUN 3. NP → ART NOUN 4. NP → ADJ NOUN Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 16 5. VP → AUX VERB NP 6. VP → VERB NP Nếu ta bắt đầu bằng khoá ART thì các quy tắc 2 và 3 là khớp. Ta ghi lại điều này cho bước xử lý tiếp theo, các quy tắc 2, 3 có thể đi tiếp được ở sau điểm ART. Ta biểu diễn điều này bằng cách viết lại các quy tắc đó cùng với dấu chấm tròn (ο) chỉ rằng ta đã đi đến đâu: 2'. NP → ART ο ADJ NOUN 3'. NP → ART ο NOUN Nếu khoá sau đó là ADJ thì có thể có quy tắc 4 và quy tắc 2' được thác triển tiếp như sau: 2''. NP → ART ADJ ο NOUN Các trạng thái trong phân tích từ dưới lên được lưu dưới dạng một cấu trúc gọi là biểu đồ (chart). Biểu đồ là một bản ghi vị trí của các từ và các cấu trúc mới phát sinh từ câu đang phân tích. Các cung trên biểu đồ lưu giữ các quy tắc đã so khớp trước đó nhưng chưa hoàn thiện. Ví dụ, sau khi đã biết một ART và sau đó là một ADJ trong ví dụ trên, ta sẽ có biểu đồ sau (Hình 3): Hình 3. Biểu đồ sau khi tìm thấy một ADJ tại vị trí 2 Có hai thành phần: ART1, ADJ1 và 4 cung hoạt động; 2 NP bắt đầu bằng ART từ 1 đến 2, 1 NP bắt đầu bằng ART ADJ từ 1 đến 3, 1 NP bắt đầu bằng ADJ từ 2 đến 3. Thuật toán phân tích cụ thể như sau: Có hai cấu trúc dữ liệu là biểu đồ và danh sách khoá ¾ biểu đồ: lưu tất cả các thông tin về các thành phần hoàn chỉnh và các cung hoạt động ¾ danh sách khoá: là một ngăn xếp các thành phần hoàn chỉnh đã được đưa vào biểu đồ. Mỗi khi danh sách khoá rỗng thì đọc từ tiếp theo của câu và đưa mọi từ loại có thể của nó vào danh sách Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 17 Ta coi mỗi ký hiệu của quy tắc tương đương với một thành phần của cung. Như vậy ta nói ART, ADJ, NOUN là 3 thành phần của cung 2'. NP → ART ο ADJ NOUN Việc đưa một thành phần C vào giữa hai vị trí p1 và p2 trên biểu đồ gồm các bước sau: 1. đưa C vào giữa p1 và p2; 2. nếu C bắt đầu một quy tắc r của văn phạm thì thêm một cung biểu diễn quy tắc r từ p1 đến p2; 3. với mỗi cung A đi từ p0 đến p1 (điểm bắt đầu của C), nếu C là thành phần con kế tiếp của A thì thêm một cung từ p0 đến p2 biểu diễn quy tắc A đã cập nhật. 4. nếu một cung nào đó trong số các cung được thêm vào tại các bước 2, 3 là một quy tắc đã hoàn chỉnh thì thêm vào danh sách khoá một thành phần mới có tên là vế trái của quy tắc đó. Ví dụ, xét thuật toán này với câu cần phân tích là The large can can hold the water, với từ điển sau: the ART large ADJ can AUX, NOUN, VERB hold NOUN, VERB water NOUN, VERB Ban đầu danh sách khoá là rỗng, do đó từ the được đọc và thành phần ART1 được đặt vào danh sách. • Vào ART1: (the từ 1 tới 2). Thêm cung NP → ART ο ADJ NOUN từ 1 tới 2, thêm cung NP → ART ο NOUN từ 1 tới 2; Cả hai cung này được thêm vào tại bước 2 của thuật toán. Sau đó từ large được đọc, tạo ra thành phần ADJ1. • Vào ADJ1: (large từ 2 tới 3). Thêm cung NP → ADJ ο NOUN từ 2 tới 3 (bước 2), thêm cung NP → ART ADJ ο NOUN từ 1 tới 3 (bước 3); ở đây, cung thứ Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 18 hai được thêm vào là do sự thác triển của cung đầu tiên tại bước 3 của thuật toán. Lúc này, ta được biểu đồ như trên Hình 3. Với từ tiếp theo can, có 3 thành phần được tạo ra là NOUN1, AUX1, và VERB1. • Vào NOUN1: (can từ 3 đến 4). Không có cung nào được thêm vào trong bước 2, song có hai cung được hoàn thiện ở bước 3 vì NOUN1 sinh ra 2 NP, 2NP này được đưa danh sách khoá ở bước 4, NP thứ nhất từ 1 đến 4 được xây dựng từ quy tắc 2, NP thứ hai từ 2 đến 4 được xây dựng từ quy tắc 4. Hai NP này bây giờ nằm trên đỉnh của ngăn xếp các khoá. • Vào NP1: NP từ 1 tới 4. Thêm cung S → NP ο VP từ 1 tới 4. • Vào NP2: NP từ 2 tới 4. Thêm cung S → NP ο VP từ 2 tới 4. Bây giờ biểu đồ có dạng như Hình 4. Hình 4. Sau khi phân tích can là NOUN Bây giờ xét tới các từ loại khác của can. • Vào AUX1: (can từ 3 đến 4). Thêm cung VP → AUX ο VERB NP từ 3 tới 4. • Vào VERB1: (can từ 3 đến 4). Thêm cung VP → VERB ο NP từ 3 tới 4. Từ tiếp theo lại là can và NOUN2, AUX2, VERB2 được tạo ra. • Vào NOUN2: (can từ 4 đến 5). Không cung nào được thêm vào. • Vào AUX2: (can từ 4 đến 5). Thêm cung VP → AUX ο VERB NP từ 4 tới 5. • Vào VERB2: (can từ 4 đến 5). Thêm cung VP → VERB ο NP từ 4 tới 5, thêm cung VP → AUX VERB ο NP từ 3 tới 5. Từ tiếp theo là hold và NOUN3, VERB3 được tạo ra. • Vào NOUN3: (hold từ 5 đến 6). Không cung nào được thêm vào. Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 19 • Vào VERB3: (hold từ 5 đến 6). Thêm cung VP → VERB ο NP từ 5 tới 6, thêm cung VP → AUX VERB ο NP từ 4 tới 6. Ta được biểu đồ như Hình 5. Hình 5. Biểu đồ sau khi thêm hold • Vào ART2: (the từ 6 đến 7). Thêm cung NP → ART ο ADJ NOUN từ 6 tới 7, thêm cung NP → ART ο NOUN từ 6 tới 7. • Vào NOUN4: (water từ 7 đến 8). Không có cung nào được thêm vào trong bước 2, một NP, NP3 từ 6 tới 8 được đẩy vào danh sách khoá do hoàn thành cung NP → ART ο NOUN từ 6 tới 7. • Vào NP3: (the water từ 6 đến 8). Một VP, VP1 từ 4 tới 8 được đẩy vào danh sách khoá do hoàn thành quy tắc VP → AUX VERB ο NP từ 4 tới 6; một VP, VP2 từ 5 tới 8 được đẩy vào danh sách khoá do hoàn thành quy tắc VP → VERB ο NP từ 5 tới 6. Ðồ thị tiếp theo của giai đoạn này như Hình 6 (chỉ vẽ những cung sử dụng trong phân tích tiếp theo). Hình 6. Biểu đồ sau khi tìm được tất cả các NP • Vào VP2 (hold the water từ 5 đến 8). Không cung nào được thêm vào. Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 20 • Vào VP1 (can hold the water từ 4 đến 8). Một S, S1 từ 1 tới 8 được thêm vào danh sách khoá bởi hoàn thiện cung S → NP ο VP từ 1 tới 4, một S, S2 từ 2 tới 8 được thêm vào danh sách khoá bởi hoàn thiện cung S → NP ο VP từ 2 tới 4. Vì ta đã thu được S gồm toàn bộ câu cần phân tích, nên việc phân tích là thành công. Nếu muốn tìm tất cả các cách phân tích câu có thể thì cần tiếp tục phân tích cho tới khi danh sách khoá là rỗng. Biểu đồ cuối cùng như Hình 7. Hình 7. Biểu đồ cuối cùng 2.6. Đánh giá hai phương pháp phân tích trên Phân tích từ dưới lên và phân tích từ trên xuống đều có những ưu nhược điểm riêng. Với phân tích từ trên xuống, ưu điểm là ta không cần quan tâm rằng trong câu đúng cú pháp không thể có những từ loại nằm sai vị trí. Nguyên nhân của ưu điểm này là do trình phân tích bắt đầu từ một từ loại và kiểm tra xem từ hiện tại có đúng là thuộc vào lớp từ loại đó hay không. Ví dụ, nếu sử dụng văn phạm 1. S → NP VP 5. NP → ART ADJ NOUN 2. S → NP AUX VERB 6. NP → ADJ NOUN 3. S → NP VERB 7. VP → AUX VERB NP 4. NP → ART NOUN 8. VP → VERB NP Bảng 2. Một văn phạm phi ngữ cảnh đơn giản thì trình phân tích từ trên xuống của câu The can fall sẽ cho rằng câu S bắt đầu bằng một NP, NP bắt đầu bằng ART, sau đó là ADJ hoặc NOUN. Vì can là NOUN, nên nó tìm thấy một NP và do đó các nghĩa AUX hoặc VERB của can không bao giờ được xét. Nhưng phân tích từ trên xuống lại có thể tốn nhiều thời gian bởi những công việc tương tự nhau có khi phải lặp lại nhiều lần. Giả sử ta cần phân tích câu The bird sang cũng với văn phạm trên. Ban đầu, trình phân tích sử dụng quy tắc 1 tìm ra một NP the bird, sau đó sử dụng quy tắc 8 cho VP, nó tìm thấy VERB, nhưng sau đó Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 21 phải là NP thì không thoả mãn. Do đó nó quay lại và thử tìm một phân tích khác của S. Trình phân tích thử dùng quy tắc 2 và NP the bird lại được phân tích lại, nhưng lần này không tìm thấy AUX, nó quay lại lần nữa để thử với quy tắc 3. Lần này thì thành công và như vậy việc phân tích NP the bird được thực hiện 3 lần. Nhược điểm này được khắc phục trong phân tích từ dưới lên. Trong ví dụ trên, NP the bird chỉ được xây dựng một lần và đối với câu này, chỉ quy tắc 3 là phù hợp. Nhưng trình phân tích từ dưới lên lại phải xem xét tất cả các từ loại có thể có của một từ và xây dựng những cấu trúc có thể không hợp lệ. Ví dụ, trong phần trước, khi phân tích câu The large can can hold the water, ta có biểu đồ cuối cùng như Hình 7. Ở đây, có nhiều cấu trúc không thể xảy ra, chẳng hạn, theo biểu đồ này thì từ vị trí 2 đến vị trí 7 có thể coi là một câu, nhưng thực tế không thể có câu nào có dạng ART S. 2.7. Phương pháp phân tích tổng hợp Ta sẽ thiết kế một trình phân tích vừa có những ưu điểm của hai kỹ thuật phân tích từ trên xuống và từ dưới lên lại không có những nhược điểm như trên. Phương pháp là vừa xây dựng một trình phân tích từ trên xuống vừa bổ sung từng thành phần vào biểu đồ. Trong quá trình phân tích, trước khi ta viết lại một ký hiệu để lấy ra những thành phần mới, ta kiểm tra xem thành phần đó đã nằm trong biểu đồ hay chưa. Nếu nó đã nằm trong biểu đồ thì ta dùng luôn mà không phải sử dụng các quy tắc của văn phạm để viết lại thành phần đó nữa. Ðể thực hiện được điều đó, ta chỉ cần sửa đổi lại tí chút thuật toán phân tích từ trên xuống. Xét câu 1 The 2 green 3 water 4 evaporated 5, trong đó green có thể là ADJ hoặc NOUN, water là NOUN hoặc VERB. Trạng thái khởi đầu như sau Trạng thái hiện tại Trạng thái lưu Vị trí (S) nil 1 Sử dụng văn phạm ở Bảng 2, viết lại S theo các quy tắc 1, 2 và 3, ta có tình huống sau Trạng thái hiện tại Trạng thái lưu Vị trí (NP VP) 1 Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 22 (NP AUX VERB) 1 (NP VERB) 1 Sử dụng các quy tắc 4, 5 và 6 để viết lại NP của trạng thái hiện tại sinh ra Trạng thái hiện tại Trạng thái lưu Vị trí (ART NOUN VP) 1 (ART ADJ NOUN VP) 1 (ADJ NOUN VP) 1 (NP AUX VERB) 1 (NP VERB) 1 Câu cần phân tích được kiểm tra xem có bắt đầu bằng một ART và sau đó là một NOUN hay không, việc này thành công, trình phân tích xây dựng được một NP trên biểu đồ. Nhưng ở đây chưa có thông tin nào ghi lại rằng dãy ART NOUN đã sinh ra một NP cả. Ðể ghi lại NP, ngay khi một ký hiệu được viết lại, trình phân tích đánh dấu ký hiệu đó và đưa nó vào một danh sách, đồng thời ghi lại vị trí bắt đầu của cụm từ. Ví dụ, nếu cụm NP được viết lại ở vị trí 1, trình phân tích sẽ đặt một cấu trúc mới [NP1], gọi là cờ dựng vào trong danh sách. Sau đó, trong quá trình phân tích, nếu phải quay lại [NP1] thì nó nhận thấy rằng cấu trúc NP bắt đầu từ vị trí 1 đã được thực hiện. Thuật toán trên được viết lại cụ thể để xử lý một vị trí nào đó như sau: 1. Nếu ký hiệu bên trái nhất của trạng thái hiện tại là tên của một điểm vào trong biểu đồ, thì sinh ra một (hay nhiều) trạng thái mới bằng cách xoá ký hiệu đó đi và cập nhật lại vị trí hiện tại trong câu thành (các) vị trí sau (các) điểm vào của biểu đồ. Ví dụ, cho vị trí và biểu đồ sau đây. Trạng thái hiện tại Trạng thái lưu Vị trí (NP VP) nil 1 Hình 8. Vị trí và biểu đồ ban đầu Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 23 Trên biểu đồ có hai NP và sinh ra hai trạng thái mới. Một trở thành trạng thái hiện tại mới, trạng thái còn lại được lưu. Vậy, ta có kết quả Trạng thái hiện tại Trạng thái lưu Vị trí (VP) 2 (VP) 4 2. Nếu như ký hiệu bên trái nhất là một cờ dựng, chẳng hạn [NP1], thì thêm một thành phần NP vào biểu đồ trải từ vị trí bắt đầu (1) cho tới vị trí hiện tại. Chẳng hạn, cho vị trí hiện tại của trạng thái ([NP2] VP) là 5, ta sẽ thêm một NP vào biểu đồ từ vị trí 2 tới vị trí 5. 3. Ngược lại, nếu ký hiệu đó là một ký hiệu kết, thì thêm một cờ dựng vào vị trí đó và viết lại ký hiệu này theo các quy tắc của văn phạm. Ví dụ, cho trạng thái (NP VP) tại vị trí 1 và một biểu đồ trống, theo văn phạm ở trên, ta sẽ sinh ra ba trạng thái mới là: (ART NOUN [NP1] VP), (ART ADJ NOUN [NP1] VP), và (ADJ NOUN [NP1] VP), tất cả đều ở vị trí 1. 4. Nếu không xảy ra các trường hợp trên thì trạng thái này không thoả, một trạng thái lưu được lấy ra làm trạng thái hiện tại. Bây giờ, sử dụng thuật toán này, ta xét lại quá trình phân tích câu The green water evaporated. Nếu ta bắt đầu bằng ký hiệu S và vị trí 1, viết lại ký hiệu này, ta được Trạng thái hiện tại Trạng thái lưu Vị trí (NP VP [S1]) 1 (NP AUX VERB [S1]) 1 (NP VERB [S1]) 1 Viết lại NP theo bước 4 trong thuật toán, ta được Trạng thái hiện tại Trạng thái lưu Vị trí (ART NOUN [NP1] VP [S1]) 1 (ART ADJ NOUN [NP1] VP [S1]) 1 (ADJ NOUN [NP1] VP [S1]) 1 (NP AUX VERB [S1]) 1 (NP VERB [S1]) 1 Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 24 Ta kiểm tra thấy câu vào có một ART và một NOUN là đúng đắn. Sau thao tác này trạng thái hiện tại là ([NP1] VP [S1]) tại vị trí 3. Theo bước 2 của thuật toán, cờ dựng [NP1] được xử lý, bằng việc thêm một cấu trúc NP là [NP1] vào biểu đồ từ vị trí 1 tới vị trí 3. Khi đó, ta thu được trạng thái của quá trình phân tích và biểu đồ như sau: Trạng thái hiện tại Trạng thái lưu Vị trí (VP [S1]) 3 (ART ADJ NOUN [NP1] VP [S1]) 1 (ADJ NOUN [NP1] VP [S1]) 1 (NP AUX VERB [S1]) 1 (NP VERB [S1]) 1 Hình 9. Biểu đồ sau khi phân tích cụm NP đầu tiên Viết lại VP sẽ có trạng thái sau Trạng thái hiện tại Trạng thái lưu Vị trí (AUX VERB NP [VP4] [S1]) 3 (VERB NP [VP4] [S1]) 3 (ART ADJ NOUN [NP1] VP [S1]) 1 (ADJ NOUN [NP1] VP [S1]) 1 (NP AUX VERB [S1]) 1 (NP VERB [S1]) 1 Ta không chấp nhận trạng thái hiện tại vì water không phải là một AUX. Trạng thái lưu đầu tiên trở thành trạng thái hiện tại, trường hợp này mặc dù water là một VERB, nhưng sau đó vì không có NP nào theo sau VERB nên trạng thái này cũng bị loại. Trạng thái lưu tiếp theo được lấy ra làm trạng thái hiện tại. Câu cần phân tích có ART (the) ở vị trí 1, ADJ (green) ở vị trí 2, và NOUN (water) ở vị trí 3 nên sinh ra một NP thứ hai. Ta có tình huống và biểu đồ sau: Trạng thái hiện tại Trạng thái lưu Vị trí (VP [S1]) 4 Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 25 (ADJ NOUN [NP1] VP [S1]) 1 (NP AUX VERB [S1]) 1 (NP VERB [S1]) 1 Hình 10. Sau khi phân tích khả năng thứ hai của NP đầu tiên Viết lại VP ở vị trí 4 trong trạng thái hiện tại sinh ra tình huống mới sau Trạng thái hiện tại Trạng thái lưu Vị trí (AUX VERB NP [VP3] [S1]) 4 (VERB NP [VP3] [S1]) 4 (ADJ NOUN [NP1] VP [S1]) 1 (NP AUX VERB [S1]) 1 (NP VERB [S1]) 1 Vì không có AUX ở vị trí 4 nên trạng thái hiện tại không được chấp nhận. Trạng thái lưu thứ nhất cũng không thoả mãn, vì tuy có một VERB ở vị trí 4 nhưng sau đó lại không có NP. Trạng thái tiếp theo (ADJ NOUN [NP1] VP [S1]) cũng bị loại do the không phải là một ADJ. Chỉ còn lại hai trạng thái và biểu đồ như sau: Trạng thái hiện tại Trạng thái lưu Vị trí (NP AUX VERB [S1]) 1 (NP VERB [S1]) 1 Hình 11. Sau khi tìm kiếm một S theo quy tắc 1 bị thất bại Bây giờ ta đã kết thúc mọi phân tích có thể từ việc bắt đầu bằng S, viết lại nó theo quy tắc 1. Bây giờ là lúc những thành phần mà biểu đồ đã lưu lại trước đó được mang Chương 2. Văn phạm phi ngữ cảnh Khoá luận tốt nghiệp 26 ra để sử dụng. Thay vì áp dụng các quy tắc để viết lại NP tại vị trí 1, trình phân tích sử dụng hai NP đã có trên biểu đồ, sinh ra Trạng thái hiện tại Trạng thái lưu Vị trí (AUX VERB [S1]) 3 (AUX VERB [S1]) 4 (NP VERB [S1]) 1 Trạng thái hiện tại bị loại, do không có AUX nào tại vị trí 3. Tương tự, trạng thái lưu đầu tiên cũng không được chấp nhận, bởi không có AUX nào ở vị trí 4 cả. Trạng thái (NP VERB [S1]) là trạng thái cho phân tích đúng đắn duy nhất. Một lần nữa, dùng 2 NP đã có trên biểu đồ, sinh ra hai trạng thái sau: Trạng thái hiện tại Trạng thái lưu Vị trí (VERB [S1]) 3 (VERB [S1]) 4 Trạng thái hiện tại sinh ra một cấu trúc S từ vị trí 1 đến vị trí 4 nhưng lại bỏ sót evaporated. Trạng thái lưu còn lại sinh ra phân tích mong muốn, câu cần phân tích có cấu trúc như sau: Hình 12. Cấu trúc của câu cần phân tích Rõ ràng, chiến lược phân tích kết hợp từ trên xuống và từ dưới lên ưu việt hơn cả hai phương pháp phân tích đơn thuần nói trên; so với cách phân tích từ trên xuống thì cách phân tích này chỉ có một hạn chế là biểu đồ cần nhiều ô nhớ hơn. Nhưng trong phần lớn các trường hợp, so với lợi thế về thời gian phân tích thì phần ô nhớ mất thêm này là không đáng kể. Chương 3. Các mạng chuyển Khoá luận tốt nghiệp Chương 3. Các mạng chuyển Ngoài các hệ văn phạm, các mô hình mạng chuyển, nhất là các mạng chuyển đệ quy cũng được sử dụng rộng rãi để mô tả các cấu trúc cú pháp của ngôn ngữ tự nhiên. Các mạng chuyển có cơ sở là các máy trừu tượng, chúng được coi là những thiết bị nhận dạng văn phạm. Chính vì vậy, trước khi đi vào phần trình bày về các mạng chuyển, em trình bày khái quát về các máy trừu tượng, từ đơn giản nhất tới tổng quát nhất. 3.1. Văn phạm và ôtômát Văn phạm một mặt có thể coi là những định nghĩa cho các câu của một ngôn ngữ, mặt khác còn có thể coi là sự mô tả của một máy trừu tượng có khả năng đoán nhận hoặc sinh những xâu nằm trong ngôn ngữ đó. Những máy này được gọi (một cách trừu tượng) là các ôtômát, và độ phức tạp của những máy này tương ứng với độ phức tạp của các quy tắc sinh trong văn phạm. Mỗi máy có thể xem là một tập các trạng thái, một thiết bị vào có khả năng truy nhập mỗi lần một ký hiệu vào, và một đơn vị điều khiển có khả năng kiểm tra và đọc đầu vào, chuyển máy sang trạng thái khác. Ngoài ra, những máy này có thể có bộ nhớ, được đơn vị điều khiển truy nhập để lưu giữ hoặc kiểm tra các ký hiệu. Yếu tố quyết định năng lực tính toán của máy là độ phức tạp của bộ nhớ và những thao tác trên bộ nhớ. Những ôtômát đơn giản nhất là các máy hữu hạn trạng thái hay các ôtômát hữu hạn trạng thái (Finite State Automata -- FSA), các ngôn ngữ mà chúng đoán nhận gọi là các ngôn ngữ chính quy. Ngôn ngữ chính quy có đầy đủ các tính chất của ngôn ngữ phi ngữ cảnh và do đó luôn có thể đoán nhận được bằng một ôtômát với số trạng thái hữu hạn. Các máy hữu hạn trạng thái không có bộ nhớ trong, nên mọi thao tác hoàn toàn được quyết định bởi ký hiệu hiện đang được đọc và trạng thái hiện tại của máy. Để minh hoạ sự vận hành của các máy nói trên, ta xét văn phạm đơn giản sau: S → aB B → bB B → c Văn phạm này sinh ra ngôn ngữ chính quy abnc. Ôtômát tương đương với nó thường được biểu diễn bằng một sơ đồ trạng thái như hình vẽ sau: Chương 3. Các mạng chuyển Khoá luận tốt nghiệp 28 trong đó các nút biểu diễn các trạng thái và các cung biểu diễn các bước chuyển. Nút vuông chỉ rằng đó là trạng thái kết. Với ôtômát này, việc chuyển từ những quy tắc sinh sang sơ đồ trạng thái là: ký hiệu không kết chuyển thành trạng thái, ký hiệu kết chuyển thành bước chuyển. Sự hoạt động của ôtômát này như sau: việc tính toán bắt đầu từ một trạng thái được xác định trước gọi là trạng thái khởi đầu, ở đây là S; ký hiệu đầu tiên của xâu vào được kiểm tra xem có cung chuyển nào khớp với nó hay không; nếu có thì máy theo cung này chuyển tới trạng thái kế tiếp và tiêu thụ ký hiệu đó, đọc tiếp ký hiệu đứng sau. Quá trình này được tiếp tục cho tới khi máy bị dừng, ví dụ khi không cung chuyển nào là khớp nữa. Nếu máy dừng tại một trạng thái kết và xâu vào đã được tiêu thụ thì ta nói xâu đó đã được đoán nhận. Nếu ta thêm bộ nhớ hoạt động theo nguyên lý của danh sách vào sau ra trước (LIFO) vào ôtômát (ví dụ một ngăn xếp đẩy xuống), cùng với một số quy tắc điều khiển thì FSA sẽ chuyển thành ôtômát đẩy xuống (Push Down Automaton -- PDA). Các PDA chỉ có thể đoán nhận những ngôn ngữ phi ngữ cảnh. Nếu bỏ đi hạn chế về tổ chức ngăn xếp trong bộ nhớ trong, chỉ áp dụng ràng buộc quy định kích thước bộ nhớ là hàm tuyến tính theo độ dài của xâu vào, thì ta tạo ra một ôtômát mạnh hơn gọi là ôtômát bị chặn tuyến tính (Linear Bounded Automaton -- LBA). Nếu cần, ta có thể tổ chức bộ nhớ trong sao cho một phần bộ nhớ được tổ chức như một ngăn xếp, phần còn lại là bộ nhớ truy nhập ngẫu nhiên, khi đó sẽ giữ lại được mối liên hệ về mặt cấu trúc với lớp các PDA yếu hơn. Các LBA có khả năng đoán nhận một lớp rất tổng quát của ngôn ngữ, được định nghĩa bởi các văn phạm tuyến tính theo chiều dài, các ngôn ngữ này bao gồm cả các thành phần cấu trúc ngữ pháp cảm ngữ cảnh thường gặp trong ngôn ngữ. Sau cùng, nếu ta bỏ đi ràng buộc cuối cùng đối với bộ nhớ trong, cho phép nó có kích thước không hạn chế, khi đó ta được lớp ôtômát tổng quát nhất, gọi là các máy Turing (Turing Machines -- TMs). Văn phạm tương đương với nó là hệ thống viết lại không hạn chế, trong đó, các quy tắc sinh được phép viết lại bất kỳ cái gì cũng thành một thứ bất kỳ. Các máy Turing là sự trừu tượng tương tự của các máy tính tuần tự đa nhiệm nguyên thuỷ. Chương 3. Các mạng chuyển Khoá luận tốt nghiệp 29 Một trong những vấn đề đầu tiên của lý thuyết các ôtômát là câu hỏi về tính quyết định, được diễn tả hình thức là: có hay không một tiên nghiệm cho phép biết được một lớp các tính toán cho trước có kết thúc trong một thời gian hữu hạn hay không. Cụ thể là, bài toán đoán nhận một xâu không thuộc ngôn ngữ tương ứng với một ôtômát đã cho nói chung không thể quyết định được bởi các TM. Câu hỏi này, về nguyên tắc, là có thể trả lời được đối với các lớp ôtômát yếu hơn. 3.2. Các yếu tố cơ sở của mạng chuyển đệ quy Mạng chuyển đệ quy (recursive transition networks -- RTNs) được Wood đưa ra lần đầu tiên vào năm 1970, là một thiết bị nhận dạng các văn phạm phi ngữ cảnh. Xét văn phạm đơn giản sau 1. (a) S → NP (Aux) V (NP) PP* 1. (b) S → Aux NP V (NP) PP* 2. NP → (Det) (Quant) Adj* N* N PP* 3. PP → Prep NP Văn phạm này định nghĩa một ngôn ngữ phi ngữ cảnh trên bảng chữ cái {Aux, V, Det, Quant, Adj, N, Prep}. Ở đây có một mở rộng so với thông thường là các ngoặc tròn, chứa các phần tử tuỳ chọn, và dấu hoa thị dùng để chỉ ký hiệu đi kèm với nó có thể không có hoặc xuất hiện nhiều hơn một lần. Các vế phải của các quy tắc cũng có thể được xem như định nghĩa của các biểu thức của các ngôn ngữ chính quy, hay các biểu thức chính quy, tương ứng trên các bảng chữ cái {NP, Aux, V, PP} đối với quy tắc 1, {Det, Quant, Adj, N, PP} đối với quy tắc 2 và {Prep, PP} đối với quy tắc 3 -- do đó mỗi biểu thức có thể được diễn tả bằng một ôtômát hữu hạn trạng thái tương đương. Ví dụ, sơ đồ trạng thái của các ôtômát tương ứng với các quy tắc 1.(a) và 1.(b) là: Chương 3. Các mạng chuyển Khoá luận tốt nghiệp 30 trong đó ký hiệu JUMP chỉ các bước chuyển không có điều kiện không tiêu thụ ký hiệu. Nhìn vào biểu diễn này, ta thấy ngay rằng biểu diễn bước chuyển của các trạng thái cho phép ta ghép các vế phải của 1.(a) và 1.(b) thành một sơ đồ duy nhất, vì hai quy tắc là giống nhau kể từ ký hiệu V trở đi. Điều này sẽ làm việc mô tả các thông tin trong hai quy tắc ngắn gọn hơn so với hình thức viết lại. Ghép hai sơ đồ A1(a) và A1(b) ta sẽ được ba sơ đồ bước chuyển tương ứng với bốn quy tắc 1-3 như sau: Ở đây, ta gặp vấn đề với các cung chuyển NP trong A1 và A3 và PP trong A2. Để biểu diễn đúng theo máy hữu hạn trạng thái thì ta phải coi chúng như những ký hiệu kết, trong khi rõ ràng chúng là các ký hiệu không kết trong văn phạm ban đầu. Vậy nếu chúng không kết thì làm thế nào để đoán nhận được bởi các ôtômát hữu hạn trạng thái tương ứng? Cách giải thích hiển nhiên ở đây là ta cần có cách nhìn khác đối với những cung "không kết" này, ta coi ba ôtômát A1-A3 là một hệ. Bây giờ ta không đòi hỏi A1 phải đoán nhận ký hiệu NP, mà để nó tạm thời chuyển sang A2, và quay lại với thông tin NP đó có thể đoán nhận được tại vị trí vào hiện tại hay không. Tương tự, A2 phải Chương 3. Các mạng chuyển Khoá luận tốt nghiệp 31 chuyển trách nhiệm đoán nhận PP cho A3, đến lượt mình, A3 lại gọi A2 để đoán nhận NP. Rõ ràng là một FSA đơn thuần không thể đáp ứng được tiến trình đệ quy này, bởi nó không có cách nào để ghi nhớ đã xuất phát từ đâu và làm thế nào để quay lại đó sau khi kết thúc một quá trình trung gian. Tuy vậy, ta thấy rằng nếu ta dùng thêm một ngăn xếp để chuyển các FSA này thành một PDA thì thiết bị này hoàn toàn có khả năng quản lý mọi thao tác phụ gồm ghi nhớ và lấy lại các trạng thái. Khi điều khiển được chuyển sang một quá trình trung gian thì trạng thái hiện tại của máy được đẩy vào ngăn xếp, để khi kết thúc quá trình này máy sẽ quay lại đúng trạng thái đó. Trong thuật ngữ của RTN, việc chuyển điều khiển sang một trạng thái, giả sử NP, được gọi là PUSH NP. Khi ra khỏi trạng thái kết ta dùng một cung có nhãn POP để chỉ rằng khi quá trình kết thúc, máy quay lại trạng thái được lưu trong ngăn xếp. Ta cũng có thể sử dụng RTN để biểu diễn từ điển, thay vì dùng tập các quy tắc viết lại dạng Det → 'a' Det → 'the' Det → 'some' ta có thể sử dụng dạng chuyển như sau và gắn kết quả vào mạng văn phạm tương tự như A1-A3. Để tiện cho việc trình bày, ta có thể định nghĩa tập các hàm mà cung chuyển có thể gọi. Các hàm tìm kiếm trong từ điển hay sử dụng nhất là CAT, hàm này kiểm tra kiểu từ loại đã định nghĩa trước trong từ điển của từ hiện tại đang đọc vào. Các hàm khác được tóm lược trong bảng sau: Các hàm Ví dụ Cách dùng CAT noun đi qua được chỉ nếu từ loại của từ hiện tại có cùng tên WRD of đi qua được chỉ nếu từ hiện tại chính là từ này PUSH NP đẩy tới một mạng khác Chương 3. Các mạng chuyển Khoá luận tốt nghiệp 32 JUMP jump luôn có thể đi qua được POP pop chỉ việc đi qua được toàn bộ mạng chuyển Để kết thúc mục này, ta tóm tắt sự giống và khác nhau giữa mạng chuyển RTN và các ôtômát hữu hạn trạng thái FSA và ôtômát đẩy xuống PDA như sau: Giống nhau: ¾ RTN cũng như FSA và PDA đều có thể đoán nhận các câu sinh bởi các văn phạm cấu trúc câu. ¾ RTN tương đương với PDA về khả năng đoán nhận ngôn ngữ sinh bởi văn phạm phi ngữ cảnh (CFG) của Chomsky. ¾ Hoạt động của RTN cũng như FSA và PDA đều có thể được biểu diễn bằng các mạng chuyển. Khác nhau: ¾ Các cung và các đỉnh (trạng thái): Trong khi các trạng thái trong mạng chuyển của FSA có nhãn là các từ không kết thúc của văn phạm tương đương với ôtômat, các cung có nhãn là các từ cuối (cũng như vậy với PDA, trừ các cung rỗng và cung kết thúc pop), thì các cung của RTN có nhãn là các từ không kết thúc (trừ một số cung đặc biệt cũng có nhãn là từ cuối) của văn phạm tương đương, với các trạng thái được đánh dấu tuỳ ý. ¾ Các mạng con: Các mạng chuyển của FSA và PDA là các mạng đầy đủ, còn mạng chuyển của RTN thì được xử lý như là một tập các mạng con. Với mỗi ký hiệu có xuất hiện ở vế trái trong các qui tắc sinh của văn phạm tương đương được biểu diễn bằng một mạng con. ¾ RTN không đơn định, quá trình đoán nhận do vậy phải dùng phương pháp quay lui. ¾ Do đặc điểm của mô hình RTN là một tập các mạng chuyển con, việc đoán nhận câu trong RTN phải theo phương pháp xử lý từ trên xuống (xuất phát từ mạng con S – tức là mạng biểu diễn các quy tắc sinh có vế trái là tiên đề) và xử lý theo chiều sâu trước (phải đi qua từng mạng con trước khi chuyển sang cung tiếp theo). Chương 3. Các mạng chuyển Khoá luận tốt nghiệp 33 3.3. Tính thủ tục của các RTN Phương pháp biểu diễn nêu trên có mức độ trừu tượng tương đương với một hệ các quy tắc viết lại của văn phạm phi ngữ cảnh, theo nghĩa mọi quy tắc của văn phạm phi ngữ cảnh đều có thể chuyển thành một RTN tương đương. Tuy nhiên, cách biểu diễn bằng RTN có một đặc điểm quan trọng mà trong các hệ quy tắc viết lại không có, đó là các tiến trình (process). Khi ta sử dụng một văn phạm để xây dựng thủ tục đoán nhận một ngôn ngữ, thì các quy tắc viết lại chỉ ra cần làm cái gì; còn ôtômát nằm trong RTN lại mô tả làm như thế nào. Để so sánh, giả sử ta dùng một hệ sản xuất để đoán nhận một ngôn ngữ phi ngữ cảnh và dùng một RTN để đoán nhận cũng ngôn ngữ đó. Khi thiết kế hệ sản xuất, ta tự do quyết định các câu hỏi như áp dụng quy tắc nào tiếp theo, phần dữ liệu nào sẽ xem xét tiếp theo, và thực hiện các thao tác "viết lại" trên dữ liệu đó như thế nào. Với RTN, quyền lựa chọn các quyết định tương tự như trên không thuộc về người thiết kế nữa, bởi vì chúng đã bị ẩn trong biểu diễn ngữ nghĩa của văn phạm. Hình thức biểu diễn bằng RTN thể hiện nhiều đặc tính của các ngôn ngữ lập trình thủ tục thường gặp, đặc biệt khi nó được dịch thành biểu diễn tuyến tính cho đầu vào của máy tính - lệnh nhảy goto có và không có điều kiện (các bước chuyển trạng thái), các nhãn lệnh (các tên trạng thái), và các lời gọi thủ tục (PUSH và POP). Các điều khiển thủ tục có một đặc điểm quan trọng không bị ẩn trong ký hiệu, đó là cách trình thông dịch thực hiện khi nó gặp một trạng thái có nhiều cung chuyển tiếp theo. Chế độ bình thường là lần lượt đi theo các cung chuyển, bắt đầu từ cung chuyển đầu tiên, thực hiện từ trên xuống và ưu tiên chiều sâu, đi theo các đường dẫn xa nhất có thể và chấp nhận đường đi đầu tiên đến được một trạng thái kết với một xâu vào rỗng và ngăn xếp rỗng. Ở đây có sự khác nhau cơ bản so với cách tiếp cận hệ sản xuất, với hệ sản xuất, dạng viết lại của các quy tắc tự nó không giả định trước bất kỳ một tiến trình nào. Người xây dựng mạng chuyển RTN cần suy nghĩ theo tiến trình nhận dạng từ trên xuống, từ trái sang phải. Như vậy, hình thức RTN cho phép ta dễ dàng theo dõi tiến trình phân tích. Các RTN mô tả tiến trình, còn CFG thì không. Do mỗi chương trình máy tính là một sự mô tả tiến trình nên các RTN rất có giá trị khi được dùng để viết chương trình phân tích. Trên thực tế cũng có nhiều trình phân tích được điều khiển bởi các quy tắc của văn phạm. Sự khác nhau lớn nhất của hai hình thức này là vào thời điểm chạy chương trình, trình phân tích RTN "biết được" tại mỗi bước đã có sẵn những lựa chọn nào, Chương 3. Các mạng chuyển Khoá luận tốt nghiệp 34 còn các trình phân tích dựa trên văn phạm phi ngữ cảnh phải tìm trong dãy các quy tắc những quy tắc nào là có thể áp dụng được. 3.4. Phân tích từ trên xuống cho mạng chuyển đệ quy Trạng thái phân tích tại một thời điểm nào đó được biểu diễn như sau: ¾ Vị trí hiện tại. Lưu lại phần nào của câu đã được phân tích rồi ¾ Nút hiện tại. Nút ta đang dừng lại để phân tích ¾ Ðiểm quay lại (trở về). Ta đang nằm trong một mạng (B) bởi lời gọi từ một nút nào đó của mạng (A). Khi đó điểm trở về là nút của mạng A, để khi quay ra ta lại tiếp tục quá trình phân tích. Trước hết, ta xét thuật toán đơn giản tìm kiếm trên một mạng chuyển đệ quy. Giả sử rằng nếu ta có thể đi qua một cung nào đó thì cung đó sẽ là đúng đắn trong phân tích cuối cùng; và giả sử ta chỉ xét các cung cat, push, và pop. Sau đó ta sẽ sửa đổi thuật toán này để tìm tất cả các đường đi bằng kỹ thuật quay lui. Giả sử ta đang đứng ở một nút trung gian nào đó và biết 3 thông tin đã qua. Ta thử đi theo một cung để ra khỏi nút hiện tại. Có các trường hợp sau xảy ra ¾ Nếu cung này là cung cat và từ kế tiếp trong câu thuộc vào lớp từ loại đó, thì - cập nhật lại vị trí hiện tại là từ kế tiếp; - cập nhật lại nút hiện tại là đích của cung này; ¾ Nếu cung này là cung push đẩy tới một mạng N thì - đưa đích của cung này vào danh sách các điểm trở về; - cập nhật lại nút hiện tại là nút bắt đầu của mạng N; ¾ Nếu cung này là cung pop và danh sách các điểm trở về chưa rỗng thì cập nhật nút hiện tại là điểm đầu tiên trong danh sách này; ¾ Nếu cung này là cung pop, danh sách các điểm trở về là rỗng và không còn từ nào cả thì việc phân tích là thành công; Ðể minh hoạ, ta xét văn phạm sau (Hình 13), Chương 3. Các mạng chuyển Khoá luận tốt nghiệp 35 Hình 13. Mạng chuyển đệ quy làm ví dụ trong phân tích từ trên xuống cùng với bộ từ vựng ART the, a NUMBER one PRONOUN one ADJ wild, green NOUN dogs, man, saw, green VERB cried, saw, broke, faded, man Khi đó, câu 1 The 2 wild 3 dogs 4 cried 5 sẽ được phân tích như trên Bảng 3. Bước Nốt hiện tại Vị trí hiện tại Ðiểm trả về Cung được đi 1. S 1 nil S/1 2. NP 1 {S1} NP/1 3. NP1 2 {S1} NP1/1 4. NP1 3 {S1} NP1/2 5. NP2 4 {S1} NP2/1 6. S1 4 nil S1/1 7. S2 5 nil N2/1 Bảng 3. Quá trình phân tích từ trên xuống Chương 3. Các mạng chuyển Khoá luận tốt nghiệp 36 Câu The green faded sẽ không thể phân tích tích được bằng văn phạm này, bởi đầu tiên trình phân tích coi green là một tính từ, cho nên sau đó nó không tìm được một danh từ. Xét câu 1 One 2 saw 3 the 4 man 5, Ban đầu, trình phân tích thử phân tích câu với cụm danh từ one saw, nhưng sau đó thất bại khi tìm một động từ tiếp theo, nó quay lại và tìm ra cách phân tích thành công với cụm danh từ là one. Quá trình phân tích như trên Bảng 4. Bước Trạng thái hiện tại Ði theo cung Các trạng thái được lưu lại 1. (S,1,nil) S/1 nil 2. (NP,1,{S1}) NP/2 (và NP/3 để lưu) nil 3. (NP1,2,{S1}) NP1/2 {NP2,2, {S1}} 4. (NP2,3,{S1}) NP2/1 {NP2,2, {S1}} 5. (S1,3,{nil}) không thể đi theo cung nào cả {NP2, 2, {S1}} 6. (NP2,2,{S1}) NP2/1 nil 7. (S1,2,nil) S1/1 nil 8. (S2,3,nil) S2/2 nil 9. (NP,3,{S2}) NP/1 nil 10. (NP1,4,{S2}) NP1/2 nil 11. (NP2,5,{S2}) NP2/1 nil 12. (S2,5,nil) S2/1 nil 13. phân tích thành công nil Bảng 4. Phân tích từ trên xuống kết hợp quay lui cho mạng chuyển đệ quy Trong bước 2, có hai cung ra khỏi nút NP có thể chấp nhận one. Cung NP/2 coi one là một số (number) và sinh ra nút kế tiếp; đồng thời one cũng là một đại từ (pronoun), nên trình phân tích lưu lại khả năng đi qua cung NP/3 để đến nút NP2, như thế trình phân tích lưu trạng thái (NP2,2,{S1}). Tại bước 6, nó dùng lại trạng thái này, bởi nhận thấy rằng không có cung nào đi ra khỏi S1 chấp nhận từ the. Với những ví dụ phức tạp hơn, sẽ có cả một danh sách các điểm được lưu. Tuỳ theo danh sách này được tổ chức theo thứ tự ra sao, trình phân tích sẽ sinh ra những thứ tự phân tích khác nhau. Chương 4. Xây dựng văn phạm tiếng Việt Khoá luận tốt nghiệp Chương 4. Xây dựng văn phạm tiếng Việt 4.1. Xây dựng tập từ loại tiếng Việt Ngữ pháp tiếng Việt hết sức phức tạp. Việc xây dựng một bộ văn phạm hoàn chỉnh cho tiếng Việt là rất khó khăn. Ngay cả về vấn đề từ loại của tiếng Việt hiện nay vẫn còn chưa hoàn toàn thống nhất. Sau khi tham khảo nhiều tài liệu chuyên ngành cơ sở ngôn ngữ học và tiếng Việt, nhóm nghiên cứu đã quyết định sử dụng trước mắt cách phân loại từ tiếng Việt theo cuốn Ngữ Pháp tiếng Việt (nhà xuất bản KHXH, 1983) và đề nghị bộ nhãn chi tiết như danh sách dưới đây: 1. Danh từ (N) a. Danh từ riêng Np b. Danh từ đơn thể Nc c. Danh từ tổng thể Ng d. Danh từ loại thể Nt e. Danh từ đơn vị Nu f. Danh từ trừu tượng Na g. Danh từ số lượng Nn h. Danh từ vị trí Nl 2. Động từ (V) a. Động từ ngoại động Vt b. Động từ nội động Vit c. Động từ cảm nghĩ Vim d. Động từ phương hướng Vo e. Động từ tồn tại Vs f. Động từ biến hoá Vb g. Động từ ý chí Vv h. Động từ tiếp thụ Va i. Động từ so sánh Vc j. Động từ “là” Vla 3. Tính từ (A) a. Tính từ hàm chất Aa b. Tính từ hàm lượng Am 4. Đại từ (P) a. Đại từ xưng hô Pp b. Đại từ không gian, thời gian Pd c. Đại từ số lượng Pn d. Đại từ hoạt động, tính chất Pa e. Đại từ nghi vấn Pi Chương 4. Xây dựng văn phạm tiếng Việt Khoá luận tốt nghiệp 38 5. Phụ từ (J) a. Phụ từ thời gian Jt b. Phụ từ mức độ Jd c. Phụ từ so sánh Jr d. Phụ từ khẳng định, phủ địnhJa e. Phụ từ mệnh lệnh Ji 6. Kết từ (C) a. Kết từ chính phụ Cm b. Kết từ liên hợp Cc 7. Trợ từ M 8. Cảm từ I 4.2. Xây dựng văn phạm tiếng Việt Mục tiêu của ta là xây dựng được một văn phạm vừa đủ để giải quyết bài toán phân tích. Nếu văn phạm quá rộng thì vừa không cần thiết vừa làm phức tạp thêm vấn đề. Nhưng nếu văn phạm quá hẹp thì không thể bao quát được hết cấu trúc của các câu cần phân tích, do đó không đủ mạnh để giải quyết bài toán. Khi xây dựng câu tiếng Việt, ta triển khai xây dựng theo từng bước từ → ngữ → câu. Ngữ pháp truyền thống chia ra các loại ngữ sau đây: Tên ngữ Nhãn Đặc trưng Danh ngữ (noun phrase) NP Danh từ làm trung tâm Động ngữ (verb phrase) VP Động từ làm trung tâm Tính ngữ (adjectival phrase) AP Tính từ làm trung tâm Giới ngữ (prepositional phrase) PP Giới từ làm trung tâm Nói chung, mỗi ngữ đều có ba bộ phận: phần phụ trước đứng trước thành tố chính, phần trung tâm chứa thành tố chính và phần phụ sau đứng sau thành tố chính. Thành tố chính của ngữ giữ vai trò quan trọng về mặt ngữ pháp đối với ngữ, cần thiết về mặt tổ chức của ngữ, sự có mặt của nó là bắt buộc, không thể lược bỏ. Thành tố chính đại diện cho toàn bộ ngữ trong mối liên hệ với các yếu tố khác nằm ngoài ngữ, chi phối các thành tố khác và quyết định chức vụ ngữ pháp của tất cả các thành tố phụ có liên quan. Xét về vị trí, thành tố phụ của ngữ đứng trước hay sau phần trung tâm. Trong cùng một loại ngữ, những từ có khả năng khi thì làm thành tố phụ sau, khi thì làm thành tố phụ trước không nhiều. Xét về từ loại, thành tố phụ có thể thuộc lớp từ hư Chương 4. Xây dựng văn phạm tiếng Việt Khoá luận tốt nghiệp 39 hoặc thuộc lớp từ thực. Trong tiếng Việt, tồn tại những lớp từ hư chuyên làm thành tố phụ trong từng loại ngữ nhất định. Chúng được dùng để nhận biết từ loại của từ làm thành tố chính. Ví dụ: • hãy | đừng | chớ + động từ • rất | hơi | khí + tính từ • tính từ + lắm | quá • hãy | đừng | chớ | rất | hơi | khí + động từ ý chí - tâm trạng Thành tố phụ trước thường là những từ riêng lẻ, ta ít gặp những cụm từ chính phụ hay chủ vị tại vị trí trước trung tâm. Về mặt từ loại thì đó thường là những phụ từ chuyên dụng, có thể thống kê thành từng nhóm nhỏ có cùng kiểu ý nghĩa khái quát và chuyên đi kèm với những từ loại nhất định. Thành tố phụ sau rất đa dạng và phức tạp về cấu tạo, về từ loại và về nghĩa. Tại vị trí này có thể là từ rời hoặc các loại cụm từ. Khái quát về từ loại, có thể chia các thành tố phụ sau ra thành 2 lớp lớn là lớp các từ có tính chất từ hư và lớp gồm các thực từ. Trong phạm vi khoá luận này, để hạn chế tính phức tạp của các cấu trúc ngữ nói riêng và cấu trúc câu nói chung, em chỉ xem xét thành tố phụ sau về mặt từ loại và dưới dạng từ rời. Thành tố chính rất quan trọng về mặt tổ chức ngữ pháp của ngữ. Nhưng về ý nghĩa thì trong phần lớn các trường hợp, thành tố phụ là yếu tố mang trọng lượng nghĩa lớn nhất. Trong lời nói, nhiều khi chỉ cần dùng một mình thành tố phụ đã đủ đưa ra thông tin. Ví dụ: - Anh đã đọc quyển sách này chưa? - Đã. Bây giờ em xin trình bày sơ lược về các danh ngữ, động ngữ và tính ngữ, tập trung vào mặt cấu tạo của chúng nhằm mục đích xây dựng các quy tắc sinh cho văn phạm tiếng Việt. 4.2.1. Danh ngữ Danh ngữ gồm ba phần: phần trung tâm, phần phụ trước và phần phụ sau. Phần trung tâm là một danh từ hoặc một danh từ chỉ loại cùng với một danh từ chỉ sự vật hay một động từ, tính từ chỉ hoạt động, trạng thái, tính chất, cả hai cùng gộp lại để chỉ một sự vật. Ví dụ: cái nhà, cây tre, con mèo, người thợ, niềm vui, cuộc họp, vẻ đẹp... Chương 4. Xây dựng văn phạm tiếng Việt Khoá luận tốt nghiệp 40 Trong danh ngữ không có phần phụ trước, bất kỳ một loại danh từ nào cũng đều có thể làm thành tố chính mà không kèm thêm điều kiện nào (trừ về ý nghĩa). Trong danh ngữ có phần phụ trước, danh từ làm thành tố chính đòi hỏi những điều kiện khá chặt chẽ. Ví dụ, có những lớp con danh từ chỉ có thể đứng ở phần trung tâm sau một danh từ loại thể. Phần phụ trước có 3 vị trí khác nhau, sắp xếp theo một trật tự nhất định, chuyên dùng để chỉ mặt số lượng của sự vật nêu ở trung tâm. Có hai vị trí có trật tự ổn định, thường dùng để chỉ mặt chất lượng của sự vật nêu ở trung tâm. Ví dụ: tất cả những cái con mèo đen ấy -3 -2 -1 0 1 2 Vị trí chỉ xuất (-1) nằm sát trung tâm, thường gặp là từ cái, từ chỉ xuất bao giờ cũng là một danh từ loại thể. Vị trí từ chỉ số lượng (-2) được chia làm các hạng sau: • số từ xác định (số đếm) một, hai,... • số từ phỏng định: vài, ba... • từ hàm ý phân phối mỗi, từng, mọi... • quán từ những, các, một... • từ mấy Vị trí chỉ tổng lượng (-3), thường gặp những từ tất cả, hết thảy, tất thảy, tất cả, cả... Phần phụ sau của cụm danh từ có hai vị trí. Phần trung tâm Vị trí 1 Vị trí 2 con mèo đen của nhà bạn Nam tôi mới xin hôm qua ấy Vị trí 1 nêu đặc trưng miêu tả, về mặt từ loại ta nhận thấy có nhiều kiểu từ loại khác nhau danh từ phòng tạp chí động từ phòng đọc tính từ phòng hẹp Chương 4. Xây dựng văn phạm tiếng Việt Khoá luận tốt nghiệp 41 số từ phòng mười bốn đại từ phòng chúng tôi Vị trí từ chỉ định 2 là yếu tố đánh dấu đường biên giới sau cùng của danh ngữ. Các từ chỉ định thường gặp là: này, kia, nọ, ấy, đấy, đó. Tóm lại, ta có cấu tạo đầy đủ của danh ngữ như sau: Phụ tố tổng thể Phụ tố số lượng Phụ tố loại thể, đơn vị Chính tố ở trung tâm Phụ tố hạn định Phụ tố chỉ định Det1 (Determiner) Det2 Det3 N AP/VP/NP/PP DP (demonstrative pronoun) Tất cả ba cái bàn gỗ ấy Những cô bán hàng này Tư tưởng tiến bộ đó Toàn thể đồng bào cả nước Trong khuôn khổ khoá luận ta chỉ xét trường hợp đơn giản với các qui tắc sinh danh ngữ như sau 1) NP → N 2) NP → Det1 Det2 Det3 N DP 3) Det1 → Ng (Danh từ tổng thể) 4) Det2 → Nn (Danh từ số lượng) 5) Det3 → Nt | Nu (Danh từ loại thể/danh từ đơn vị) 6) DP → Pd (Đại từ không gian/thời gian) 4.2.2. Động ngữ Về mặt cấu tạo, động ngữ cũng có ba thành phần: phần trung tâm, phần phụ trước và phần phụ sau. Phần trung tâm có thể là một động từ (ví dụ, đang viết thư, đã mắc bệnh), một ngữ khứ hồi (ví dụ, vừa đi Nam Định về hôm qua) hoặc một thành ngữ (ví dụ, cứ chỉ tay năm ngón hoài). Trong phạm vi khoá luận này, em chỉ xét phần trung tâm là một động từ, bởi vì kiểu thành tố chính là một động từ là kiểu có tính chất tiêu biểu, có tác dụng nhiều nhất đối với việc xác định tính chất động từ cho một từ cũng như đối với việc phân định các tiểu loại trong từ loại động từ. Chương 4. Xây dựng văn phạm tiếng Việt Khoá luận tốt nghiệp 42 Khi xem xét kiểu thành tố chính là một động từ, ta cần phân biệt hai loại động từ độc lập và không độc lập. Trong điều kiện sử dụng bình thường, động từ độc lập có thể tự thân làm thành tố chính, còn động từ không độc lập đòi hỏi phải có một từ khác đi sau để bổ sung ý nghĩa. Động từ không độc lập được chia làm các nhóm: • động từ tình thái, ví dụ, cần, nên, phải, có thể, không thể, định, toan, dám, chịu, mong, muốn, chúc, bị, được, mắc, phải... • động từ tiếp diễn, chấm dứt, ví dụ, bắt đầu, tiếp tục, hết, thôi... Các động từ độc lập điển hình là các động từ chỉ hoạt động vật lý, hoặc trạng thái tâm lý như: đọc, thực hiện, lấy, đi, lo, kính nể, vui... Thực tiễn sử dụng ngôn ngữ cho thấy tại phần phụ trước của động ngữ có thể gặp hai lớp từ khác nhau rõ rệt: • Những từ mang nhiều ý nghĩa ngữ pháp, chuyên đi kèm động từ (hoặc tính từ), có thể gọi chung là những phụ từ. • Một số từ rõ nghĩa từ vựng, những thực từ. Số lượng phụ từ làm thành tố phụ trước trong động ngữ chỉ khoảng vài chục từ, chia làm các nhóm con • chỉ sự tiếp diễn, tương tự của hoạt động, trạng thái, như đều, cũng vẫn, cứ, còn... • chỉ quan hệ thời gian của hoạt động, trạng thái như từng, đã, vừa, mới, đang, sẽ... • chỉ tần số (số lần) khái quát của sự xuất hiện hoạt động trạng thái, như thường, hay, năng, ít, hiếm... • chỉ mức độ của trạng thái như rất, hơi, khí, quá... • nêu lên ý khẳng định hay phủ định như có, không, chưa, chẳng... • nêu ý sai khiến, khuyên nhủ như hãy, đừng, chớ... Tại phần phụ trước cụm động từ, ta gặp hai kiểu thực từ thành tố phụ sau đây: 1. Những từ tượng thanh tượng hình và một số tính từ có tác dụng miêu tả hành động, trạng thái nêu ở động từ - thành tố chính. Ví dụ, ào ào chảy, lác đác rơi, khẽ kêu, căn bản hoàn thành, tích cực làm việc... Chương 4. Xây dựng văn phạm tiếng Việt Khoá luận tốt nghiệp 43 2. Kiến trúc gồm một kết từ với một danh từ chỉ điểm xuất phát. Kiến trúc này thường đứng trước các động từ chỉ hướng (ra, vào, lên, xuống), các kết từ thường gặp là từ, ở, dưới, trên, trong, ngoài... Ví dụ, từ quê ra, ở Bắc vô, dưới Hải Phòng lên... Cũng giống như trong tổ chức của danh ngữ, phần phụ sau của động ngữ phức tạp hơn về nhiều phương diện so với phần phụ trước. Chỉ xét riêng về phương diện từ loại, thành tố phụ sau của động ngữ có thể là những yếu tố thuộc mọi từ loại có thể có, chẳng hạn danh từ đọc sách động từ ăn đứng tính từ đi nhanh số từ chia ba đại từ hỏi ai chỉ định từ lại đây phụ từ hiểu rồi Ở động ngữ, phụ từ làm thành tố phụ sau có thể được chia thành những nhóm nhỏ với những ý nghĩa ngữ pháp riêng, như sau: • Nhóm từ chỉ ý kết thúc, gồm rồi, đã... • Nhóm từ chỉ ý cầu khiến (mời mọc, mệnh lệnh, rủ rê) gồm đi, nào, thôi... • Nhóm từ chỉ kết quả gồm 3 từ được, mất, phải... • Chỉ sự tự lực thì dùng từ lấy. Ví dụ, làm lấy • Nhóm từ chỉ sự cùng chung, gồm có với, cùng. Ví dụ, cho nó chơi với. • Từ nhau chỉ sự qua lại, tương hỗ. Ví dụ. Yêu nhau xin nhớ lời nhau. • Nhóm từ chỉ hướng như ra, vào, tới, lui, qua, lại... • Nhóm từ chỉ mức độ, như lắm, quá. • Nhóm từ chỉ cách thức diễn ra trong thời gian của hoạt động, trạng thái, gồm ngay, liền, tức khắc, tức thì, dần, dần dần, từ từ, nữa, hoài, luôn, mãi... Cũng như với các phụ từ, khả năng xuất hiện thực từ tại phần phụ sau động ngữ lệ thuộc nội dung ý nghĩa của từ làm thành tố chính. Tóm lại, ta có cấu tạo đầy đủ của động ngữ như sau: Chương 4. Xây dựng văn phạm tiếng Việt Khoá luận tốt nghiệp 44 Phụ tố trước Chính tố ở trung tâm Phụ tố sau phụ từ/thực từ V phụ từ/thực từ đã ăn xong cơm còn yêu nhiều hãy hỏi tôi Trong khuôn khổ khoá luận ta chỉ xét trường hợp đơn giản với các qui tắc sinh động ngữ như sau 1) VP → Det1 V Det2 2) Det1 → J | A | C 3) Det2 → J | A | C 4.2.3. Tính ngữ Cấu tạo chung của tính ngữ cũng gồm 3 phần: phần trung tâm, phần phụ trước, phần phụ sau. Các thành tố phụ của tính ngữ gồm có hai loại: thành tố phụ là phụ từ và thành tố phụ là thực từ. Phần lớn những thành tố phụ là phụ từ xuất hiện ở động ngữ đồng thời cũng có thể làm thành tố phụ trong tính ngữ. Cụ thể như: đã, sẽ, đang, vừa, đều, mới, vẫn, cứ, cũng... với tư cách thành tố phụ trước; rồi với tư cách là thành tố phụ sau. Một vài thành tố phụ có tác dụng đánh dấu từ loại động từ không thể xuất hiện hoặc chỉ xuất hiện với những điều kiện nhất định ở tính ngữ, như hãy, đừng (thành tố phụ trước), đã (thành tố phụ sau). Xét tính từ ở vị trí trung tâm ngữ trong mối quan hệ với hai loại thành tố phụ là hư từ và thực từ, có thể phân biệt hai trường hợp sau đây, trong mỗi trường hợp đó, có sự phân biệt giữa hai lớp con tính từ đối với nhau: 1. Xét ở khả năng kết hợp với những phụ từ chỉ mức độ như rất, lắm, quá, cực kỳ... Ở đây phân biệt được hai lớp con tính từ là tính từ có thang độ (ví dụ, tốt, đẹp, xấu, đúng, sai, to, nhỏ, vừa, xanh, sạch...) và tính từ không có thang độ hay tính từ tuyệt đối (ví dụ, riêng tư, công, chính, đỏ au, thơm ngát, chín nẫu). 2. Xét khả năng kết hợp với thực từ về phía sau. Có thể phân biệt hai lớp con tính từ: Chương 4. Xây dựng văn phạm tiếng Việt Khoá luận tốt nghiệp 45 a. Những tính từ có thực từ làm rõ nghĩa, tức là có bổ ngữ. Ví dụ đông, đầy, vắng, thưa, mau, nhiều... (Ngoài đường đông người). b. Những tính từ không cần có thực từ làm rõ nghĩa. Phần phụ trước của tính ngữ thường là các phụ từ chuyên dụng, như rất, hơi, khí, cực kỳ, tuyệt.... Ngoài những từ chuyên dụng này, tại phần phụ trước của tính ngữ, có thể xuất hiện hầu hết các phụ từ đi với động từ (trừ hãy, đừng, chớ). Cũng như phần phụ sau của động ngữ, trong phần phụ sau của tính ngữ có thể phân biệt những từ có tính chất từ hư -- phụ từ và các thực từ. Phụ từ chuyên dụng làm thành tố phụ sau của tính ngữ là từ lắm. Những từ cực, cực kỳ, tuyệt, quá như đã nói ở trên, thường đứng sau tính từ, nhưng cũng dễ dàng chuyển lên trước tính từ với sắc thái nhấn mạnh. Ví dụ, đẹp lắm, đẹp cực kỳ... Đặt trong mối quan hệ với tính từ làm thành tố chính, các thực từ làm thành tố phụ sau cũng được chia làm các nhóm nhỏ để tiện miêu tả về ý nghĩa, những thường là danh từ. Ở trong phạm vi khoá luận, em chưa sử dụng những sự phân biệt này. Tóm lại, cấu tạo đầy đủ của tính ngữ là: Phụ tố trước Chính tố ở trung tâm Phụ tố sau phụ từ A phụ từ/thực từ rất tốt nết khoẻ cực kỳ Trong khuôn khổ khoá luận ta chỉ xét trường hợp đơn giản với các qui tắc sinh tính ngữ như sau 1) AP → Det1 A Det2 2) Det1 → J 3) Det2 → J | N 4.2.4. Câu đơn hai thành phần Câu đơn hai thành phần là câu đơn có một cụm chủ - vị duy nhất làm thành nòng cốt câu. Câu đơn hai thành phần chiếm vị trí trung tâm và chủ yếu của việc miêu tả ngữ pháp về câu. Vì câu đơn hai thành phần có sự tương ứng với tổ chức của một phán đoán logic tối giản và, mặt khác, ở nó hội tụ các đặc trưng cơ bản của phần cú pháp học về câu (xét ở mặt ngữ pháp), nó được sử dụng rộng rãi nhất và được dùng làm cơ Chương 4. Xây dựng văn phạm tiếng Việt Khoá luận tốt nghiệp 46 sở cho những kiểu câu có cấu tạo lớn hơn (câu đơn mở rộng nòng cốt câu, câu phức thành phần và nhất là câu ghép). Câu đơn được phân loại dựa trên các khuôn hình, đi từ khái quát đến cụ thể. Khuôn hình cơ sở của câu đơn hai thành phần là khuôn hình chủ - vị. I. [Câu] = [Chủ ngữ] + [Vị ngữ] Chủ ngữ có thể là danh ngữ, là tên riêng hoặc đại từ. Khuôn hình hiện thực cấp 1 thực hiện hoá khuôn hình cơ sở đến bậc từ loại. Giả sử chủ ngữ là danh ngữ, chúng ta xây dựng lược đồ như sau: 1. [Câu] = [Danh ngữ] + [Tính ngữ] | [Động ngữ] 2. [Câu] = [Danh ngữ] + [Từ không độc lập chỉ quan hệ + Danh ngữ | Động ngữ] Các ví dụ tương ứng là: Anh này + giỏi | đọc sách Anh này + là + sinh viên Cái này + để + treo Khuôn hình hiện thực cấp 2 cụ thể hoá các khuôn hình cấp 1 ở một số yếu tố của chúng. Trong khuôn hình này, cấu trúc 2. được thác triển tiếp như sau: là Anh này là sinh viên bằng Cái ấm này bằng nhôm Danh ngữ tại | do | bởi ... Danh ngữ Việc này tại anh ấy của Cái áo này của tôi ngoài | trên ... Anh ấy ngoài vườn như Cô ấy như người ốm Danh ngữ để Động ngữ Cái bàn này để ăn cơm Khuôn hình hiện thực cấp 3 là những biến thể song song và có thể chi tiết hơn của các khuôn hình cấp 2. Nhưng trong phạm vi khoá luận này, em xin dừng lại ở khuôn hình hiện thực cấp 2. Chương 4. Xây dựng văn phạm tiếng Việt Khoá luận tốt nghiệp 47 4.2.5. Văn phạm tiếng Việt Tổng kết lại, ta xét văn phạm sinh một lớp các câu đơn giản hai thành phần của tiếng Việt như sau: 1. [Câu] → [Chủ ngữ] + [Vị ngữ] 2. [Chủ ngữ] → [Tên riêng] 3. [Chủ ngữ] → [Đại từ] 4. [Chủ ngữ] → [Đại từ] + [Phụ tố chỉ định] 5. [Chủ ngữ] → [Danh ngữ] 6. [Vị ngữ] → [Tính ngữ] 7. [Vị ngữ] → [Động ngữ] 8. [Vị ngữ] → [Từ quan hệ] + [Danh ngữ] 9. [Vị ngữ] → [Từ quan hệ] + [Động ngữ] 10. [Danh ngữ] → [Danh từ] 11. [Danh ngữ] → [Phụ tố số lượng] + [Danh từ] 12. [Danh ngữ] → [Phụ tố số lượng] + [Phụ tổ loại thể, đơn vị] + [Danh từ] 13. [Danh ngữ] → [Danh từ] + [Phụ tố chỉ định] 14. [Danh ngữ] → [Phụ tổ loại thể, đơn vị] + [Danh từ] 15. [Danh ngữ] → [Phụ tổ loại thể, đơn vị] + [Danh từ] + [Phụ tố chỉ định] 16. [Danh ngữ] → [Phụ tố số lượng] + [Phụ tổ loại thể, đơn vị] + [Danh từ] + [Phụ tố chỉ định] 17. [Động ngữ] → [Động từ] 18. [Động ngữ] → [Động từ] + [Danh từ] 19. [Động ngữ] → [Động từ] + [Phụ từ] 20. [Động ngữ] → [Động từ] + [Tính từ] 21. [Động ngữ] → [Phụ từ] + [Động từ] 22. [Động ngữ] → [Phụ từ] + [Động từ] + [Phụ từ] 23. [Động ngữ] → [Phụ từ] + [Động từ] + [Danh từ] 24. [Động ngữ] → [Phụ từ] + [Động từ] + [Tính từ] 25. [Tính ngữ] → [Tính từ] 26. [Tính ngữ] → [Tính từ] + [Phụ từ] Chương 4. Xây dựng văn phạm tiếng Việt Khoá luận tốt nghiệp 48 27. [Tính ngữ] → [Tính từ] + [Danh từ] 28. [Tính ngữ] → [Phụ từ] + [Tính từ] 29. [Tính ngữ] → [Phụ từ] + [Tính từ] + [Danh từ] Bảng 5. Tập luật của văn phạm tiếng Việt Bây giờ em xin trình bày cấu trúc dữ liệu được sử dụng trong chương trình phân tích cú pháp từ trên xuống cho văn phạm phi ngữ cảnh, chỉ nêu lên phần cài đặt cấu trúc dữ liệu và thuật toán phân tích mà không liệt kê chi tiết toàn bộ mã nguồn của chương trình. Cấu trúc dữ liệu và thuật toán được trình bày trong ngôn ngữ lập trình Java. Với tiếng Việt, trước khi phân tích cú pháp, ta cần tách các đơn vị từ vựng trong câu, sau đó áp dụng tương tự mô hình tiếng Anh. Vì vậy, trong phần này em chỉ trình bày cấu trúc dữ liệu và cài đặt thuật toán cho bài toán phân tích cú pháp tiếng Anh. Trong phần phụ lục của khoá luận em sẽ trình bày chi tiết bài toán tách từ vựng tiếng Việt. Chương 5. Cài đặt chương trình Khoá luận tốt nghiệp Chương 5. Cài đặt chương trình 5.1. Cấu trúc dữ liệu Từ điển là một danh sách tuyến tính các mục từ trong từ điển. Mỗi mục từ là một đối tượng của lớp Lexicon. Lớp Lexicon gồm hai thành phần dữ liệu: biến kiểu xâu ký tự word chứa nội dung của mục từ và một vector partOfSpeech biểu diễn các từ loại tương ứng với từ đó. Các phương thức thao tác trên hai thành phần dữ liệu này là: ¾ boolean isPos(String c) kiểm tra xem từ này có kiểu từ loại là c hay không ¾ String getWord() lấy ra nội dung của từ ¾ Vector getPos() lấy ra vector các từ loại của từ Lớp Lexicon có dạng như sau: class Lexicon { String word; Vector partOfSpeech; Lexicon(String w, Vector pos) {} boolean isPOS(String c) {} public String getWord() {} public Vector getPOS() {} public String toString() {} } Để tăng tốc độ tính toán trong quá trình phân tích, ta biểu diễn mỗi kiểu từ loại bởi một ký tự. Để thực hiện điều này, ta dùng một bảng băm (hashtable) chứa các cặp khoá-trị thể hiện các cặp kiểu từ loại -- mã ký tự tương ứng. Trong chương trình phân tích cú pháp tiếng Anh, ta dùng bảng băm sau: Hashtable ht = new Hashtable(); String keys[] = {"S", "N", "V", "a","n", "v", "i", "j", "P", "p", "x", "o", "u" }; String values[] = {"S", "NP", "VP", "ART", "NOUN", "VERB", "NAME", "ADJ", "PP", "PREP", "AUX", "PRONOUN", "NUMBER" }; for (int i = 0; i < keys.length; i++) ht.put(keys[i], values[i]); Bảng băm này cũng tiện dụng khi biểu diễn các nút của cây chứa kết quả phân tích. Để biểu diễn các nút của cây phân tích, ta sử dụng lớp ParsingTreeNode. Lớp này gồm hai thành phần dữ liệu value chứa tên từ loại và key chứa mã của từ loại này. Lớp ParsingTreeNode có dạng như sau: class ParsingTreeNode { private String value; Chương 5. Cài đặt chương trình Khoá luận tốt nghiệp 50 private String key; public ParsingTreeNode() {} public ParsingTreeNode(String k, String v) {} public String getKey() {} public String toString() {} } Với bảng băm nêu trên, ta có văn phạm đơn giản của tiếng Anh gồm 11 quy tắc như sau: STT Dạng đầy đủ Dạng biểu diễn 1. S → NP VP S → NV 2. NP → ART NOUN N → an 3. NP → ART ADJ NOUN N → ajn 4. NP → NAME N → i 5. NP → PRONOUN N → o 6. PP → PREP NP P → pN 7. VP → VERB V → v 8. VP → AUX V NP V → xvN 9. VP → VERB NP V → vN 10. VP → VERB NP PP V → vNP 11. VP → VERB PP V → vP Bảng 6. Tập luật của văn phạm tiếng Anh Để lưu các vế trái và vế phải của các quy tắc sinh trong văn phạm, ta sử dụng hai mảng một chiều left, right: int MAX_RULES = 50; // số quy tắc cực đại String left[] = new String[MAX_RULES]; String right[] = new String[MAX_RULES]; Các từ của câu cần phân tích được chứa trong mảng tokens. Với tiếng Anh, ta chỉ cần dựa vào các ký tự trắng trong câu để cắt ra các từ. String tokens[]; Để chứa các trạng thái phân tích được sao lưu và vị trí hiện tại đang xét trong câu cần phân tích, ta dùng các ngăn xếp Stack backupStates = new Stack(); Stack positions = new Stack(); Chương 5. Cài đặt chương trình Khoá luận tốt nghiệp 51 5.2. Cài đặt thuật toán Để dựng được cây phân tích, bao giờ ta cũng cần tìm dẫn xuất trái của quá trình phân tích. Dẫn xuất trái là một dẫn xuất tại mỗi bước luôn luôn chọn chữ phụ đầu tiên của xâu trung gian để thực hiện phép thế. Như vậy, một xâu ω bất kỳ thuộc vào ngôn ngữ sinh bởi văn phạm G khi và chỉ khi có tồn tại dẫn xuất trái để từ ký hiệu khởi đầu S suy dẫn được ra ω. Ta gọi dãy các số hiệu của các quy tắc suy dẫn i1i2...in là dãy trái. Ta quy bài toán phân tích câu về bài toán tìm dãy trái của ω. Với những cấu trúc dữ liệu và thuật toán đã trình bày, ta có phương thức tìm dãy trái của một xâu như sau: ¾ Input: Một câu tiếng Anh ω, các từ cách nhau ít nhất một ký tự trắng, không có các dấu chấm câu ¾ Output: Dãy trái của ω nếu phân tích được, hoặc trả lời không đoán nhận được public Vector parse(String w) { int i,j; boolean recognizable = false; // đã đoán nhận được? Vector parsingOrder = new Vector();// dãy trái của phân tích // Lấy ra các từ trong câu StringTokenizer stk = new StringTokenizer(w); int n = stk.countTokens(); tokens = new String[n]; i = 0; while (stk.hasMoreTokens()) { tokens[i] = stk.nextToken(); i++; } String curState = ""; // trạng thái hiện tại int curPos = 0; // vị trí hiện tại Stack backupStates = new Stack(); // các trạng thái sao lưu Stack positions = new Stack(); // các vị trí sao lưu Stack ruleIdxs = new Stack(); // chỉ số các quy tắc được chọn backupStates.push(startSymbol); // startSymbol = S - câu ruleIdxs.push(new Vector()); positions.push(new Integer(0)); // vòng lặp phân tích while ((!backupStates.isEmpty()) && (!recognizable)) { curState = (String)backupStates.pop(); parsingOrder = (Vector)ruleIdxs.pop(); curPos = ((Integer)positions.pop()).intValue(); j = 0; while ((curState.length() > 0) && (Character.isLowerCase(curState.charAt(j)))) { // lo•i b• nh•ng ph••ng án không th• ••a t•i k•t qu•… while ((curState.length() > n-curPos) && (!backupStates.isEmpty())) { curState = (String)backupStates.pop(); curPos = ((Integer)positions.pop()).intValue(); parsingOrder = (Vector)ruleIdxs.pop(); } // nếu từ hiện tại thuộc kiểu từ loại này… if (lexiconDic.match(""+curState.charAt(j),tokens[curPos])){ curPos++; Chương 5. Cài đặt chương trình Khoá luận tốt nghiệp 52 curState = (curState.length() == 1)? "" : curState.substring(1); j = 0; if ((curPos >= tokens.length) && curState.compareTo("") == 0)){ recognizable = true; break; } } else { // n•u không thì xét v• trí và tr•ng thái sao l•u… if (!positions.isEmpty()) curPos = ((Integer)positions.pop()).intValue(); if (!backupStates.isEmpty()) { curState = (String)backupStates.pop(); parsingOrder = (Vector)ruleIdxs.pop(); } else break; } } // Áp d•ng các suy d•n: ••a các ph••ng án ti•p theo vào các ng•n x•p, // ch• ••a vào các ph••ng án có kh• n•ng cho k•t qu• if ((!recognizable) && (curState.compareTo("") != 0)) for (i = 0; i < numberOfRules; i++) if ((left[i].compareTo("" + curState.charAt(0)) == 0) && (curState.length() <= tokens.length-curPos+1)) { backupStates.push(right[i]+ ((curState.length() >= 1) ? curState.substring(1) : "")); positions.push(new Integer(curPos)); Vector tempVec = new Vector(); for (Enumeration e = parsingOrder.elements(); e.hasMoreElements();) tempVec.addElement((Integer)e.nextElement()); tempVec.addElement(new Integer(i+1)); ruleIdxs.push(tempVec); } } // kết thúc vòng lặp phân tích if (!recognizable) return new Vector(); else return parsingOrder; } Phương thức parse nêu trên tìm dãy trái của ω và đưa nó vào một vector các số nguyên, mỗi phần tử của vector này là số hiệu của các quy tắc suy dẫn tương ứng. 5.3. Thể hiện kết quả phân tích Để thể hiện kết quả phân tích ở dạng cây, ta dùng cấu trúc JTree của Java. Cây phân tích được xây dựng từ dãy trái, trong quá trình chèn các nút mới, ta sử dụng thuật toán tìm kiếm theo chiều sâu để tìm nút cha của nút mới cần chèn vào. Phương thức xây dựng cây phân tích như sau: public JTree createParsingTree(Vector parsingOrder) { JTree tree; rootNode = new DefaultMutableTreeNode(new ParsingTreeNode("S", "S")); int q; Enumeration e; String s; for (int i = 0; i < parsingOrder.size(); i++) { q = ((Integer)parsingOrder.elementAt(i)).intValue()-1; e = rootNode.depthFirstEnumeration(); DefaultMutableTreeNode treeNode; while (e.hasMoreElements()) { treeNode = (DefaultMutableTreeNode)e.nextElement(); s = ((ParsingTreeNode)treeNode.getUserObject()).getKey(); if ((s.compareTo(left[q]) == 0) && (treeNode.isLeaf())) { DefaultMutableTreeNode tempNode = null; Chương 5. Cài đặt chương trình Khoá luận tốt nghiệp 53 for (int j = 0; j < right[q].length(); j++) { String key = "" + right[q].charAt(j); tempNode = new DefaultMutableTreeNode(new ParsingTreeNode(key, (String)partOfSpeechMap.get(key))); treeNode.add(tempNode); } break; } } } e = rootNode.depthFirstEnumeration(); DefaultMutableTreeNode treeNode; int j = 0; while (e.hasMoreElements()) { treeNode = (DefaultMutableTreeNode)e.nextElement(); if (treeNode.isLeaf()) { DefaultMutableTreeNode tempNode = null; tempNode = new DefaultMutableTreeNode(tokens[j]); treeNode.add(tempNode); j++; } } tree = new JTree(rootNode); tree.setEditable(true); tree.getSelectionModel().setSelectionMode( TreeSelectionModel.SINGLE_TREE_SELECTION); tree.setShowsRootHandles(true); return tree; } Hình 14 là giao diện của chương trình và thể hiện cây phân tích của câu "The green water evaporated" nhập từ một hộp soạn thảo. Hình 14. Giao diện chương trình phân tích cú pháp tiếng Anh Nếu trình phân tích không phân tích được câu nhập vào (câu sai cú pháp hoặc câu chứa từ không có trong từ điển) thì chương trình đưa ra thông báo là không phân tích Chương 5. Cài đặt chương trình Khoá luận tốt nghiệp 54 được. Dưới đây là kết quả phân tích của chương trình với một số câu nhập vào khác nhau: Chương 5. Cài đặt chương trình Khoá luận tốt nghiệp 55 Chương 5. Cài đặt chương trình Khoá luận tốt nghiệp 56 Để thử nghiệm chương trình phân tích cú pháp tiếng Việt, ta có thể nhập vào một số câu có cấu trúc khác nhau. Nếu dùng ký hiệu [w*] để chỉ từ w có thể xuất hiện hoặc không xuất hiện trong câu thì những câu có dạng: 1. Cô [ấy*] [rất*] tốt [nết*] 2. Cô [ấy*] tốt [cực kỳ*] đều được phân tích đúng. Để thử nghiệm danh ngữ làm chủ ngữ, ta có thể thay đại từ “cô” bằng các tổ hợp: mèo, mèo ấy, con mèo, con mèo ấy, những con mèo ấy và chọn tính ngữ làm vị ngữ cho phù hợp. Có thể nhập vào một số câu như sau để thử nghiệm động ngữ làm vị ngữ: Anh [này*] [đang*] ăn [cơm* | ngon*] Tương tự, có thể thay đại từ “anh” bằng một danh ngữ. Để thử nghiệm từ quan hệ, ta có thể dùng một số câu như: 1. Tôi là sinh viên 2. Nó bằng nhôm 3. Anh ấy là sinh viên 4. Họ là các sinh viên 5. Chúng là hai con mèo Chương 5. Cài đặt chương trình Khoá luận tốt nghiệp 57 5.4. Đánh giá kết quả Khoá luận trình bày việc vận dụng các mô hình văn phạm phi ngữ cảnh và các mạng chuyển vào bài toán phân tích cú pháp tiếng Anh và tiếng Việt. Trong phân tích cú pháp có những đặc điểm chính sau: • Tách riêng việc giải quyết phân tách từ vựng và phân tích cú pháp cho tiếng Việt. Sử dụng kết quả phân tích cú pháp để hỗ trợ quyết định chọn phương án phân tách từ vựng của câu (Phần Phụ lục). • Giải quyết được vấn đề độ dài từ ghép hoặc cụm từ cố định. • Chương trình hiện tại chỉ xử lý những câu đơn hai thành phần đơn giản của tiếng Việt • Với câu nhập nhằng thì đưa ra mọi phương án phân tích có thể. • Chương trình cung cấp các giao diện nhập liệu và xử lý trong môi trường hệ điều hành Windows, thuận tiện cho việc sử dụng. Mọi câu đưa vào đều được thực hiện theo hai bước, gồm tách từ vựng và phân tích cú pháp. Mặc dù em chưa đưa ra được những số liệu thống kê chính xác nhưng quá trình thử nghiệm bước đầu cho thấy chương trình chạy khá nhanh và cho kết quả tương đối chính xác. Khoá luận tốt nghiệp Phụ lục Bài toán tách từ vựng tiếng Việt Trước khi thực hiện phân tích cú pháp của một câu tiếng Việt, ta cần một bước tiền xử lý quan trọng, đó là tách câu thành các đơn vị từ vựng và gán cho chúng những nhãn từ loại tương ứng (chẳng hạn danh từ, động từ...). 1. Đặt bài toán Nhập vào một câu tiếng Việt bất kỳ, hãy tách câu đó thành những đơn vị từ vựng (từ), hoặc chỉ ra những âm tiết nào không có trong từ điển (phát hiện đơn vị từ vựng mới). Để giải quyết bài toán đặt ra, ta cần tập dữ liệu gồm từ điển âm tiết (khoảng 6700 âm tiết) và từ điển từ vựng tiếng Việt (khoảng 30.000 từ). Việc sử dụng hai bộ từ điển nêu trên trong phạm vi đề tài nghiên cứu đã được sự đồng ý của Trung tâm từ điển học. Các từ điển được lưu dưới dạng các tệp văn bản có định dạng mã TCVN hoặc Unicode (UTF-8). 2. Các bước giải quyết 1. Xây dựng ôtôtmát âm tiết đoán nhận tất cả các âm tiết tiếng Việt 2. Xây dựng ôtôtmát từ vựng đoán nhận tất cả các từ vựng tiếng Việt. 3. Dựa trên các ôtômát nêu trên, xây dựng đồ thị tương ứng với câu cần phân tích và sử dụng thuật toán tìm kiếm trên đồ thị để liệt kê các cách phân tích có thể. Tư tưởng của phương pháp xây dựng các ôtômát là: xây dựng dần dần dựa trên ôtômát đã có ở bước trước và âm tiết (hoặc từ vựng) mới đọc được từ tệp dữ liệu ở bước hiện tại. Bảng chữ cái của ôtômát âm tiết là bảng chữ cái tiếng Việt, mỗi cung chuyển được ghi trên đó một ký tự, ban đầu ôtômát âm tiết chỉ gồm một trạng thái khởi đầu được đánh số hiệu 0. Giả sử tại bước nào đó ta đọc được âm tiết a có độ dài n (tính bằng số ký tự) từ tệp dữ liệu. Xuất phát từ trạng thái khởi đầu p = q0 ta lấy ra từng ký tự ci của a và tìm xem từ p có cung chuyển đến trạng thái q nào đó mà trên đó ghi ký tự ci hay không. Nếu có trạng thái q như thế, ta chuyển p thành q và lặp lại bước trên với ký tự ci+1 tiếp theo. Nếu không có q nào như thế, ta ra khỏi vòng lặp và xây dựng mới các trạng thái và cung chuyển tương ứng trên đó ghi các ký tự ci, ci+1,..., cn-1 theo sơ đồ sau (ô vuông chỉ rằng đó là trạng thái kết). Bài toán tách từ vựng tiếng Việt Khoá luận tốt nghiệp 59 Ví dụ, với ba âm tiết phương, pháp, trình ta sẽ có ôtômát âm tiết như Hình 15. Hình 15. Phương pháp xây dựng ôtômát âm tiết Ôtômát từ vựng được xây dựng tương tự, với điểm khác như sau: thay vì ghi trên mỗi cung chuyển một ký tự, ta ghi một số. Số này là số hiệu của trạng thái (kết) của ôtômát âm tiết tại đó đoán nhận mỗi âm tiết của từ. Với cách tổ chức này, ta làm giảm được kích thước của ôtômát từ vựng mà không làm mất thông tin của nó, bởi vì mỗi âm tiết được xác định bằng một trạng thái kết duy nhất trong ôtômát âm tiết. Ví dụ, với hai từ phương pháp và phương trình, giả sử khi đưa lần lượt các âm tiết phương, pháp, trình qua ôtômát âm tiết, ta đến được các trạng thái kết ghi các số n1, n2, n3 thì trên các cung chuyển tương ứng ta ghi các số n1, n2, n3 (Hình 16). Hình 16. Phương pháp xây dựng ôtômát từ vựng Sau khi đã xây dựng xong hai ôtômát, ta ghi chúng vào hai tệp định kiểu để dùng trong bước phân tách từ vựng. Đến lúc này, hai từ điển ban đầu không còn cần thiết nữa, mọi dữ liệu của ta nằm trong hai tệp ghi hai ôtômát này. Nếu mỗi ký tự (char) được ghi vào tệp với kích thước 2 byte (mã Unicode), mỗi số nguyên (int) có kích thước 4 byte thì tệp lưu ôtômát âm tiết có kích thước 146KB, tệp ôtômát từ vựng có kích thước 1MB. Tư tưởng của thuật toán phân tách từ vựng là quy việc phân tách câu về việc tìm đường đi trên một đồ thị có hướng, không có trọng số. Bài toán tách từ vựng tiếng Việt Khoá luận tốt nghiệp 60 Giả sử câu ban đầu là một dãy gồm n+1 âm tiết s0, s1, ..., sn. Ta xây dựng một đồ thị có n+2 đỉnh v0, v1, ..., vn, vn+1, sắp thứ tự trên một đường thẳng từ trái sang phải; trong đó, từ đỉnh vi đến đỉnh vj có cung (i < j) nếu các âm tiết si, si+1, ..., sj-1 theo thứ tự lập thành một từ. Khi đó mỗi cách phân tách câu khác nhau tương ứng với một đường đi trên đồ thị từ đỉnh đầu v0 đến đỉnh cuối vn+1. Trong các cách phân tách câu đó, cách phân tích câu đúng đắn nhất ứng với đường đi qua ít cung nhất trên đồ thị. Trong trường hợp câu có sự nhập nhằng thì đồ thị sẽ có nhiều hơn một đường đi ngắn nhất từ đỉnh đầu đến đỉnh cuối, ta liệt kê toàn bộ các đường đi ngắn nhất trên đồ thị, từ đó đưa ra tất cả các phương án tách câu có thể và để người dùng quyết định sẽ chọn phương án nào, tuỳ thuộc vào ngữ nghĩa hoặc văn cảnh. Ví dụ, xét một câu có cụm "thuộc địa bàn", ta có đồ thị như sau (Hình 17) Hình 17. Một tình huống nhập nhằng Cụm này có sự nhập nhằng giữa thuộc địa và địa bàn và ta sẽ có hai kết quả phân tách là "thuộc địa / bàn" và "thuộc / địa bàn". Ta có thể chỉ ra rất nhiều những cụm nhập nhằng trong tiếng Việt, chẳng hạn "tổ hợp âm tiết", "bằng chứng cớ",... Trường hợp trong câu có âm tiết không nằm trong từ điển thì rõ ràng ôtômát âm tiết không đoán nhận được âm tiết này. Kết quả là đồ thị ta xây dựng từ câu đó là không liên thông. Dựa vào tính chất này, ta thấy rằng nếu đồ thị không liên thông thì dễ dàng phát hiện ra rằng đơn vị âm tiết không đoán nhận được không nằm trong từ điển âm tiết, tức nó bị viết sai chính tả hoặc là một đơn vị âm tiết (từ vựng) mới. 3. Đánh giá kết quả Với cách tiếp cận như trên, bài toán phân tách từ vựng trong câu tiếng Việt về cơ bản đã được giải quyết, đặc biệt là vấn đề tách các tổ hợp từ tương đương với một đơn vị từ vựng, thường là các cụm từ cố định, ngữ cố định hoặc các thành ngữ trong tiếng Việt. Nếu chúng ta chỉ sử dụng một danh sách từ vựng thông thường và thực hiện các thao tác tìm kiếm trên danh sách này thì không thể đảm bảo thời gian tách từ vựng đối với câu có chiều dài lớn. Với những câu nhập vào có sự nhập nhằng từ vựng, tức có nhiều hơn một cách phân tách thì chương trình liệt kê toàn bộ các phương án tách từ có thể và giành quyền Bài toán tách từ vựng tiếng Việt Khoá luận tốt nghiệp 61 lựa chọn kết quả cho người sử dụng. Trong tất cả các phương án phân tách đó bao giờ cũng tồn tại phương án đúng. Dưới đây là một số câu nhập vào và kết quả tách từ tương ứng. 1. Nó | là | một | bản | tuyên ngôn | đặc sắc | của | chủ nghĩa nhân đạo | , một | tiếng | chuông | cảnh tỉnh | trước | hiểm họa | lớn lao | của | hành tinh | trước | sự | điên rồ | của | những | kẻ | cuồng tín 2. Sự | giản dị | trong sáng | toả | khắp | tác phẩm | đã | khiến | nó | trở nên | một | bài | thơ | bất hủ | mà | mãi mãi | người ta | muốn | đem | làm quà | tặng | của | tình yêu 3. Trong khi | các | thành phần | tư bản chủ nghĩa | có | những | bước | phát triển | mạnh | hơn | thời kì | trước | thì | thế lực | của | giai cấp | địa chủ | vẫn | không hề | suy giảm. Tuy nhiên, chương trình phân tách từ vựng hiện tại vẫn còn một số vấn đề khó khăn cần phải tiếp tục nghiên cứu giải quyết: Thứ nhất là vấn đề giải quyết nhập nhằng phân tách. Cần phải chọn một phương án đúng đắn trong số nhiều phương án. Các hướng tiếp cận khả thi cho vấn đề này có thể là: - Dùng phương pháp phân tích cú pháp. Tiến hành phân tích cú pháp của câu với những phương án tách từ vựng có thể, từ đó loại ra những phương án sai cú pháp. Muốn thực hiện được điều này thì ta cần một trình phân tích cú pháp tương đối tin cậy và đầy đủ. - Dùng phương pháp xác suất - thống kê. Ta sẽ thống kê trên những tập văn (corpus) tương đối lớn của tiếng Việt để tìm ra xác suất của các bộ đôi hay bộ ba từ loại hoặc từ vựng đi cạnh nhau. Từ đó lựa chọn phương án phân tách có xác suất sai ít nhất. Chương trình phân tích cú pháp tiếng Việt hiện tại cũng đã có khả năng nhận biết được một số câu nhập nhằng từ vựng. Ví dụ, với câu “bản sao chụp mờ” thì có thể có hai cách phân tích như trong Hình 18. Ở đây có hai cách phân tách từ có thể là “bản | sao chụp” và “bản sao | chụp”, trình phân tích nhận thấy cả hai cách tách từ này đều đúng cú pháp và đưa ra hai cây phân tích tương ứng. Nhưng xét một ví dụ tương tự, câu “anh ấy rất thuộc địa bàn” thì mặc dù cụm “thuộc địa bàn” có hai cách phân tách từ vựng là “thuộc | địa bàn” và “thuộc địa | bàn” nhưng trình phân tích chỉ đoán nhận được một và đưa ra cách phân tích tương ứng với cách tách từ đó. Do đó, cách tách từ còn lại là sai. (Hình 19) Bài toán tách từ vựng tiếng Việt Khoá luận tốt nghiệp 62 Hình 18. Các phương án phân tích cho một câu tiếng Việt nhập nhằng Hình 19. Cây phân tích ứng với cách tách từ đúng Thứ hai là vấn đề giải quyết tên riêng, tên viết tắt và tên có nguồn gốc nước ngoài có mặt trong câu. Hiện tại chương trình phân tách chưa nhận ra được các cụm từ dạng “Nguyễn Văn A”, “Đại học Khoa học Tự nhiên”, hoặc “ĐT. 8.20.20.20”, “1.000$”, “0,05%”... Tài liệu tham khảo [1] Margaret King, Parsing Natural Language, Academic Press Inc, London, 1983. [2] Christopher D. Manning and Hinrich Schütze, Foundations of Statistical Natural Language Processing, Massachusetts Institute of Technology, USA, 1999. [3] Emmanuel Roche and Yves Schabes, Finite-State Language Processing, The MIT Press, Massachusetts, USA, 1997. [4] Đỗ Đức Giáo, Đặng Huy Ruận, Văn phạm và ngôn ngữ hình thức, NXB Khoa học và kỹ thuật, Hà Nội, 1991. [5] Lê Thanh Hương, Phân tích cú pháp tiếng Việt, Luận văn tốt nghiệp cao học, Hà Nội, 1999. [6] Diệp Quang Ban, Hoàng Văn Thung, Ngữ pháp tiếng Việt (2 tập), NXB Giáo dục, Hà Nội, 1999. [7] Mai Ngọc Chừ, Vũ Đức Nghiệu, Hoàng Trọng Phiến, Cơ sở ngôn ngữ học và tiếng Việt, NXB Giáo dục, Hà Nội, 2000. [8] Nguyễn Thiện Giáp, Đoàn Thiện Thuật, Nguyễn Minh Thuyết, Dẫn luận ngôn ngữ học, NXB Giáo dục, Hà Nội, 2001. [9] Ngữ Pháp Tiếng Việt, NXB Khoa học xã hội, 1983. [10] Hoàng Phê, Từ điển tiếng Việt, NXB Khoa học xã hội - Trung tâm từ điển học, Hà Nội, 2000. [11] Bruce Eckel, Thinking in Java, 2nd edition, Revision 11, 2000. [12] Sun Microsystem, The Java Tutorial, CDROM, 2000.