Evaluating GLR parsing algorithms

✍ Scribed by Adrian Johnstone; Elizabeth Scott; Giorgios Economopoulos

• Publisher: Elsevier Science
• Year: 2006
• Tongue: English
• Weight: 495 KB
• Volume: 61
• Category: Article
• ISSN: 0167-6423
• DOI: 10.1016/j.scico.2006.04.004

✦ Synopsis

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.