Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Luận Văn - Báo Cáo
Báo cáo khoa học
Báo cáo khoa học: "Polynomial Time and Space Shift-Reduce Parsing of Arbitrary Context-free Grammars.*"
Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo khoa học: "Polynomial Time and Space Shift-Reduce Parsing of Arbitrary Context-free Grammars.*"
Linh Trang
88
8
pdf
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
We introduce an algorithm for designing a predictive left to right shift-reduce non-deterministic push-down machine corresponding to an arbitrary unrestricted context-free grammar and an algorithm for efficiently driving this machine in pseudo-parallel. The performance of the resulting parser is formally proven to be superior to Earley's parser (1970). The technique employed consists in constructing before run-time a parsing table that encodes a nondeterministic machine in the which the predictive behavior has been compiled out. . | Polynomial Time and space Shift-Reduce Parsing of Arbitrary Context-free Grammars. Yves Schabes Dept of Computer Information Science University of Pennsylvania Philadelphia PA 19104-6389 USA e-mail schabes@linc.cis.upenn.edu Abstract We introduce an algorithm for designing a predictive left to right shift-reduce non-deterministic push-down machine corresponding to an arbitrary unrestricted context-free grammar and an algorithm for efficiently driving this machine in pseudo-parallel. The performance of the resulting parser is formally proven to be superior to Earley s parser 1970 . The technique employed consists in constructing before run-time a parsing table that encodes a non-deterministic machine in the which the predictive behavior has been compiled out. At run time the machine is driven in pseudo-parallel with the help of a chart. The recognizer behaves in the worst case in ớ G 2n3 -time and ỡ ƠỊn2 -space. However in practice it is always superior to Earley s parser since the prediction steps have been compiled before runtime. Finally we explain how other more efficient variants of the basic parser can be obtained by deter-minizing portions of the basic non-deterministic pushdown machine while still using the same pseudoparallel driver. 1 Introduction Predictive bottom-up parsers Earley 1968 Earley 1970 Graham et al. 1980 are often used for natural language processing because of thefr superior average performance compared to purely bottom-up parsers We are extremely indebted to Fernando Pereừa and Stuart Shieber for providing valuable technical comments during dis cussions about earlier versions of tins algorithm. We are also grateful to Aravind Joshi for his support of this research. We also thank Robert Frank. AU remaining errors are the author s responsibility alone. This research was partially funded by ARO grant DAAL03-89-C0031PRI and DARPA grant N00014-9O-J-1863. such as CKY-style parsers Kasami 1965 Younger 1967 . Their practical superiority is mainly .
TÀI LIỆU LIÊN QUAN
Báo cáo khoa học: "A Polynomial-Time Parsing Algorithm for TT-MCTAG"
Báo cáo khoa học: "Fast, Space-Efficient, non-Heuristic, Polynomial Kernel Computation for NLP Applications"
Báo cáo khoa học: "An Approximate Approach for Training Polynomial Kernel SVMs in Linear Time"
Báo cáo khoa học: "A Polynomial-Time Fragment of Dominance Constraints"
Báo cáo khoa học: "A Polynomial-Time Algorithm for Statistical Machine Translation"
Báo cáo khoa học: "Polynomial Time and Space Shift-Reduce Parsing of Arbitrary Context-free Grammars.*"
Báo cáo khoa học: "PARALLEL MULTIPLE CONTEXT-FREE GRAMMARS, FINITE-STATE TRANSLATION SYSTEMS, AND POLYNOMIAL-TIME RECOGNIZABLE SUBCLASSES OF LEXICAL-FUNCTIONAL GRAMMARS"
Báo cáo khoa học: "Polynomial Learnability and Locality of Formal Grammars"
Báo cáo toán học: "Interpolation Conditions and Polynomial Projectors Preserving Homogeneous Partial Differential Equations "
Báo cáo toán học: "The Abel-type polynomial identities"
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.