Modelling GLL Parser Implementations

Adrian Johnstone; Elizabeth Scott

doi:10.1007/978-3-642-19440-5_4

Modelling GLL Parser Implementations

Adrian Johnstone, Elizabeth Scott

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

796 Downloads (Pure)

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 language	English
Title of host publication	Software Language Engineering: Third International Conference, SLE 2010, Eindhoven, The Netherlands, October 12-13, 2010, Revised Selected Papers
Editors	Brian Malloy, Steffen Staab, Mark van den Brand
Publisher	Springer
Pages	42-61
Number of pages	20
ISBN (Electronic)	978-3-642-19440-5
ISBN (Print)	978-3-642-19439-9
DOIs	https://doi.org/10.1007/978-3-642-19440-5_4
Publication status	Published - 2011

Publication series

Name	Lecture Notes in Computer Science
Volume	6563
ISSN (Print)	0302-9743

Keywords

GLL parsing
general context-free parsing
implementation spaces
time-space tradeoffs

Access to Document

10.1007/978-3-642-19440-5_4

Submitted ManuscriptSubmitted manuscript, 207 KB

http://link.springer.com/chapter/10.1007%2F978-3-642-19440-5_4

1 Conference contribution

LDT: a language definition technique
Johnstone, A., Scott, E. & van den Brand, M., 26 Mar 2011, LDTA '11 Proceedings of the Eleventh Workshop on Language Descriptions, Tools and Applications. ACM, p. 1-8 8 p. 9
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

8 Downloads (Pure)

Cite this

Johnstone, A., & Scott, E. (2011). Modelling GLL Parser Implementations. In B. Malloy, S. Staab, & M. van den Brand (Eds.), Software Language Engineering: Third International Conference, SLE 2010, Eindhoven, The Netherlands, October 12-13, 2010, Revised Selected Papers (pp. 42-61). (Lecture Notes in Computer Science; Vol. 6563). Springer. https://doi.org/10.1007/978-3-642-19440-5_4

@inproceedings{2c1e93df746c42718de6534141d0c9b5,

title = "Modelling GLL Parser Implementations",

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{\textquoteright}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{\"i}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.",

keywords = "GLL parsing, general context-free parsing, implementation spaces, time-space tradeoffs",

author = "Adrian Johnstone and Elizabeth Scott",

year = "2011",

doi = "10.1007/978-3-642-19440-5_4",

language = "English",

isbn = "978-3-642-19439-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "42--61",

editor = "Brian Malloy and Steffen Staab and {van den Brand}, Mark",

booktitle = "Software Language Engineering: Third International Conference, SLE 2010, Eindhoven, The Netherlands, October 12-13, 2010, Revised Selected Papers",

}

Johnstone, A & Scott, E 2011, Modelling GLL Parser Implementations. in B Malloy, S Staab & M van den Brand (eds), Software Language Engineering: Third International Conference, SLE 2010, Eindhoven, The Netherlands, October 12-13, 2010, Revised Selected Papers. Lecture Notes in Computer Science, vol. 6563, Springer, pp. 42-61. https://doi.org/10.1007/978-3-642-19440-5_4

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 proceeding › Conference contribution

TY - GEN

T1 - Modelling GLL Parser Implementations

AU - Johnstone, Adrian

AU - Scott, Elizabeth

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - GLL parsing

KW - general context-free parsing

KW - implementation spaces

KW - time-space tradeoffs

U2 - 10.1007/978-3-642-19440-5_4

DO - 10.1007/978-3-642-19440-5_4

M3 - Conference contribution

SN - 978-3-642-19439-9

T3 - Lecture Notes in Computer Science

SP - 42

EP - 61

BT - Software Language Engineering: Third International Conference, SLE 2010, Eindhoven, The Netherlands, October 12-13, 2010, Revised Selected Papers

A2 - Malloy, Brian

A2 - Staab, Steffen

A2 - van den Brand, Mark

PB - Springer

ER -

Modelling GLL Parser Implementations

Abstract

Publication series

Keywords

Access to Document

Research output

LDT: a language definition technique

Cite this