A Reference GLL Implementation

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

62 Downloads (Pure)


The Generalised-LL (GLL) context-free parsing algorithm
was introduced at the 2009 LDTA workshop, and since then a
series of variant algorithms and implementations have been
described. There is a wide variety of optimisations that may
be applied to GLL, some of which were already present in
the originally published form.
This paper presents a reference GLL implementation shorn
of all optimisations as a common baseline for the real-world
comparison of performance across GLL variants. This baseline
version has particular value for non-specialists, since
its simple form may be straightforwardly encoded in the
implementer’s preferred programming language.
We also describe our approach to low level memory management
of GLL internal data structures. Our evaluation on
large inputs shows a factor 3–4 speedup over a naïve implementation
using the standard Java APIs and a factor 4–5
reduction in heap requirements. We conclude with notes
on some algorithm-level optimisations that may be applied
independently of the internal data representation.
Original languageEnglish
Title of host publicationProceedings of the 16th ACM SIGPLAN International Conference on Software Language Engineering (SLE ’23), October 23–24, 2023, Cascais, Portugal
Number of pages13
ISBN (Electronic)979-8-4007-0396-6/23/10.
Publication statusPublished - 23 Oct 2023

Cite this