Structuring the GLL parsing algorithm for performance

• Two new variants of the GLL algorithm.
• FGLL for efficient parsing of factorised grammars.
• RGLL for parsing using a reduced set of descriptors.
• Both techniques yield significant speed up on programming language grammars compared and can be used together.
• The modifications are all at algorithm level and do not depend on inplementation details of the GLL data structures.

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 respectively 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.