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 journalArticle

Published

Documents

  • Accepted Manuscript

    Accepted author manuscript, 530 KB, PDF-document

    Embargo ends: 28/06/19

    Licence: CC BY-NC-ND Show licence

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.
Original languageEnglish
Pages (from-to)120-145
Number of pages26
JournalScience of Computer Programming
Volume166
Early online date28 Jun 2018
DOIs
StatePublished - 15 Nov 2018
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 10474461