GLL parsing with flexible combinators

L. Thomas van Binsbergen, Elizabeth Scott, Adrian Johnstone

Research output: Contribution to conferencePaperpeer-review

6410 Downloads (Pure)

Abstract

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 expression in P3 yields a binarised grammar reflecting the expression'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 similar architecture to P3, adjusting it to avoid grammar binarisation. Avoiding binarisation has a significant positive effect on the running times of the underlying parsing procedure, which we demonstrate using real-world grammars. Binarisation 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
Pages16-28
Number of pages13
DOIs
Publication statusPublished - Oct 2018
EventSoftware Language Engineering -
Duration: 5 Nov 20186 Nov 2018

Conference

ConferenceSoftware Language Engineering
Abbreviated titleSLE 2018
Period5/11/186/11/18

Cite this