GLL syntax analysers for EBNF grammars. / Scott, Elizabeth; Johnstone, Adrian.

In: Science of Computer Programming, Vol. 166, 15.11.2018, p. 120-145.

Research output: Contribution to journalArticlepeer-review

Published

Standard

GLL syntax analysers for EBNF grammars. / Scott, Elizabeth; Johnstone, Adrian.

In: Science of Computer Programming, Vol. 166, 15.11.2018, p. 120-145.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Scott, Elizabeth ; Johnstone, Adrian. / GLL syntax analysers for EBNF grammars. In: Science of Computer Programming. 2018 ; Vol. 166. pp. 120-145.

BibTeX

@article{58d1ec5e28df486a879e36d58a9f8abf,
title = "GLL syntax analysers for EBNF grammars",
abstract = "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 simplicity. In this paper we give a formal specification for a parse tree representation of derivations which reflects the EBNF structure of the grammar, is worst case cubic size, and captures all derivations in the case of ambiguity. Particular care is needed in the case of closures with nullable bodies. We also describe an extension of GLL which directly supports the EBNF constructs. The resulting parsers are worst case cubic and follow the structure of the specifying EBNF grammar, making the parser behaviour easy to reason about. The parsers exploit the efficiency of factorisation and the use of iteration rather than recursion, retaining the structure of the specification in the presence of embedded semantic actions.",
author = "Elizabeth Scott and Adrian Johnstone",
year = "2018",
month = nov,
day = "15",
doi = "10.1016/j.scico.2018.06.001",
language = "English",
volume = "166",
pages = "120--145",
journal = "Science of Computer Programming",
issn = "0167-6423",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - GLL syntax analysers for EBNF grammars

AU - Scott, Elizabeth

AU - Johnstone, Adrian

PY - 2018/11/15

Y1 - 2018/11/15

N2 - 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 simplicity. In this paper we give a formal specification for a parse tree representation of derivations which reflects the EBNF structure of the grammar, is worst case cubic size, and captures all derivations in the case of ambiguity. Particular care is needed in the case of closures with nullable bodies. We also describe an extension of GLL which directly supports the EBNF constructs. The resulting parsers are worst case cubic and follow the structure of the specifying EBNF grammar, making the parser behaviour easy to reason about. The parsers exploit the efficiency of factorisation and the use of iteration rather than recursion, retaining the structure of the specification in the presence of embedded semantic actions.

AB - 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 simplicity. In this paper we give a formal specification for a parse tree representation of derivations which reflects the EBNF structure of the grammar, is worst case cubic size, and captures all derivations in the case of ambiguity. Particular care is needed in the case of closures with nullable bodies. We also describe an extension of GLL which directly supports the EBNF constructs. The resulting parsers are worst case cubic and follow the structure of the specifying EBNF grammar, making the parser behaviour easy to reason about. The parsers exploit the efficiency of factorisation and the use of iteration rather than recursion, retaining the structure of the specification in the presence of embedded semantic actions.

U2 - 10.1016/j.scico.2018.06.001

DO - 10.1016/j.scico.2018.06.001

M3 - Article

VL - 166

SP - 120

EP - 145

JO - Science of Computer Programming

JF - Science of Computer Programming

SN - 0167-6423

ER -