کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436119 1441781 2006 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Evaluating GLR parsing algorithms
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Evaluating GLR parsing algorithms
چکیده انگلیسی

We describe the behaviour of three variants of GLR parsing: (i) Farshi’s original correction to Tomita’s non-general algorithm; (ii) the Right Nulled GLR algorithm which provides a more efficient generalisation of Tomita and (iii) the Binary Right Nulled GLR algorithm, on three types of LR table. We present a guide to the parse-time behaviour of these algorithms which illustrates the inefficiencies in conventional Farshi-style GLR parsing. We also describe the tool GTB (Grammar Tool Box) which provides a platform for comparative studies of parsing algorithms; and use GTB to exercise the three GLR algorithms running with LR(0), SLR(1) and LR(1) tables for ANSI-C, ISO-Pascal and IBM VS-COBOL. We give results showing the size of the structures constructed by these parsers and the amount of searching required during the parse, which abstracts their runtime.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Science of Computer Programming - Volume 61, Issue 3, August 2006, Pages 228-244