GLL parsing with flexible combinators. / van Binsbergen, L. Thomas; Scott, Elizabeth; Johnstone, Adrian.

2018. Paper presented at Software Language Engineering, .

Research output: Contribution to conferencePaper



  • Manuscript

    Accepted author manuscript, 829 KB, PDF-document


At SLE in 2014, Ridge presented the P3 combinator library
with which parsers can be developed for left-recursive, non-
deterministic and ambiguous grammars. A combinator ex-
pression in P3 yields a binarised grammar reflecting the ex-
pression’s structure. The grammar is given to an underlying,
generalised parsing procedure computing all derivations.

In this paper we present a combinator library with a simi-
lar architecture to P3, adjusting it to avoid grammar binari-
sation. Avoiding binarisation has a significant positive effect
on the running times of the underlying parsing procedure,
which we demonstrate using real-world grammars. Binarisa-
tion is avoided by restricting the applicability of combinators,
resulting in combinator expressions closely resembling BNF
fragments. Usability is recovered by defining coercions that
automatically convert expressions where necessary. As the
underlying parsing procedure, we use a purely functional
variant of generalised top-down (GLL) parsing.
Original languageEnglish
Number of pages13
StatePublished - 24 Oct 2018
EventSoftware Language Engineering -
Duration: 5 Nov 20186 Nov 2018


ConferenceSoftware Language Engineering
Abbreviated titleSLE 2018
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 31087568