Derivation representation using binary subtree sets

Elizabeth Scott, Adrian Johnstone, L. Thomas van Binsbergen

Research output: Contribution to journalArticlepeer-review

181 Downloads (Pure)


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
Early online date25 Jan 2019
Publication statusPublished - 15 Apr 2019

Cite this