Structuring the GLL parsing algorithm for performance

Research output: Contribution to journalArticlepeer-review

775 Downloads (Pure)

Abstract

GLL (Generalised LL) parsing algorithms provide a sequentialisation of recursive-descent style parsing that yields efficient, compiled parsers which admit any context free grammar, including left recursive and non-left-factored rules. The resulting parsers retain the `recursively decent' property that the structure of the parser closely follows the structure of the grammar; as such it is feasible to
debug grammars by tracing the corresponding GLL parser using a conventional code debugger.

In this paper we develop two variants of the GLL algorithm called FGLL and RGLL which support (i) efficient parsing of factorised grammars and (ii) parsing using a reduced set of descriptors. Both techniques yield significant speed up on programming language grammars compared to the base GLL algorithm. We also discuss the ordering of descriptor processing and its effects on performance.
Original languageEnglish
Pages (from-to)1-22
Number of pages22
JournalScience of Computer Programming
Volume125
Early online date20 Apr 2016
DOIs
Publication statusPublished - 1 Sept 2016

Cite this