Simple, Efficient, Sound and Complete Combinator Parsing for All Context-Free Grammars, Using an Oracle

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.