Evaluating GLR parsing algorithms

摘要

We describe the behaviour of three variants of GLR parsing: (ⅰ) Farshi's original correction to Tomita's non-general algorithm; (ⅱ) the Right Nulled GLR algorithm which provides a more efficient generalisation of Tomita and (ⅲ) 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.