tailieunhanh - Báo cáo khoa học: "An alternative LR algorithm for TAGs"

We present a new LR algorithm for treeadjoining grammars. It is an alternative to an existing algorithm that is shown to be incorrect. Furthermore, the new algorithm is much simpler, being very close to traditional LR parsing for context-free grammars. The construction of derived trees and the computation of features also become straightforward. | An alternative LR algorithm for TAGs Mark-Jan Nederhof DFKI Stuhlsatzenhausweg 3 D-66123 Saarbriicken Germany E-mail nederhof@ Abstract We present a new LR algorithm for treeadjoining grammars. It is an alternative to an existing algorithm that is shown to be incorrect. Furthermore the new algorithm is much simpler being very close to traditional LR parsing for context-free grammars. The construction of derived trees and the computation of features also become straightforward. 1 Introduction The efficiency of LR Ã parsing techniques Sippu and Soisalon-Soininen 1990 appears to be very attractive from the perspective of natural language processing. This has stimulated the computational linguistics community to develop extensions of these techniques to general context-free grammar parsing. The best-known example is generalized LR parsing Tomita 1986 . A first attempt to adapt LR parsing to treeadjoining grammars TAGs was made by Schabes and Vijay-Shanker 1990 . The description was very complicated however and not surprisingly no implementation of the algorithm seems to have been made up to now. Apart from presentational difficulties the algorithm as it was published is also incorrect. Brief indications of the nature of the incorrectness have been given before by Kinyon 1997 . There seems to be no straightforward way to correct the algorithm. We therefore developed an alternative to the algorithm from Schabes and Vijay-Shanker 1990 . This alternative is novel in presentational aspects and is fundamentally different in that it incorporates reductions of subtrees. The new algorithm has the benefit that many theoretically and practically useful properties carry over from the context-free case. For example by making a straightforward translation from TAGs to linear indexed grammars one may identify computations of the parser with rightmost derivations in reverse. Also the extensions needed for construction of parse trees or derived trees as they are often called for

• Báo cáo khoa học
• An alternative LR
• algorithm for TAGs
• Mark Jan Nederhof
• báo cáo khoa học
• mô hình ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• An alternative method
• training probabilistic LR parsers
• 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