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 pedagogic value, 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.
Mon 23 OctDisplayed time zone: Lisbon change
14:00 - 15:30
|A reference GLL implementationResearch Paper
Adrian Johnstone Royal Holloway University of London, UKDOI
|Sharing Trees and Contextual Information: Re-imagining Forwarding in Attribute GrammarsResearch Paper
Lucas Kramer University of Minnesota, Eric Van Wyk Department of Computer Science and Engineering, University of Minnesota, USADOI Pre-print
|Nanopass Attribute GrammarsResearch Paper
Nathan Ringo University of Minnesota, Lucas Kramer University of Minnesota, Eric Van Wyk Department of Computer Science and Engineering, University of Minnesota, USADOI Pre-print