GLL syntax analysers for EBNF grammars

Research output: Contribution to journalArticlepeer-review

729 Downloads (Pure)

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
Publication statusPublished - 15 Nov 2018

Cite this