Semantics and Algorithms for Data-Dependent Grammars

Traditional parser generation technologies are incapable of handling the demands of modern programmers. In this paper, the authors present the design and theory of a new parsing engine, YAKKER, capable of handling the requirements of modern applications including full scannerless context-free grammars with regular expressions as right-hand sides for defining non-terminals. YAKKER also includes facilities for binding variables to intermediate parse results and using such bindings within arbitrary constraints to control parsing. These facilities allow the kind of data-dependent parsing commonly needed in systems applications, particularly those that operate over binary data.