Derivation representation using binary subtree sets. / Scott, Elizabeth; Johnstone, Adrian; van Binsbergen, L. Thomas.

In: Science of Computer Programming, Vol. 175, 15.04.2019, p. 63-84.

Research output: Contribution to journalArticle

Published

Documents

  • Accepted Manuscript

    Accepted author manuscript, 464 KB, PDF document

    Embargo ends: 25/01/20

    Licence: CC BY-NC-ND Show licence

Abstract

This paper introduces sets of binary subtree representations as an
alternative to shared packed parse forests as the output of a generalised parser, and shows how these may be generated by Earley's algorithm,
by a new GLL-style parser and by Johnson's continuation passing combinator style parsers. The set based output removes the clerical overhead associated with
graph constructions, making the parsers simpler.
Original languageEnglish
Pages (from-to)63-84
Number of pages22
JournalScience of Computer Programming
Volume175
Early online date25 Jan 2019
DOIs
Publication statusPublished - 15 Apr 2019

Research outputs

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

ID: 30348223