Purely functional GLL parsing. / van Binsbergen, L. Thomas; Scott, Elizabeth; Johnstone, Adrian.

In: Journal of Computer Languages, Vol. 58, 100945, 06.2020.

Research output: Contribution to journalArticlepeer-review

Published

Standard

Purely functional GLL parsing. / van Binsbergen, L. Thomas; Scott, Elizabeth; Johnstone, Adrian.

In: Journal of Computer Languages, Vol. 58, 100945, 06.2020.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

BibTeX

@article{3907bbe07f1845a8b680803651431c04,
title = "Purely functional GLL parsing",
abstract = "Generalised parsing has become increasingly important in the context of software language design and several compiler generators and language workbenches have adopted generalised parsing algorithms such as GLR and GLL. The original GLL parsing algorithms are described in low-level pseudo-code as the output of a parser generator. This paper explains GLL parsing dierently, dening the FUN-GLL algorithm as a collection of pure, mathematical functions and focussing on the logic of the algorithm by omitting implementation details. In particular, the data structures are modelled by abstract sets and relations rather than specialised implementations. The description is further simplied by omitting lookahead and adopting the binary subtree representation of derivations to avoid the clerical overhead of graph construction.Conventional parser combinators inherit the drawbacks from the recursive descent algorithms they implement. Based on FUN-GLL, this paper denes generalised parser combinators that overcome these problems. The algorithm is described in the same notation and style as FUN-GLL and uses the same data structures. Both algorithms are explained as a generalisation of basic recursive descent algorithms. The generalised parser combinators of this paper have several advantages over combinator libraries that generate internal grammars. For example, with the generalised parser combinators it is possible to parse larger permutation phrases and to write parsers for languages that are not context-free.The 'BNF combinator library' is built around the generalised parser combinators. With the library, embedded and executable syntax specications are written. The specications contain semantic actions for interpreting programs and constructing syntax trees. The library takes advantage of Haskell's type-system to type-check semantic actions and Haskell's abstraction mechanism enables `reuse through abstraction'. The practicality of the library is demonstrated by running parsers obtained from the syntax descriptions of several software languages.",
author = "{van Binsbergen}, {L. Thomas} and Elizabeth Scott and Adrian Johnstone",
year = "2020",
month = jun,
doi = "10.1016/j.cola.2020.100945",
language = "English",
volume = "58",
journal = "Journal of Computer Languages",
issn = "2590-1184",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Purely functional GLL parsing

AU - van Binsbergen, L. Thomas

AU - Scott, Elizabeth

AU - Johnstone, Adrian

PY - 2020/6

Y1 - 2020/6

N2 - Generalised parsing has become increasingly important in the context of software language design and several compiler generators and language workbenches have adopted generalised parsing algorithms such as GLR and GLL. The original GLL parsing algorithms are described in low-level pseudo-code as the output of a parser generator. This paper explains GLL parsing dierently, dening the FUN-GLL algorithm as a collection of pure, mathematical functions and focussing on the logic of the algorithm by omitting implementation details. In particular, the data structures are modelled by abstract sets and relations rather than specialised implementations. The description is further simplied by omitting lookahead and adopting the binary subtree representation of derivations to avoid the clerical overhead of graph construction.Conventional parser combinators inherit the drawbacks from the recursive descent algorithms they implement. Based on FUN-GLL, this paper denes generalised parser combinators that overcome these problems. The algorithm is described in the same notation and style as FUN-GLL and uses the same data structures. Both algorithms are explained as a generalisation of basic recursive descent algorithms. The generalised parser combinators of this paper have several advantages over combinator libraries that generate internal grammars. For example, with the generalised parser combinators it is possible to parse larger permutation phrases and to write parsers for languages that are not context-free.The 'BNF combinator library' is built around the generalised parser combinators. With the library, embedded and executable syntax specications are written. The specications contain semantic actions for interpreting programs and constructing syntax trees. The library takes advantage of Haskell's type-system to type-check semantic actions and Haskell's abstraction mechanism enables `reuse through abstraction'. The practicality of the library is demonstrated by running parsers obtained from the syntax descriptions of several software languages.

AB - Generalised parsing has become increasingly important in the context of software language design and several compiler generators and language workbenches have adopted generalised parsing algorithms such as GLR and GLL. The original GLL parsing algorithms are described in low-level pseudo-code as the output of a parser generator. This paper explains GLL parsing dierently, dening the FUN-GLL algorithm as a collection of pure, mathematical functions and focussing on the logic of the algorithm by omitting implementation details. In particular, the data structures are modelled by abstract sets and relations rather than specialised implementations. The description is further simplied by omitting lookahead and adopting the binary subtree representation of derivations to avoid the clerical overhead of graph construction.Conventional parser combinators inherit the drawbacks from the recursive descent algorithms they implement. Based on FUN-GLL, this paper denes generalised parser combinators that overcome these problems. The algorithm is described in the same notation and style as FUN-GLL and uses the same data structures. Both algorithms are explained as a generalisation of basic recursive descent algorithms. The generalised parser combinators of this paper have several advantages over combinator libraries that generate internal grammars. For example, with the generalised parser combinators it is possible to parse larger permutation phrases and to write parsers for languages that are not context-free.The 'BNF combinator library' is built around the generalised parser combinators. With the library, embedded and executable syntax specications are written. The specications contain semantic actions for interpreting programs and constructing syntax trees. The library takes advantage of Haskell's type-system to type-check semantic actions and Haskell's abstraction mechanism enables `reuse through abstraction'. The practicality of the library is demonstrated by running parsers obtained from the syntax descriptions of several software languages.

U2 - 10.1016/j.cola.2020.100945

DO - 10.1016/j.cola.2020.100945

M3 - Article

VL - 58

JO - Journal of Computer Languages

JF - Journal of Computer Languages

SN - 2590-1184

M1 - 100945

ER -