Grammar Inference for Ad Hoc Parsers

Abstract

Any time we use common string functions like split, trim, or slice, we effectively perform parsing. Yet no one ever bothers to write down grammars for such ad hoc parsers. We propose a grammar inference system that allows programmers to get input grammars from unannotated source code “for free,” enabling a range of new possibilities, from interactive documentation to grammar-aware semantic change tracking. To this end, we introduce Panini, an intermediate representation with a novel refinement type system that incorporates domain knowledge of ad ‍hoc parsing.