tailieunhanh - Báo cáo khoa học: "AN OPTIMAL TABULAR PARSING ALGORITHM"

In this p a p e r we relate a number of parsing algorithms which have been developed in very different areas of parsing theory, and which include deterministic algorithms, tabular algorithms, and a parallel algorithm. We show that these algorithms are based on the same underlying ideas. By relating existing ideas, we hope to provide an opportunity to improve some algorithms based on features of others. A second purpose of this paper is to answer a question which has come up in the area of tabular parsing, namely how to obtain a parsing algorithm with the property that. | AN OPTIMAL TABULAR PARSING ALGORITHM Mark-J an Nederhof University of Nijmegen Department of Computer Science Toernooiveld 6525 ED Nijmegen The Netherlands markj an Abstract In this paper we relate a number of parsing algorithms which have been developed in very different areas of parsing theory and which include deterministic algorithms tabular algorithms and a parallel algorithm. We show that these algorithms are based on the same underlying ideas. By relating existing ideas we hope to provide an opportunity to improve some algorithms based on features of others. A second purpose of this paper is to answer a question which has come up in the area of tabular parsing namely how to obtain a parsing algorithm with the property that the table will contain as little entries as possible but without the possibility that two entries represent the same subderivation. Introduction Left-corner LC parsing is a parsing strategy which has been used in different guises in various areas of computer science. Deterministic LC parsing with k symbols of lookahead can handle the class of LC fc grammars. Since LC parsing is a very simple parsing technique and at the same time is able to deal with left recursion it is often used as an alternative to top-down TD parsing which cannot handle left recursion and is generally less efficient. Nondeterministic LC parsing is the foundation of a very efficient parsing algorithm 7 related to Tomita s algorithm and Earley s algorithm. It has one disadvantage however which becomes noticeable when the grammar contains many rules whose right-hand sides begin with the same few grammars symbols . A a 31 I a 2 I . where a is not the empty string. After an LC parser has recognized the first symbol X of such an a it will as next step predict all aforementioned rules. This amounts to much nondeterminism which is detrimental both to the time-complexity and the space-complexity. Supported by the Dutch Organisation for Scientific Research NWO .

• Báo cáo khoa học
• AN OPTIMAL TABULAR
• PARSING ALGORITHM
• Mark Jan
• báo cáo khoa học
• mô hình ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Xử lý ngôn ngữ
• Natural Language Processing
• Ngôn ngữ lập trình
• Nhập nhằng cấu trúc
• Tri thức về ngôn ngữ
• Mô hình n gram
• Dịch máy
• Phương pháp dịch máy
• Hiểu ngôn ngữ
• Phân tích ngữ nghĩa
• Phân loại tin tự động
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• Mô hình ngôn ngữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Tách từ tiếng Việt
• Gán nhãn từ loại
• Phân tích cú pháp
• Nghĩa từ vựng
• Phân giải nhập nhằng từ
• Phân loại văn bản
• Lexical chain
• Phản hồi thông tin
• Bài toán PTCP
• Cấu trúc ngữ pháp
• Phân tích cú pháp xác suất
• CKY kết hợp xác suất
• Văn phạm phi ngữ cảnh xác suất
• Hình thái học