Semantics and algorithms for data-dependent grammars
Authors:
Open Access
- 2 January 2010
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 45 (1) , 417-430
Abstract
We present the design and theory of a new parsing engine, YAKKER, capable of satisfying the many needs of modern programmers and modern data processing applications. In particular, our new parsing engine handles (1) full scannerless context-free grammars with (2) regular expressions as right-hand sides for defining nonterminals. YAKKER also includes (3) facilities for binding variables to intermediate parse results and (4) 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. In addition, (5) nonterminals may be parameterized by arbitrary values, which gives the system good modularity and abstraction properties in the presence of data-dependent parsing. Finally, (6) legacy parsing libraries,such as sophisticated libraries for dates and times, may be directly incorporated into parser specifications. We illustrate the importance and utility of this rich collection of features by presenting its use on examples ranging from difficult programming language grammars to web server logs to binary data specification. We also show that our grammars have important compositionality properties and explain why such properties areimportant in modern applications such as automatic grammar induction. In terms of technical contributions, we provide a traditional high-level semantics for our new grammar formalization and show how to compile grammars into non deterministic automata. These automata are stack-based, somewhat like conventional push-down automata,but are also equipped with environments to track data-dependent parsing state. We prove the correctness of our translation of data-dependent grammars into these new automata and then show how to implement the automata efficiently using a variation of Earley's parsing algorithm.Keywords
This publication has 21 references indexed in Scilit:
- Faster Scannerless GLR Parsing2009
- Right nulled GLR parsersACM Transactions on Programming Languages and Systems, 2006
- Parsing expression grammars2004
- Elkhound: A Fast, Practical GLR Parser Generator2004
- An attribute evaluation of context-free languagesInformation Processing Letters, 1994
- Attribute-directed top-down parsingLecture Notes in Computer Science, 1992
- Attributed translationsJournal of Computer and System Sciences, 1974
- Transition network grammars for natural language analysisCommunications of the ACM, 1970
- An efficient context-free parsing algorithmCommunications of the ACM, 1970
- The next 700 programming languagesCommunications of the ACM, 1966