Please use this identifier to cite or link to this item:
Title: Simple, efficient, sound and complete combinator parsing for all context-free grammars, using an oracle
Authors: Ridge, Tom
First Published: Sep-2014
Presented at: Software Language Engineering - 7th International Conference, SLE 2014, Västerås, Sweden, September 15-16, 2014
Publisher: Springer International Publishing
Citation: Software Language Engineering, 7th International Conference, SLE 2014, Västerås, Sweden, September 15-16, 2014, Proceedings of, pp. 261-281
Abstract: Parsers for context-free grammars can be implemented directly and naturally in a functional style known as “combinator parsing”, using recursion following the structure of the grammar rules. Traditionally parser combinators have struggled to handle all features of context-free grammars, such as left recursion. Previous work introduced novel parser combinators that could be used to parse all context-free grammars. A parser generator built using these combinators was proved both sound and complete in the HOL4 theorem prover. Unfortunately the performance was not as good as other parsing methods such as Earley parsing. In this paper, we build on this previous work, and combine it in novel ways with existing parsing techniques such as Earley parsing. The result is a sound-and-complete combinator parsing library that can handle all context-free grammars, and has good performance.
Series/Report no.: Lecture Notes in Computer Science;
DOI Link: 10.1007/978-3-319-11245-9_15
ISBN: 978-3-319-11244-2
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © 2014, Springer. Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website.
Description: timestamp: Tue, 09 Sep 2014 10:57:11 +0200 biburl: bibsource: dblp computer science bibliography,
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
ridge14sle.pdfOther217.69 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.