Derivation representation using binary subtree sets

Elizabeth Scott; Adrian Johnstone; L. Thomas van Binsbergen

doi:10.1016/j.scico.2019.01.008

Derivation representation using binary subtree sets

Elizabeth Scott, Adrian Johnstone, L. Thomas van Binsbergen

Research output: Contribution to journal › Article › peer-review

181 Downloads (Pure)

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 language	English
Pages (from-to)	63-84
Number of pages	22
Journal	Science of Computer Programming
Volume	175
Early online date	25 Jan 2019
DOIs	https://doi.org/10.1016/j.scico.2019.01.008
Publication status	Published - 15 Apr 2019

Access to Document

10.1016/j.scico.2019.01.008

Accepted ManuscriptAccepted author manuscript, 464 KBLicence: CC BY-NC-ND

Cite this

@article{d718368bd4a449c8b023bdaae5feaece,

title = "Derivation representation using binary subtree sets",

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 withgraph constructions, making the parsers simpler. ",

author = "Elizabeth Scott and Adrian Johnstone and {van Binsbergen}, {L. Thomas}",

year = "2019",

month = apr,

day = "15",

doi = "10.1016/j.scico.2019.01.008",

language = "English",

volume = "175",

pages = "63--84",

journal = "Science of Computer Programming",

issn = "0167-6423",

publisher = "Elsevier",

}

TY - JOUR

T1 - Derivation representation using binary subtree sets

AU - Scott, Elizabeth

AU - Johnstone, Adrian

AU - van Binsbergen, L. Thomas

PY - 2019/4/15

Y1 - 2019/4/15

N2 - 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 withgraph constructions, making the parsers simpler.

AB - 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 withgraph constructions, making the parsers simpler.

U2 - 10.1016/j.scico.2019.01.008

DO - 10.1016/j.scico.2019.01.008

M3 - Article

SN - 0167-6423

VL - 175

SP - 63

EP - 84

JO - Science of Computer Programming

JF - Science of Computer Programming

ER -