A Reference GLL Implementation

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.