Semantics and algorithms for data-dependent grammars

Trevor Jim, Yitzhak Mandelbaum, David Walker

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationPOPL'10 - Proceedings of the 37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
Pages417-430
Number of pages14
DOIs
StatePublished - Apr 20 2010
Event37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'10 - Madrid, Spain
Duration: Jan 17 2010Jan 23 2010

Publication series

NameConference Record of the Annual ACM Symposium on Principles of Programming Languages
ISSN (Print)0730-8566

Other

Other37th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'10
CountrySpain
CityMadrid
Period1/17/101/23/10

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Ambiguous grammars
  • Automata
  • Context-sensitive grammars
  • Data-dependent grammars
  • EBNF
  • Earley parsing
  • L-attributed grammars
  • Regular expressions
  • Regular right-sides
  • Scannerless parsing
  • Semantic predicates
  • Transducers

Fingerprint Dive into the research topics of 'Semantics and algorithms for data-dependent grammars'. Together they form a unique fingerprint.

Cite this