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: "LR RECURSIVE TRANSITION NETWORKS FOR EARLEY AND TOMITA PARSING"
Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo khoa học: "LR RECURSIVE TRANSITION NETWORKS FOR EARLEY AND TOMITA PARSING"
Hoa Thiên
89
8
pdf
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Efficient syntactic and semantic parsing for ambiguous context-free languages are generally characterized as complex, specialized, highly formal algorithms. In fact, they are readily constructed from straightforward recursive Iransition networks (RTNs). In this paper, we introduce LR-RTNs, and then computationally motivate a uniform progression from basic LR parsing, to Earley's (chart) parsing, concluding with Tomita's parser. These apparently disparate algorithms are unified into a single implementation, which was used to automatically generate all the figures in this paper. 1. I N T R O D U C T I O N Ambiguous context-free grammars (CFGs) are currently used in. | LR RECURSIVE TRANSITION NETWORKS FOR EARLEY AND TOMITA PARSING Marie Perl in School of Computer Science Carnegie Mellon University Pittsburgh PA 15213 Internet perlin@cs.cmu.edu ABSTRACT Efficient syntactic and semantic parsing for ambiguous context-free languages are generally characterized as complex specialized highly formal algorithms. In fact they are readily constructed from straightforward recursive transition networks RTNs . In this paper we introduce LR-RTNs and then computationally motivate a uniform progression from basic LR parsing to Earley s chart parsing concluding with Tomita s parser. These apparently disparate algorithms are unified into a single implementation which was used to automatically generate all the figures in this paper. 1. INTRODUCTION Ambiguous context-free grammars CFGs are cuưently used in the syntactic and semantic processing of natural language. For efficient parsing two major computational methods are used. The first is Earley s algorithm Earley 1970 which merges parse trees to reduce the computational dependence on input sentence length from exponential to cubic cost. Numerous variations on Earley s dynamic programming method have developed into a family of chart parsing Winograd 1983 algorithms. The second is Tomita s algorithm Tomita 1986 which generalizes Knuth s Knuth 1965 and DeRemer s DeRemer 1971 computer language LR parsing techniques. Tomita s algorithm augments the LR parsing set of items construction with Earley s ideas. What is not currently appreciated is the continuity between these apparently distinct computational methods. Tomita has proposed Tomita 1985 constructing his algorithm from Earley s parser instead of DeRemer s LR parser. In fact as we shall show Earley s algorithm may be viewed as one form of LR parsing. Incremental constructions of Tomita s algorithm Heering Klint and Rekers 1990 may similarly be viewed as just one point along a continuum of methods. This work was supported in part by grant R29 LM .
TÀI LIỆU LIÊN QUAN
Kỷ yếu tóm tắt báo cáo khoa học: Hội nghị khoa học tim mạch toàn quốc lần thứ XI - Hội tim mạch Quốc gia Việt Nam
Báo cáo nghiên cứu khoa học: "Danh lục các loài thú ở khu bảo tồn thiên nhiên Pù Huống tỉnh Nghệ An và ý nghĩa bảo tồn nguồn gen quí hiếm của chúng"
Báo cáo khoa học: Hỗ trợ nâng cao năng lực quản lý chất thải sinh hoạt tại thành phố Hội An
Báo cáo nghiên cứu khoa học: "Tính năng động nghệ thuật của văn học hiện đại Việt Nam và một cách nhìn hành trình thể loại"
Báo cáo nghiên cứu khoa học: " DỊCH CHUYỂN TRUY VẤN OQL VÀO CÁC PHÉP TÍNH BAO HÀM"
Báo cáo khoa học: " Áp dụng thủ tục phân tích trong kiểm toán báo cáo tài chính"
Báo cáo nghiên cứu khoa học: "Người lính trở về sau chiến tranh với mặc cảm “ăn mày dĩ vãng’ trong tiểu thuyết Chu Lai"
Báo cáo nghiên cứu khoa học: "Khảo sát hiện tượng chuyển đổi chức năng - nghĩa của động từ tiếng Việt"
Báo cáo nghiên cứu khoa học: " BẢN CHẤT KHOA HỌC VÀ CÁCH MẠNG LÀ CỘI NGUỒN SỨC SỐNG CỦA CHỦ NGHĨA MÁC - LÊNIN"
Báo cáo khoa học: " CẢI TIẾN CÁC THUẬT TOÁN MƯỢN VÀ KHOÁ KÊNH TẦN SỐ MẠNG DI ĐỘNG TẾ BÀO"
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.