Modelling GLL Parser Implementations. / Johnstone, Adrian; Scott, Elizabeth.

Software Language Engineering: Third International Conference, SLE 2010, Eindhoven, The Netherlands, October 12-13, 2010, Revised Selected Papers. ed. / Brian Malloy; Steffen Staab; Mark van den Brand. Springer, 2011. p. 42-61 (Lecture Notes in Computer Science; Vol. 6563).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Published

Documents

Links

Abstract

We describe the development of space-efficient implementations of GLL parsers, and the process by which we refine a set-theoretic model of the algorithm into a practical parser generator that creates practical parsers. GLL parsers are recursive descent-like, in that the structure of the parser’s code closely mirrors the grammar rules, and so grammars (and their parsers) may be debugged by tracing the running parser in a debugger. While GLL recognisers are straightforward to describe, full GLL parsers present technical traps and challenges for the unwary. In particular, naïve implementations based closely on the theoretical description of GLL can result in data structures that are not practical for grammars for real programming language grammars such as ANSI-C. We develop an equivalent formulation of the algorithm as a high-level set-theoretic model supported by table-based indices, in order to then explore a set of alternative implementations which trade space for time in ways which preserve the cubic bound.
Original languageEnglish
Title of host publicationSoftware Language Engineering: Third International Conference, SLE 2010, Eindhoven, The Netherlands, October 12-13, 2010, Revised Selected Papers
EditorsBrian Malloy, Steffen Staab, Mark van den Brand
PublisherSpringer
Pages42-61
Number of pages20
ISBN (Electronic)978-3-642-19440-5
ISBN (Print)978-3-642-19439-9
DOIs
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
Volume6563
ISSN (Print)0302-9743

Research outputs

This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 17225208