Zobrazeno 1 - 10
of 50
pro vyhledávání: '"Adrian Johnstone"'
Publikováno v:
Science of Computer Programming. 175:63-84
This paper introduces sets of binary subtree representations as an alternative to shared packed parse forests as the output of a generalised parser, and shows how these may be generated by Earley's algorithm, by a new GLL-style parser and by Johnson'
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8ac3081690bdca5d73974ed365793443
https://doi.org/10.1016/j.scico.2019.01.008
https://doi.org/10.1016/j.scico.2019.01.008
Publikováno v:
Journal of Computer Languages, 58
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 algori
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::74e4de56e6e18911a980eee0503e3ac1
https://ir.cwi.nl/pub/29663
https://ir.cwi.nl/pub/29663
Autor:
Adrian Johnstone, Elizabeth Scott
Publikováno v:
Science of Computer Programming. 166:120-145
GLL is a worst-case cubic, recursive descent based parsing technique which can be applied to all BNF grammars without the need for grammar modification. However, EBNF grammars are often used, both for their compactness and their relative expressive s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::35a336ac26c469d4fa95a8fc5565496f
https://doi.org/10.1016/j.scico.2018.06.001
https://doi.org/10.1016/j.scico.2018.06.001
Autor:
Adrian Johnstone, Elizabeth Scott
Publikováno v:
Science of Computer Programming. 125:1-22
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 p
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8fa6b4e844674661e830610217405d37
https://doi.org/10.1016/j.scico.2016.04.003
https://doi.org/10.1016/j.scico.2016.04.003
Publikováno v:
SLE
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
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8bd6e76c2f48270815d11970d2bc4df5
https://ir.cwi.nl/pub/29666
https://ir.cwi.nl/pub/29666
Autor:
Elizabeth Scott, Adrian Johnstone
Publikováno v:
Science of Computer Programming. 97:64-68
Object oriented and pattern based metaphors for software present a solid engineering base for software understanding and construction, but sometimes impose a high performance overhead. We quantify this overhead for one form of generalised parsing and
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ef938f9f69f218e774d08b1ba4741251
https://doi.org/10.1016/j.scico.2013.11.018
https://doi.org/10.1016/j.scico.2013.11.018
Autor:
Adrian Johnstone, Elizabeth Scott
Publikováno v:
Science of Computer Programming. 78:1828-1844
Backtracking techniques which are often used to extend recursive descent (RD) parsers can have explosive run-times and cannot deal with grammars with left recursion. GLL parsers are fully general, worst-case cubic parsers which have the recursive des
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::40159e69ebc2d1742c3c1d7e4d373451
https://doi.org/10.1016/j.scico.2012.03.005
https://doi.org/10.1016/j.scico.2012.03.005
Publikováno v:
Journal of Discrete Algorithms. 13:47-58
A set X of vertices of an acyclic graph is convex if any vertex on a directed walk between elements of X is itself in X. We construct an algorithm for generating all input–output constrained convex (IOCC) sets in an acyclic digraph, which uses seve
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::15eac5e461a46263f0841970145c5eb1
https://doi.org/10.1016/j.jda.2012.02.002
https://doi.org/10.1016/j.jda.2012.02.002
Autor:
Elizabeth Scott, Adrian Johnstone
Publikováno v:
Electronic Notes in Theoretical Computer Science. 253(7):177-189
Recursive Descent (RD) parsers are popular because their control flow follows the structure of the grammar and hence they are easy to write and to debug. However, the class of grammars which admit RD parsers is very limited. Backtracking techniques m
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::76c81ed5b4d9113bd6db4dfc3339dbaf
Autor:
Elizabeth Scott, Adrian Johnstone
Publikováno v:
Science of Computer Programming. 75(1-2):55-70
In their recogniser forms, the Earley and RIGLR algorithms for testing whether a string can be derived from a grammar are worst-case cubic on general context free grammars (CFG). Earley gave an outline of a method for turning his recognisers into par
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b91b27de0f9a5dd94da834062ef89e51