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.
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 language | English |
---|---|
Pages (from-to) | 1-22 |
Number of pages | 22 |
Journal | Science of Computer Programming |
Volume | 125 |
Early online date | 20 Apr 2016 |
DOIs | |
Publication status | Published - 1 Sept 2016 |